所謂周遊(Traversal)是指沿着某條搜尋路線，依次對樹中每個結點均做一次且僅做一次通路。通路結點所做的操作依賴于具體的應用問題。周遊是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。周遊方式分别為：先序周遊、中序周遊、後序周遊。二叉樹前序周遊：根-> 左-> 右；二叉樹中序周遊：左-> 根-> 右；二叉樹後序周遊：左-> 右-> 根
所謂周遊(Traversal)是指沿着某條搜尋路線，依次對樹中每個結點均做一次且僅做一次通路。通路結點所做的操作依賴于具體的應用問題。周遊是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。
周遊方式分别為：先序周遊、中序周遊、後序周遊。
周遊之前，我們先來建立一棵樹。
首先要聲明結點TreeNode類，代碼如下：
public class TreeNode {
private int val;
private TreeNode left;
private TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
// 省略get、set
}
随機建立一個tree
public class TreeBuilder {
/**
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
* / \
* 8 9
* @return
*/
public static TreeNode randomBuild() {
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node7 = new TreeNode(7);
TreeNode node6 = new TreeNode(6, null, node9);
TreeNode node5 = new TreeNode(5);
TreeNode node4 = new TreeNode(4, node8, null);
TreeNode node3 = new TreeNode(3, node6, node7);
TreeNode node2 = new TreeNode(2, node4, node5);
TreeNode node1 = new TreeNode(1, node2, node3);
return node1;
}
}
使用遞歸的方式進行周遊
public class TreePrint1 {
public static void main(String[] args) {
TreeNode head = TreeBuilder.randomBuild();
System.out.println("preorderTraversal");
preorderTraversal(head);
System.out.println("\n\ninorderTraversal");
inorderTraversal(head);
System.out.println("\n\npostorderTraversal");
postorderTraversal(head);
}
/**
* 二叉樹前序周遊 根-> 左-> 右
*/
private static void preorderTraversal(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.getVal() + " ");
preorderTraversal(head.getLeft());
preorderTraversal(head.getRight());
}
/**
* 二叉樹中序周遊 左-> 根-> 右
*/
private static void inorderTraversal(TreeNode head) {
if (head == null) {
return;
}
inorderTraversal(head.getLeft());
System.out.print(head.getVal() + " ");
inorderTraversal(head.getRight());
}
/**
* 二叉樹後序周遊 左-> 右-> 根
*/
private static void postorderTraversal(TreeNode head) {
if (head == null) {
return;
}
postorderTraversal(head.getLeft());
postorderTraversal(head.getRight());
System.out.print(head.getVal() + " ");
}
}
使用非遞歸的方式進行周遊
public class TreePrint2 {
public static void main(String[] args) {
TreeNode head = TreeBuilder.randomBuild();
System.out.println("preorderTraversal");
preorderTraversal(head);
System.out.println("\n\ninorderTraversal");
inorderTraversal(head);
System.out.println("\n\npostorderTraversal");
postorderTraversal(head);
}
/**
* 二叉樹前序周遊 根-> 左-> 右
*/
private static void preorderTraversal(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = head;
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.print(node.getVal() + " ");
stack.push(node);
node = node.getLeft();
}
if (!stack.isEmpty()) {
node = stack.pop().getRight();
}
}
}
/**
* 二叉樹中序周遊 左-> 根-> 右
*/
private static void inorderTraversal(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = head;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (!stack.isEmpty()) {
node = stack.pop();
System.out.print(node.getVal() + " ");
node = node.getRight();
}
}
}
/**
* 二叉樹後序周遊 左-> 右-> 根
*/
private static void postorderTraversal(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = head; // 目前根節點
TreeNode last = null; // 上一次列印的節點
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (!stack.isEmpty()) {
node = stack.pop();
/*
沒有右節點，目前節點可以列印了
目前節點的右節點就是上一次列印的節點，目前節點可以列印了
“node = null”表示目前節點的這個分支不能再處理了，因為外層循環是“node = node.getLeft()”
*/
if (node.getRight() == null || node.getRight() == last) {
System.out.print(node.getVal() + " ");
last = node;
node = null;
}else {
stack.add(node);
node = node.getRight();
}
}
}
}
}
__EOF__
歡迎轉載，但請注明出處！
歡迎大家一起交流學習！如果有什麼疑問，大家可以在評論區一起交流！
如果您覺得文章對您有幫助，可以點選文章右下角【推薦】一下。您的鼓勵是我的最大動力！