二叉樹的遞歸遍歷和非遞歸遍歷（附詳細例子）
二叉樹的遍歷主要有遞歸實現和非遞歸實現，遞歸實現比較好理解，非遞歸實現主要是利用了棧的思想，後進先出，本文實現二叉樹的非遞歸遍歷主要是用了LinkedList可以當做棧使用的功能。具體例子如下：
package com.sheepmu;
import java.util.LinkedList;
public class BinaryTree
{
private TreeNode root;// 根節點
public BinaryTree()
{
}
public BinaryTree(TreeNode root)
{
this.root = root;
}
public TreeNode getRoot()
{
return root;
}
public void setRoot(TreeNode root)
{
this.root = root;
}
/**
* 節點類
*/
private static class TreeNode
{
private String data = null;// 數據部分
private TreeNode left;// 左節點的引用
private TreeNode right;// 右節點的引用
public TreeNode(String data, TreeNode left, TreeNode right)//節點的構造函數，測試函數中創建節點就是用了它
{
this.data = data;
this.left = left;
this.right = right;
}
public String getData()//節點類的get和set方法
{
return data;
}
public void setData(String data)
{
this.data = data;
}
public TreeNode getLeft()
{
return left;
}
public void setLeft(TreeNode left)
{
this.left = left;
}
public TreeNode getRight()
{
return right;
}
public void setRight(TreeNode right)
{
this.right = right;
}
}
/**
* 遞歸 前續遍歷
*/
public void preOrder(TreeNode node)
{
if (node != null)
{
System.out.print(node.getData()+" ");
preOrder(node.getLeft());
preOrder(node.getRight());
}
}
/**
* 遞歸 中續遍歷
*/
public void inOrder(TreeNode node)
{
if (node != null)
{
inOrder(node.getLeft());
System.out.print(node.getData()+" ");
inOrder(node.getRight());
}
}
/**
* 遞歸 後續遍歷
*/
public void postOrder(TreeNode node)
{
if (node != null)
{
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.print(node.getData()+" ");
}
}
/**
* 非遞歸 前續遍歷
*/
public void preOrderNoRecursion()
{
LinkedList stack = new LinkedList();
stack.push(root);
TreeNode current = null;
while (!stack.isEmpty())
{
current = stack.pop();
System.out.print(current.data+" ");
if (current.getRight() != null)
stack.push(current.getRight());
if (current.getLeft() != null)
stack.push(current.getLeft());
}
System.out.println();
}
/**
* 非遞歸 中續遍歷
*/
public void inorderNoRecursion()
{
LinkedList stack = new LinkedList();
TreeNode current = root;
while (current != null || !stack.isEmpty())
{
while(current != null)
{
stack.push(current);
current = current.getLeft();
}
if (!stack.isEmpty())
{
current = stack.pop();
System.out.print(current.data+" ");
current = current.getRight();
}
}
System.out.println();
}
/**
* 非遞歸 後續遍歷
*/
public void postorderNoRecursion()
{
TreeNode rNode = null;
TreeNode current = root;
LinkedList stack = new LinkedList();
while(current != null || !stack.isEmpty())
{
while(current != null)
{
stack.push(current);
current = current.getLeft();
}
current = stack.pop();
while (current != null && (current.getRight() == null ||current.getRight() == rNode))
{
System.out.print(current.data+" ");
rNode = current;
if (stack.isEmpty())
{
System.out.println();
return;
}
current = stack.pop();
}
stack.push(current);
current = current.getRight();
}
}
public static void main(String[] args)
{
TreeNode l2 = new TreeNode("E", null, null);//這五行構造一棵二叉樹
TreeNode r2 = new TreeNode("D", null, null);
TreeNode l1 = new TreeNode("B",null, r2);// 根節點左子樹
TreeNode r1 = new TreeNode("C", l2, null);// 根節點右子樹
TreeNode root = new TreeNode("A", l1, r1);// 創建根節點
BinaryTree bt = new BinaryTree(root);
System.out.print(" 遞歸 前序遍歷------->");
bt.preOrder(bt.getRoot());
System.out.print(" 非遞歸 前序遍歷------->");
bt.postorderNoRecursion();
System.out.print(" 遞歸 中序遍歷------->");
bt.inOrder(bt.getRoot());
System.out.print(" 非遞歸 中序遍歷------->");
bt.inorderNoRecursion();
System.out.print(" 遞歸 後序遍歷------->");
bt.postOrder(bt.getRoot());
System.out.print(" 非遞歸 後序遍歷------->");
bt.postorderNoRecursion();
}
}
遞歸 前序遍歷------->A B D C E 非遞歸 前序遍歷------->D B E C A
