二叉樹是一種非常重要的資料結構，很多其它資料結構都是基于二叉樹的基礎演變而來的。對于二叉樹，有前序、中序以及後序三種周遊方法。因為樹的定義本身就是遞歸定義，是以采用遞歸的方法去實作樹的三種周遊不僅容易了解而且代碼很簡潔。而對于樹的周遊若采用非遞歸的方法，就要采用棧去模拟實作。在三種周遊中，前序和中序周遊的非遞歸算法都很容易實作，非遞歸後序周遊實作起來相對來說要難一點。
節點分布如下:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* @author 李文浩
* @version 2017/7/30.
*/
public class BinaryTree {
/**
* 節點定義
*/
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
/**
* 高度，左右子樹中的較大值
*
* @param node
* @return
*/
public static int height(TreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = height(node.left);
int rightHeight = height(node.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
/**
* 層序周遊一顆二叉樹，用廣度優先搜尋的思想，使用一個隊列來按照層的順序存放節點
* 先将根節點入隊列，隻要隊列不為空，然後出隊列，并通路，接着講通路節點的左右子樹依次入隊列
*
* @param node
*/
public static void levelTraversal(TreeNode node) {
if (node == null)
return;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(node);
TreeNode treeNode;
while (!queue.isEmpty()) {
treeNode = queue.poll();
System.out.print(treeNode.val + " ");
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
}
}
/**
* 先序遞歸
*
* @param treeNode
*/
public static void preOrder(TreeNode treeNode) {
if (treeNode != null) {
System.out.print(treeNode.val + " ");
preOrder(treeNode.left);
preOrder(treeNode.right);
}
}
/**
* 中序遞歸
*
* @param treeNode
*/
public static void inOrder(TreeNode treeNode) {
if (treeNode != null) {
inOrder(treeNode.left);
System.out.print(treeNode.val + " ");
inOrder(treeNode.right);
}
}
/**
* 後序遞歸
*
* @param treeNode
*/
public static void postOrder(TreeNode treeNode) {
if (treeNode != null) {
postOrder(treeNode.left);
postOrder(treeNode.right);
System.out.print(treeNode.val + " ");
}
}
/**
* 先序非遞歸：
* 這種實作類似于圖的深度優先周遊（DFS）。
* 維護一個棧，将根節點入棧，然後隻要棧不為空，出棧并通路，
* 接着依次将通路節點的右節點、左節點入棧。
* 這種方式應該是對先序周遊的一種特殊實作（看上去簡單明了），
* 但是不具備很好的擴充性，在中序和後序方式中不适用
*
* @param root
*/
public static void preOrderStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode treeNode = stack.pop();
System.out.print(treeNode.val + " ");
if (treeNode.right != null) {
stack.push(treeNode.right);
}
if (treeNode.left != null) {
stack.push(treeNode.left);
}
}
}
/**
* 先序非遞歸2：
* 利用棧模拟遞歸過程實作循環先序周遊二叉樹。
* 這種方式具備擴充性，它模拟遞歸的過程，将左子樹點不斷的壓入棧，直到null，
* 然後處理棧頂節點的右子樹。
*
* @param root
*/
public static void preOrderStack2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
//将左子樹點不斷的壓入棧
while (treeNode != null) {
//先通路再入棧
System.out.print(treeNode.val + " ");
stack.push(treeNode);
treeNode = treeNode.left;
}
//出棧并處理右子樹
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}
/**
* 中序非遞歸：
* 利用棧模拟遞歸過程實作循環中序周遊二叉樹。
* 思想和上面的先序非遞歸2相同，
* 隻是通路的時間是在左子樹都處理完直到null的時候出棧并通路。
*
* @param treeNode
*/
public static void inOrderStack(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<>();
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.left;
}
//左子樹進棧完畢
if (!stack.isEmpty()) {
treeNode = stack.pop();
System.out.print(treeNode.val + " ");
treeNode = treeNode.right;
}
}
}
public static class TagNode {
TreeNode treeNode;
boolean isFirst;
}
/**
* 後序非遞歸：
* 後序周遊不同于先序和中序，它是要先處理完左右子樹，
* 然後再處理根(回溯)。
* <p>
* <p>
* 對于任一結點P，将其入棧，然後沿其左子樹一直往下搜尋，直到搜尋到沒有左孩子的結點，
* 此時該結點出現在棧頂，但是此時不能将其出棧并通路，是以其右孩子還為被通路。
* 是以接下來按照相同的規則對其右子樹進行相同的處理，當通路完其右孩子時，該結點又出現在棧頂，
* 此時可以将其出棧并通路。這樣就保證了正确的通路順序。
* 可以看出，在這個過程中，每個結點都兩次出現在棧頂，隻有在第二次出現在棧頂時，才能通路它。
* 是以需要多設定一個變量辨別該結點是否是第一次出現在棧頂，這裡是在樹結構裡面加一個标記，然後合成一個新的TagNode。
*
* @param treeNode
*/
public static void postOrderStack(TreeNode treeNode) {
Stack<TagNode> stack = new Stack<>();
TagNode tagNode;
while (treeNode != null || !stack.isEmpty()) {
//沿左子樹一直往下搜尋，直至出現沒有左子樹的結點
while (treeNode != null) {
tagNode = new TagNode();
tagNode.treeNode = treeNode;
tagNode.isFirst = true;
stack.push(tagNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty()) {
tagNode = stack.pop();
//表示是第一次出現在棧頂
if (tagNode.isFirst == true) {
tagNode.isFirst = false;
stack.push(tagNode);
treeNode = tagNode.treeNode.right;
} else {
//第二次出現在棧頂
System.out.print(tagNode.treeNode.val + " ");
treeNode = null;
}
}
}
}
/**
* 後序非遞歸2：
* 要保證根結點在左孩子和右孩子通路之後才能通路，是以對于任一結點P，先将其入棧。如果P不存在左孩子和右孩子，則可以直接通路它；
* 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被通路過了，則同樣可以直接通路該結點。
* 若非上述兩種情況，則将P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被通路，
* 左孩子和右孩子都在根結點前面被通路。
*
* @param treeNode
*/
public static void postOrderStack2(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<>();
TreeNode currentTreeNode;
TreeNode preTreeNode = null;
stack.push(treeNode);
while (!stack.isEmpty()) {
currentTreeNode = stack.peek();
//如果目前結點沒有孩子結點或者孩子節點都已被通路過
if ((currentTreeNode.left == null && currentTreeNode.right == null) ||
(preTreeNode != null && (preTreeNode == currentTreeNode.left || preTreeNode == currentTreeNode.right))) {
System.out.print(currentTreeNode.val + " ");
stack.pop();
preTreeNode = currentTreeNode;
} else {
if (currentTreeNode.right != null) {
stack.push(currentTreeNode.right);
}
if (currentTreeNode.left != null) {
stack.push(currentTreeNode.left);
}
}
}
}
}
參考文檔
- 二叉樹的非遞歸周遊
- JAVA下實作二叉樹的先序、中序、後序、層序周遊（遞歸和循環）