數(shù)據(jù)結(jié)構(gòu)采用 --------------- 二叉鏈表結(jié)構(gòu)
本文主要描述二叉樹的先序、中序、后序、層序的遞歸和非遞歸遍歷。
class TreeNode<T> {
//下標(biāo)
public int index;
//數(shù)據(jù)
public T data;
//左子樹
public TreeNode<T> left;
//右子樹
public TreeNode<T> right;
public TreeNode(int index, T data) {
this.index = index;
this.data = data;
}
}
創(chuàng)建初始化數(shù)據(jù)
TestBinaryTree.TreeNode<String> treeNode1=new TestBinaryTree.TreeNode<String>(1,"A");
TestBinaryTree.TreeNode<String> treeNode2=new TestBinaryTree.TreeNode<String>(2,"B");
TestBinaryTree.TreeNode<String> treeNode3=new TestBinaryTree.TreeNode<String>(3,"C");
TestBinaryTree.TreeNode<String> treeNode4=new TestBinaryTree.TreeNode<String>(4,"D");
//指向關(guān)系
treeNode1.left=treeNode2;
treeNode1.right=treeNode3;
treeNode2.left=treeNode4;
4種遍歷方法的基序一致，得到的結(jié)果卻不一樣：
先(前)序：當(dāng)前移步操作到這個節(jié)點后，就輸出該節(jié)點的值，并繼續(xù)遍歷其左右子樹。(根左右)
中序：當(dāng)前移步操作到這個節(jié)點后，將其暫存，遍歷完左子樹后，再輸出該節(jié)點的值，然后遍歷右子樹。(左根右)
后序：當(dāng)前移步操作到這個節(jié)點后，將其暫存，遍歷完左右子樹后，再輸出該節(jié)點的值。(左右根)
層序：按照二叉樹的層次輸出，從左到右，從上到下依次輸出。
層序：A B C D
前序：A B D C
中序：D B A C
后序：D B C A
二叉樹數(shù)據(jù)源
PS:這里使用的二叉樹畫圖是由一個網(wǎng)站生成的。數(shù)據(jù)結(jié)構(gòu)動態(tài)生成神器
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
還有一個好用的在線作圖工具：
https://www.processon.com/
前序遍歷：
前序
遞歸先序遍歷
遞歸前序遍歷很容易理解，先輸出節(jié)點的值，再遞歸遍歷左右子樹。中序和后序的遞歸類似，改變根節(jié)點輸出位置即可。
//前序-----迭代方式遍歷
public void printBeforeSoft(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
printBeforeSoft(node.left);
printBeforeSoft(node.right);
}
非遞歸先序遍歷
因為要在遍歷完節(jié)點的左子樹后接著遍歷節(jié)點的右子樹，為了能找到該節(jié)點，需要使用棧來進(jìn)行暫存。中序和后序也都涉及到回溯，所以都需要用到棧。
//前序-----非迭代方式遍歷------壓棧方式
public void printBeforeSoft1(TreeNode node) {
if (node == null) {
return;
}
// 用來暫存節(jié)點的棧
Stack<TreeNode<String>> datas = new Stack<>();
datas.push(node);
// 只要棧不為空，都進(jìn)入循環(huán)
while (!datas.isEmpty()) {
//將棧頂元素取出來并打印，接著把右、左節(jié)點壓入棧,一直循環(huán)下去，直到棧為空。
TreeNode<String> treeNode = datas.pop();
System.out.println("--->" + treeNode.data);
if (treeNode.right != null) {
datas.push(treeNode.right);
}
if (treeNode.left != null) {
datas.push(treeNode.left);
}
}
}
非遞歸前序遍歷輸出結(jié)果：A B D C
中序遍歷
中序
遞歸中序遍歷
過程和遞歸先序遍歷類似
//中序遍歷
public void printMidSoft(TreeNode node) {
if (node == null) {
return;
}
printMidSoft(node.left);
System.out.print(node.data + " ");
printMidSoft(node.right);
}
非遞歸中序遍歷
和非遞歸先序遍歷類似，唯一區(qū)別是當(dāng)前移步操作到這個節(jié)點時，并不直接輸出該節(jié)點，而是當(dāng)此結(jié)點下左子數(shù)為空時，從棧中彈出，再輸出，接著壓入右邊子節(jié)點。
//中序-----非迭代方式遍歷------壓棧方式
public void printMidSoft1(TreeNode node) {
if (node == null) {
return;
}
System.out.println();
Stack<TreeNode<String>> datas = new Stack<>();
TreeNode head = node;
while (!datas.isEmpty() || head != null) {
if (head != null) {
datas.push(head);
head = head.left;
} else {
head = datas.pop();
System.out.print(head.data + " ");
head = head.right;
}
}
}
非遞歸中序遍歷：D B A C
后序遍歷
后序
遞歸后序遍歷
過程和遞歸先序遍歷類似
//后序遍歷
public void printPostSoft(TreeNode node) {
if (node == null) {
return;
}
printPostSoft(node.left);
printPostSoft(node.right);
System.out.print(node.data + " ");
}
非遞歸后序遍歷
后續(xù)遍歷和先序、中序遍歷不太一樣。
后序遍歷在決定是否可以輸出當(dāng)前節(jié)點的值的時候，需要考慮其左右子樹是否都已經(jīng)遍歷完成。
所以有多種思路。如用雙棧、斷鏈標(biāo)記、末尾標(biāo)記等。
方案一:雙棧
//后序-----非迭代方式遍歷------壓棧方式---雙棧
public void printPostSoft1(TreeNode node) {
if (node == null) {
return;
}
TreeNode head = node;
System.out.println();
Stack<TreeNode<String>> datas = new Stack<>();
Stack<TreeNode> twoDatas = new Stack<>();
datas.push(head);
while (!datas.isEmpty()) {
head = datas.pop();
twoDatas.push(head);
if (head.left != null) {
datas.push(head.left);
}
if (head.right != null) {
datas.push(head.right);
}
}
while (!twoDatas.isEmpty()) {
System.out.print(twoDatas.pop().data + " ");
}
}
方案二：斷鏈標(biāo)記
//后序-----非迭代方式遍歷------壓棧方式 2
public void printPostSoft2(TreeNode node) {
if (node != null) {
System.out.println();
Stack<TreeNode<String>> datas = new Stack<>();
datas.push(node);
TreeNode head = node;
while (!datas.isEmpty()) {
head = datas.peek();
if (head.left != null) {
datas.push(head.left);
head.left = null;
} else if (head.right != null) {
datas.push(head.right);
head.right = null;
} else {
datas.pop();
System.out.print(head.data + " ");
}
}
}
}
方案三：末尾標(biāo)記
//后序-----非迭代方式遍歷------壓棧方式 3
public void printPostSoft3(TreeNode root) {
if (root != null) {
Stack<TreeNode<String>> datas = new Stack<>();
TreeNode node = root;
TreeNode lastVisit = root;
while (node != null || !datas.isEmpty()) {
while (node != null) {
datas.push(node);
node = node.left;
}
//查看當(dāng)前棧頂元素
node = datas.peek();
//如果其右子樹也為空，或者右子樹已經(jīng)訪問
//則可以直接輸出當(dāng)前節(jié)點的值
if (node.right == null || node.right == lastVisit) {
System.out.print(node.data + " ");
datas.pop();
lastVisit = node;
node = null;
} else {
//否則，繼續(xù)遍歷右子樹
node = node.right;
}
}
}
非遞歸后序遍歷：D B C A
層序：
與前面三個都不一樣，按照二叉樹的層次輸出，從左到右，從上到下依次輸出。
這里采用隊列的方式實現(xiàn)(LinkedList剛好是一個雙向鏈表的隊列)。
//層序
public void levelOrderTrav(TreeNode n) {
Queue<TreeNode> q = new LinkedList<>();
q.add(n);
while (q.size() != 0) {
n = q.poll();
System.out.print(" " + n.data);
if (n.left != null)
q.add(n.left);
if (n.right != null)
q.add(n.right);
}
}
有什么錯誤請留言糾正。
