溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關Java中的遍歷怎么利用二叉樹實現，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
遞歸實現
public void preorder_Traversal(TreeNode root)
{
if(root==null)return;
//訪問節點的邏輯代碼塊
System.out.print(root.val+" ");
preorder_Traversal(root.left);
preorder_Traversal(root.right);
}非遞歸過程如下：
1.每遍歷一個節點的時候，先節點入棧，然后尋找當前節點的左子節點。（因為是前序遍歷，所以在節點入棧之前就可以對節點進行訪問）
2.當某個節點的左子節點，當左子節點不為空的時候，重復過程1.
3.當左子節點為空的時候將當前節點出棧，并且通過其尋找右子節點，右子節點不為空的時候，重復過程1-2
4.當右子節點也為空的時候，則跳回上一個該節點的父節點（即因為當前節點已經出棧，所以現在在棧中最上層的節點是當前節點的父節點）
非遞歸實現
public void preorder(TreeNode root)
{
Stack<TreeNode> stack=new Stack<>();
while(root!=null||!stack.isEmpty())
{
//當前節點不為空，則入棧，確保最后遍歷到的節點沒有左子節點
//因為是前序遍歷，所以再遍歷到每個節點的時候，都可以先訪問，再尋找其左右子節點。
while(root!=null)
{
System.out.print(root.val+" ");
stack.push(root);
root=root.left;
}
if(!stack.empty())
{
//把這兩步看成是一步，找到右節點，并把已處理的中節點從stack當中去除
root=stack.pop();
root=root.right;
}
}
}
遞歸實現
public void inorder_Traversal(TreeNode root)
{
if(root==null)return;
inorder_Traversal(root.left);
//訪問節點的邏輯代碼塊
System.out.print(root.val+" ");
inorder_Traversal(root.right);
}非遞歸
對比前序、中序，發現代碼幾乎一模一樣，但唯一的不同的是，訪問節點的位置不一樣，中序遍歷是當左子節點被訪問過，或者不存在的時候，才可以訪問中間節點，所以再該處，訪問節點的位置放在了當左子節點不存在的時候，即節點出棧的時候，即是左子節點不存在的時候進行訪問。
非遞歸實現
public void Inorder(TreeNode root)
{
Stack<TreeNode> stack=new Stack<>();
while(root!=null||!stack.isEmpty())
{
//當前節點不為空，則入棧，確保最后遍歷到的節點沒有左子節點
while(root!=null)
{
stack.push(root);
root=root.left;
}
//通過當前節點，跳到當前節點的右節點，因為是中序遍歷，所以當前節點沒有左節點的時候，就
可以訪問當前節點
if(!stack.empty())
{
root=stack.pop();
System.out.print(root.val+" ");
root=root.right;
}
}
}
遞歸實現
public void postorder_Traversal(TreeNode root)
{
if(root==null)return;
postorder_Traversal(root.left);
postorder_Traversal(root.right);
//訪問節點的邏輯代碼塊
System.out.print(root.val+" ");
}非遞歸版本一
借助兩個棧來存儲我們的節點以及標示位，過程如下：
1.每遍歷一個節點的時候，先節點入棧s，并且s2入棧一個標識位0，然后尋找當前節點的左子節點。
2.當某個節點的左子節點，當左子節點不為空的時候，重復過程1.
3.當左子節點為空的時候將當前節點peek出（即將節點拿出，但棧中還是有該節點），并且此時將s2對應棧頂的標識位改為1，通過其尋找右子節點，右子節點不為空的時候，重復過程1-2
4.當右子節點也為空的時候，并且s2對應的標識符為1的時候，則彈出s1棧頂的當前節點，并且將s2的標識符彈出（即因為當前節點還沒有出棧，所以現在在棧中最上層的節點是當前節），注意s1彈出當前節點并訪問，但是不賦值給root，在這個root此時還是null
5.進入過程3，此時root被peek賦值到當前節點的父節點（因為在過程4當中，已經pop出了當前節點，所以s1棧頂是當前節點的父節點）的右子節點。
6.重復過程1-5
public void Postorder(TreeNode root)
{
Stack<TreeNode> s =new Stack<>();
Stack<Integer> s2 =new Stack<>();
Integer i=new Integer(1);
while(root!=null||!s.isEmpty())
{
//只要當前節點非空，就入棧
while(root!=null)
{
s.push(root);
s2.push(new Integer(0));
root=root.left;
}
//s2當中如果存1，則意味著當前s1對應的節點的左右子節點都已經遍歷過了。
while(!s.empty()&&s2.peek().equals(i))
{
s2.pop();
System.out.print(s.pop().val+" ");
}
if(!s.isEmpty())
{
s2.pop();
s2.push(new Integer(1));
root=s.peek();
root=root.right;
}
}
}非遞歸版本二
實現思路：
在進行后序遍歷的時候是先要遍歷左子樹，然后在遍歷右子樹，最后才遍歷根節點。所以在非遞歸的實現中要先把根節點入棧，然后再把左子樹入棧直到左子樹為空，此時停止入棧。此時棧頂就是需要訪問的元素，所以直接取出訪問p。在訪問結束后，還要判斷被訪問的節點p是否為棧頂節點的左子樹，如果是的話那么還需要訪問棧頂節點的右子樹，所以將棧頂節點的右子樹取出賦值給p。如果不是的 話則說明棧頂節點的右子樹已經訪問完了，那么現在可以訪問棧頂節點了，所以此時將p賦值為null。判斷結束的條件是p不為空或者棧不為空，若果兩個條件都不滿足的話，說明所有節點都已經訪問完成。
非遞歸實現
public void postOrder(Node root) {
Stack<Node> s = new Stack<Node>();
Node p = root;
while (p != null || !s.empty()) {
while(p != null) {
s.push(p);
p = p.left;
}
p = s.pop();
System.out.print(p.val+" ");
//這里需要判斷一下，當前p是否為棧頂的左子樹，如果是的話那么還需要先訪問右子樹才能訪問根節點
//如果已經是不是左子樹的話，那么說明左右子書都已經訪問完畢，可以訪問根節點了，所以講p復制為NULL
//取根節點
if (!s.empty() && p == s.peek().left) {
p = s.peek().right;
}
else p = null;
}
} 
用隊列實現，步驟是：
1.對于不為空的結點，先把該結點加入到隊列中；
2.從隊中拿出結點，如果該結點的左右結點不為空，就分別把左右結點加入到隊列中；
3.重復以上操作直到隊列為空；
public void LaywerTraversal(TreeNode root){
if(root==null) return;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
TreeNode currentNode;
while(!list.isEmpty()){
currentNode=list.poll();
System.out.println(currentNode.val);
if(currentNode.left!=null){
list.add(currentNode.left);
}
if(currentNode.right!=null){
list.add(currentNode.right);
}
}
}以上就是Java中的遍歷怎么利用二叉樹實現，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
