樹(shù)是一種經(jīng)常用到的結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合
樹(shù)的每一個(gè)節(jié)點(diǎn)有一個(gè)值和一個(gè)包含所有子節(jié)點(diǎn)的列表明未，從圖的觀點(diǎn)來(lái)看槽华，樹(shù)也可視為一個(gè)擁有N 個(gè)節(jié)點(diǎn)和N-1 條邊的一個(gè)有向無(wú)環(huán)圖。
二叉樹(shù)是一種更為典型的樹(shù)狀結(jié)構(gòu)趟妥。如它名字所描述的那樣硼莽，二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)，通常子樹(shù)被稱作“左子樹(shù)”和“右子樹(shù)”煮纵。
樹(shù)的遍歷
-
前序遍歷
首先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹(shù)偏螺，最后遍歷右子樹(shù)
F
/ \
B G
/ \ \
A D I
/ \ /
C E H
//遍歷結(jié)構(gòu)是
F行疏、B、A套像、D酿联、C、E夺巩、G贞让、I、H
-
中序遍歷
先遍歷左子樹(shù)柳譬，然后訪問(wèn)根節(jié)點(diǎn)喳张，最后訪問(wèn)右子樹(shù)
F
/ \
B G
/ \ \
A D I
/ \ /
C E H
//遍歷結(jié)構(gòu)是
A、B美澳、C销部、D、E制跟、F舅桩、G、H雨膨、I
-
后序遍歷
先遍歷左子樹(shù)擂涛，然后遍歷右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)
F
/ \
B G
/ \ \
A D I
/ \ /
C E H
//遍歷結(jié)構(gòu)是
A聊记、C撒妈、E、D排监、B踩身、H、I社露、G挟阻、F
總結(jié)
所謂前中后都是根據(jù)根節(jié)點(diǎn)的位置來(lái)命名的。后序在數(shù)學(xué)表達(dá)式中廣泛使用，編寫(xiě)程序來(lái)解析后綴法更加容易附鸽。
這里舉一個(gè)例子：
對(duì)于這個(gè)圖脱拼，我們使用中序遍歷很容易能找出表達(dá)式：4x(7-2)+5
如果你想對(duì)這棵樹(shù)進(jìn)行后序遍歷，使用棧來(lái)處理表達(dá)式會(huì)變得更加容易坷备。 每遇到一個(gè)操作符熄浓，就可以從棧中彈出棧頂?shù)膬蓚€(gè)元素，計(jì)算并將結(jié)果返回到棧中省撑。
遍歷
我們有三種常用的遍歷方法赌蔑、遞歸、迭代竟秫、morris娃惯，我們以給定的節(jié)點(diǎn)類如下，分別介紹三種遍歷方法
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
-
遞歸
//遞歸邏輯是最簡(jiǎn)單的肥败，我們只需要把輸出加在不同的位置 public static void order(TreeNode tree) { if (tree == null) return; //前序?qū)懛ㄖ呵常∠旅娲a注釋 // System.out.printf(tree.val + ""); //然后輸出左節(jié)點(diǎn) preOrder(tree.left); //前序?qū)懛ǎ∠旅娲a注釋 // System.out.printf(tree.val + ""); //然后輸出右節(jié)點(diǎn) preOrder(tree.right); //后序?qū)懛裕∠旅娲a注釋 // System.out.printf(tree.val + ""); } -
迭代
本質(zhì)上是在模擬遞歸皿哨，因?yàn)樵谶f歸的過(guò)程中使用了系統(tǒng)棧，所以在迭代的解法中常用
Stack來(lái)模擬系統(tǒng)棧纽谒。-
前序
首先我們應(yīng)該創(chuàng)建一個(gè)
Stack用來(lái)存放節(jié)點(diǎn)证膨，首先我們想要打印根節(jié)點(diǎn)的數(shù)據(jù)，此時(shí)Stack里面的內(nèi)容為空鼓黔，所以我們優(yōu)先將頭結(jié)點(diǎn)加入Stack椎例，然后打印。之后我們應(yīng)該先打印左子樹(shù)请祖，然后右子樹(shù)订歪。所以先加入 Stack 的就是右子樹(shù)，然后左子樹(shù)肆捕。
此時(shí)你能得到的流程如下:
-
```java
public static void preOrderIteration(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
```
-
中序
- 同理創(chuàng)建一個(gè) Stack刷晋，然后按 左 中 右的順序輸出節(jié)點(diǎn)。
- 盡可能的將這個(gè)節(jié)點(diǎn)的左子樹(shù)壓入 Stack慎陵，此時(shí)棧頂?shù)脑厥亲钭髠?cè)的元素眼虱，其目的是找到一個(gè)最小單位的子樹(shù)(也就是最左側(cè)的一個(gè)節(jié)點(diǎn))，并且在尋找的過(guò)程中記錄了來(lái)源席纽，才能返回上層,同時(shí)在返回上層的時(shí)候已經(jīng)處理完畢左子樹(shù)了捏悬。。
- 當(dāng)處理完最小單位的子樹(shù)時(shí)润梯，返回到上層處理了中間節(jié)點(diǎn)过牙。（如果把整個(gè)左中右的遍歷都理解成子樹(shù)的話甥厦，就是處理完 左子樹(shù)->中間(就是一個(gè)節(jié)點(diǎn))->右子樹(shù)）
- 如果有右節(jié)點(diǎn)，其也要進(jìn)行中序遍歷寇钉。
當(dāng)整個(gè)左子樹(shù)退棧的時(shí)候這個(gè)時(shí)候輸出了該子樹(shù)的根節(jié)點(diǎn) 2刀疙，之后輸出中間節(jié)點(diǎn) 1。然后處理根節(jié)點(diǎn)為3右子樹(shù)扫倡。
```java
public static void inOrderIteration(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
cur = node.right;
}
}
}
```
-
后序
//1 前序遍歷的過(guò)程 是 中左右谦秧。 //2 將其轉(zhuǎn)化成 中右左。也就是壓棧的過(guò)程中優(yōu)先壓入左子樹(shù)撵溃，在壓入右子樹(shù)疚鲤。 //3 然后將這個(gè)結(jié)果返回來(lái)，這里是利用棧的先進(jìn)后出倒序打印缘挑。 public static void postOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(head); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); if (node.left != null) { stack1.push(node.left); } if (node.right != null) { stack1.push(node.right); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().value + " "); } }//1 用一個(gè)指針 cur 標(biāo)記當(dāng)前退出的節(jié)點(diǎn)是什么集歇。 //2 后序遍歷的過(guò)程中在遍歷完左子樹(shù)跟右子樹(shù) cur 都會(huì)回到根結(jié)點(diǎn)。所以當(dāng)前不管是從左子樹(shù)還是右子樹(shù)回到根結(jié)點(diǎn)都不應(yīng)該再操作了卖哎，應(yīng)該退回上層。 //3 如果是從右邊再返回根結(jié)點(diǎn)删性，應(yīng)該回到上層亏娜。 public static void postOrderIteration2(TreeNode head) { if (head == null) { return; } TreeNode cur = head; Stack<TreeNode> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty()) { TreeNode peek = stack.peek(); if (peek.left != null && peek.left != cur && peek.right != cur) { stack.push(peek.left); } else if (peek.right != null && peek.right != cur) { stack.push(peek.right); } else { System.out.print(stack.pop().val + " "); cur = peek; } } } -
Morris解法
Morris 遍歷使用二叉樹(shù)節(jié)點(diǎn)中大量指向 null 的指針，由 Joseph Morris 于 1979 年發(fā)明蹬挺。
時(shí)間復(fù)雜度：
額外空間復(fù)雜度：在你閱讀以下代碼之前维贺，在這邊先講解一下 Morris 的通用解法過(guò)程。
Morris 的整體思路就是將 以某個(gè)根結(jié)點(diǎn)開(kāi)始巴帮，找到它左子樹(shù)的最右側(cè)節(jié)點(diǎn)之后與這個(gè)根結(jié)點(diǎn)進(jìn)行連接
我們可以從 圖2 看到溯泣，如果這么連接之后，cur 這個(gè)指針是可以完整的從一個(gè)節(jié)點(diǎn)順著下一個(gè)節(jié)點(diǎn)遍歷榕茧，將整棵樹(shù)遍歷完畢垃沦，直到 7 這個(gè)節(jié)點(diǎn)右側(cè)沒(méi)有指向。
public static void preOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;//當(dāng)前開(kāi)始遍歷的節(jié)點(diǎn)
TreeNode cur2 = null;//記錄當(dāng)前結(jié)點(diǎn)的左子樹(shù)
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {//找到當(dāng)前左子樹(shù)的最右側(cè)節(jié)點(diǎn)用押，且這個(gè)節(jié)點(diǎn)應(yīng)該在指向根結(jié)點(diǎn)之前肢簿，否則整個(gè)節(jié)點(diǎn)又回到了根結(jié)點(diǎn)。
cur2 = cur2.right;
}
if (cur2.right == null) {//這個(gè)時(shí)候如果最右側(cè)這個(gè)節(jié)點(diǎn)的右指針沒(méi)有指向根結(jié)點(diǎn)蜻拨，創(chuàng)建連接然后往下一個(gè)左子樹(shù)的根結(jié)點(diǎn)進(jìn)行連接操作池充。
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {//當(dāng)左子樹(shù)的最右側(cè)節(jié)點(diǎn)有指向根結(jié)點(diǎn)，此時(shí)說(shuō)明我們已經(jīng)回到了根結(jié)點(diǎn)并重復(fù)了之前的操作缎讼，同時(shí)在回到根結(jié)點(diǎn)的時(shí)候我們應(yīng)該已經(jīng)處理完 左子樹(shù)的最右側(cè)節(jié)點(diǎn) 了收夸，把路斷開(kāi)。
cur2.right = null;
}
}
cur1 = cur1.right;//一直往右邊走血崭，參考圖
}
}
-
前序遍歷
- 在某個(gè)根結(jié)點(diǎn)創(chuàng)建連線的時(shí)候打印卧惜。因?yàn)槲覀兪琼樦筮叺母?jié)點(diǎn)來(lái)創(chuàng)建連線厘灼，且創(chuàng)建的過(guò)程只有一次。
- 打印某些自身無(wú)法創(chuàng)建連線的節(jié)點(diǎn)序苏，也就是葉子節(jié)點(diǎn)手幢。
public static void preOrderMorris(TreeNode head) { if (head == null) { return; } TreeNode cur1 = head; TreeNode cur2 = null; while (cur1 != null) { cur2 = cur1.left; if (cur2 != null) { while (cur2.right != null && cur2.right != cur1) { cur2 = cur2.right; } if (cur2.right == null) { cur2.right = cur1; System.out.print(cur1.value + " "); cur1 = cur1.left; continue; } else { cur2.right = null; } } else { System.out.print(cur1.value + " "); } cur1 = cur1.right; } } -
中序遍歷
從最左側(cè)開(kāi)始順著右節(jié)點(diǎn)打印。也就是在將
cu1切換到上層節(jié)點(diǎn)的時(shí)候忱详。public static void inOrderMorris(TreeNode head) { if (head == null) { return; } TreeNode cur1 = head; TreeNode cur2 = null; while (cur1 != null) { cur2 = cur1.left; //構(gòu)建連接線 if (cur2 != null) { while (cur2.right != null && cur2.right != cur1) { cur2 = cur2.right; } if (cur2.right == null) { cur2.right = cur1; cur1 = cur1.left; continue; } else { cur2.right = null; } } System.out.print(cur1.value + " "); cur1 = cur1.right; } } 后序遍歷
當(dāng)我們到達(dá)最左側(cè)围来，也就是左邊連線已經(jīng)創(chuàng)建完畢了。
打印 4
打印 5 2
打印 6
打印 7 3 1
我們將一個(gè)節(jié)點(diǎn)的連續(xù)右節(jié)點(diǎn)當(dāng)成一個(gè)單鏈表來(lái)看待匈睁。
當(dāng)我們返回上層之后监透，也就是將連線斷開(kāi)的時(shí)候，打印下層的單鏈表航唆。
比如返回到≌吐２，此時(shí)打印∨锤啤４
比如返回到》嗬恰１，此時(shí)打印∪伟丁５≡匍２
比如返回到 ３享潜，此時(shí)打印±浮６
那么我們只需要將這個(gè)單鏈表逆序打印就行了，下文也給出了 單鏈表逆序代碼
這里不應(yīng)該打印當(dāng)前層剑按，而是下一層疾就，否則根結(jié)點(diǎn)會(huì)先與右邊打印。
public static void postOrderMorris(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur1 = head;//遍歷樹(shù)的指針變量
TreeNode cur2 = null;//當(dāng)前子樹(shù)的最右節(jié)點(diǎn)
while (cur1 != null) {
cur2 = cur1.left;
if (cur2 != null) {
while (cur2.right != null && cur2.right != cur1) {
cur2 = cur2.right;
}
if (cur2.right == null) {
cur2.right = cur1;
cur1 = cur1.left;
continue;
} else {
cur2.right = null;
postMorrisPrint(cur1.left);
}
}
cur1 = cur1.right;
}
postMorrisPrint(head);
}
//打印函數(shù)
public static void postMorrisPrint(TreeNode head) {
TreeNode reverseList = postMorrisReverseList(head);
TreeNode cur = reverseList;
while (cur != null) {
System.out.print(cur.value + " ");
cur = cur.right;
}
postMorrisReverseList(reverseList);
}
//翻轉(zhuǎn)單鏈表
public static TreeNode postMorrisReverseList(TreeNode head) {
TreeNode cur = head;
TreeNode pre = null;
while (cur != null) {
TreeNode next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
return pre;
}
