date: 2016-08-18 9:17:00
title: 二叉樹面試題彙總(二)
categories: 資料結構
版權聲明：本站采用開放的[知識共享署名-非商業性使用-相同方式共享 許可協定]進行許可
所有文章出現的代碼，将會出現在我的github中，名字可以根據類全名來找，我在github中的檔案夾也會加目錄備注。
二叉樹的先序周遊
遞歸法
思路：
- 二叉樹的先序、中序、後序周遊使用遞歸法實作非常簡單，因為樹是由遞歸定義的。
- 不管使用遞歸還是非遞歸方法實作對于二叉樹的周遊，首先我們需要抓住周遊的關鍵，即對節點的通路順序。
- 使用不同的方法，對每個節點的通路順序不同。
- 先序周遊、中序周遊、後序周遊中，先、中、後是指根節點的通路順序，一般二叉樹分為“DLR”，其中D 代表根節點，L代表左子樹，R代表右子樹，先序為DLR,中序為LDR,後序為LRD
- 掌握了上面的要領，那麼實作對二叉樹的先中後序周遊就非常簡單了。
代碼實作:
public static void preOrderTraverseByRecursion(BinaryTree root) {
// 遞歸的出口
if (root == null)
return;
// 1、先通路根節點，在這裡隻是做簡單的資料輸出
System.out.print(root.getValue() + " ");
// 2、遞歸通路左子節點，因為左子節點可能還有子節點
preOrderTraverseByRecursion(root.getLeftChild());
// 3、遞歸通路右子節點，理由同上
preOrderTraverseByRecursion(root.getRightChild());
}
圖解：
測試代碼:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.preOrderTraverseByRecursion(n1);
}
}
樹結構：
運作結果
疊代法
思路：
- 要使用非遞歸法實作二叉樹的先序周遊，可以這樣想，既然可以用遞歸實作，那麼就可以用棧實作（為什麼？）。
- 即使使用非遞歸實作二叉樹的先序周遊，也要抓住各個節點的通路順序，在這裡，最先通路的是根節點，是以當有節點入棧時，它可以看成是其子節點的根節點，那麼可以直接輸出該節點的資料
- 然後再判斷目前節點有無左右子節點，這裡要注意棧的特點，先存右子樹，再存左子樹
- 如果還不能了解，可以通過自己随意畫一棵二叉樹，對着進棧出棧的順序來看代碼。或者自己根據先序周遊的順序來寫代碼也行，重要的是想法。
代碼實作：
/**
* 非遞歸法 周遊二叉樹
*
* @param root
*/
public static void preOrderTraverseByIterative(BinaryTree root) {
// 判斷目前節點是否為空，為空就空操作
if (root == null)
return;
// 定義一個棧來存儲節點，一個變量來記錄目前節點
Stack<BinaryTree> stack = new Stack<BinaryTree>();
BinaryTree currentNode = root;
stack.push(currentNode);
// 進入循環體，條件:棧不為空
while (!stack.isEmpty()) {
// 棧頂節點出棧并指派給目前節點
currentNode = stack.pop();
// 輸出根節點資料
System.out.print(currentNode.getValue() + "：");
// 判斷目前節點有無右子樹，有入棧
if (currentNode.getRightChild() != null)
stack.push(currentNode.getRightChild());
// 判斷目前節點有無左子樹，有入棧
if (currentNode.getLeftChild() != null)
stack.push(currentNode.getLeftChild());
}
}
樹結構：
運作結果：
二叉樹的中序周遊
遞歸法
思路:
- 抓住通路順序，中序周遊:LDR,代碼實作可以參照先序周遊。
- 首先得到根節點，但是中序周遊要先通路左子節點，是以先遞歸得到子節點，然後再通路根節點，最後通路右子節點
圖解：
代碼實作:
/**
* 使用遞歸中序周遊二叉樹
*
* @param root
*/
public static void inOrderTraverseByRecursion(BinaryTree root) {
// 遞歸出口
if (root == null)
return;
// 遞歸通路左子樹
inOrderTraverseByRecursion(root.getLeftChild());
// 通路根節點
System.out.print(root.getValue() + " ");
// 遞歸通路右子樹
inOrderTraverseByRecursion(root.getRightChild());
}
測試代碼:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.inOrderTraverseByRecursion(n1);
}
}
運作結果:
疊代
思路：
- 中序周遊，就先要得到左葉子節點，定義一個棧用來存儲左節點（同時也可能是根節點），一個變量來指向目前節點（開始是根節點）
- 得到左葉子節點後，通路該節點，在本文中，通路的意思是：該節點出棧，并輸出該節點的資料，
- 該節點出棧之後，意味着現在棧頂節點為剛剛出棧節點的根節點
- 把目前節點指向剛剛出棧節點的右子節點，到這裡再傳回上面的循環中，如果目前節點（此時指向了右子節點）為空，直接彈出棧頂節點（剛剛出棧節點的根節點），
圖解:
實作代碼:
public static void inOrderTraverseByIterative(BinaryTree root) {
// 首先判斷根節點是否為空，為空空操作
if (root == null)
return;
// 建立一個棧來存儲節點，建立一個節點來指向目前節點
Stack<BinaryTree> stack = new Stack<BinaryTree>();
BinaryTree currentNode = root;
// 定義一個循環,循環體為:
while (true) {
// 1、循環把左子節點的所有左節點加入棧，條件是目前節點不為空
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
// 2、當棧為空時跳出總循環,為什麼在這裡跳？不在外層直接定義條件？
// 因為剛剛開始棧為空，并且是在循環體内對棧進行壓棧操作
if (stack.isEmpty())
break;
// 3、通路節點
currentNode = stack.pop();
System.out.print(currentNode.getValue() + " ");
// 4、把目前節點指向剛剛彈棧的右子節點
currentNode = currentNode.getRightChild();
}
}
測試代碼：
情況一:根節點最後一個左子節點是葉子節點
樹結構：
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
// BinaryTree n7 = new BinaryTree(7);
// BinaryTree n8 = new BinaryTree(8);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
// n4.setRightChild(n7);
// n7.setLeftChild(n8);
BTreeTraverse.inOrderTraverseByIterative(n1);
}
}
運作結果：
情況二：左子樹最後一個左子節點不是葉子節點
樹的結構：
測試代碼:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
BinaryTree n7 = new BinaryTree(7);
BinaryTree n8 = new BinaryTree(8);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
n4.setRightChild(n7);
n7.setLeftChild(n8);
BTreeTraverse.inOrderTraverseByIterative(n1);
}
}
運作結果:
二叉樹的後序周遊
遞歸法
思路：
後續周遊節點通路順序： LRD，思路可以參考先序、中序周遊~
代碼實作：
public static void postOrderTraverseByRecursion(BinaryTree root) {
// 使用遞歸方法後序周遊二叉樹
// 遞歸出口
if (root == null)
return;
// 遞歸通路左子節點
postOrderTraverseByRecursion(root.getLeftChild());
// 遞歸通路右子節點
postOrderTraverseByRecursion(root.getRightChild());
// 通路根節點
System.out.print(root.getValue() + " ");
}
圖解:
測試代碼：
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.postOrderTraverseByRecursion(n1);
}
}
樹結構:
運作結果：
疊代法
思路：
- 後續周遊對節點的通路順序是LRD，就在我百思不得其解的時候，我看出了一些破綻
- 它就是先序周遊的倒序版，既然上面我們已經解決了先序周遊的疊代方法，那麼我們隻需要多弄一個棧，把裡面的節點倒過來，不就實作了後序周遊嗎? 夠給力嗎？
- 可能有些人會說，先序周遊是DLR啊，後序周遊是LRD，怎麼一樣？如果你有這樣的疑問，那我隻能說你不是真的懂先序周遊
- 先序周遊使用疊代方式實作的時候，不是要把輸出目前資訊的節點的左右子節點存到棧裡面嗎?隻需要調整左右節點進棧的順序即可！
圖解:
代碼實作：
// 使用非遞歸方式實作二叉樹的後序周遊
public static void postOrderTraverseByIterative(BinaryTree root) {
// 首先判斷傳進來的根節點是否為空，為空空操作
if (root == null)
return;
// 定義兩個棧，一個用來實作”DRL"的先序周遊，另外一個棧用來颠倒前面棧的順序
Stack<BinaryTree> stack = new Stack<BinaryTree>();
Stack<BinaryTree> outStack = new Stack<BinaryTree>();
BinaryTree currentNode = root;
stack.push(currentNode);
while (!stack.isEmpty()) {
// 既然要實作先序周遊，當然是先通路根節點，把先出棧的放到另外一個棧
currentNode = stack.pop();
outStack.push(currentNode);
// 再判斷左子節點，不為空入棧1
if (currentNode.getLeftChild() != null)
stack.push(currentNode.getLeftChild());
// 判斷右子節點，不為空，入棧1
if (currentNode.getRightChild() != null)
stack.push(currentNode.getRightChild());
}
// 輸出outStack棧中的節點
while (!outStack.isEmpty()) {
System.out.print(outStack.pop().getValue() + " ");
}
}
測試代碼:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.postOrderTraverseByIterative(n1);
}
}
樹結構：
運作結果:
層次查詢
非遞歸方式
思路：
- 按層次周遊，講的也是節點通路的順序。
- 這時候使用棧就不合适了，應該使用隊列，先通路到的可以先輸出
- 先把根節點入隊， 當隊列不為空的時候，隊頭節點出隊，再判斷目前出隊節點是否有左右子節點，有就入隊
代碼實作：
// 非遞歸方式實作層次周遊
public static void levelTraverseByIterative(BinaryTree root) {
if (root == null)
return;
// 定義一個隊列來實作
Queue<BinaryTree> queue = new LinkedList<BinaryTree>();
// 首先把根節點入隊
queue.add(root);
BinaryTree currentNode = root;
while (!queue.isEmpty()) {
// 入隊再出隊
currentNode = queue.remove();
System.out.print(currentNode.getValue() + " ");
// 然後把左右子節點入隊
if (currentNode.getLeftChild() != null)
queue.add(currentNode.getLeftChild());
if (currentNode.getRightChild() != null)
queue.add(currentNode.getRightChild());
}
}
圖解:
測試代碼:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.levelTraverseByIterative(n1);
}
}
樹結構:
運作結果:
改進
在上面的運作結果中我們可以看到，雖然是按分層形式通路的，可是結果并沒有顯示哪些節點屬于哪一層，很容易讓人覺得好像這些節點都是屬于同一層節點，那麼怎樣實作讓函數在算完一層之後輸出一個換行呢?
思路：
- 可以借助前面求樹深度疊代方法實作的思路，在這裡定義兩個變量，一個用來記住目前層次的節點數，另外一個用來記錄下一層的節點數
- 當記錄目前層節點數為0時，輸出換行，并且在每次把節點出隊和入隊，都對這兩個變量進行修改，這樣就可以實作分層輸出！
代碼實作：
// 非遞歸方式實作層次周遊
public static void levelTraverseByIterative(BinaryTree root) {
if (root == null)
return;
// 定義一個隊列來實作
Queue<BinaryTree> queue = new LinkedList<BinaryTree>();
// 新定義的兩個變量！大家可以通過名字來了解其作用
int currentLevelNodes = 1, nextLevelNodes = 0;
// 首先把根節點入隊
queue.add(root);
BinaryTree currentNode = root;
while (!queue.isEmpty()) {
// 入隊再出隊
currentNode = queue.remove();
// 在出隊時，對目前層節點數進行修改！
currentLevelNodes--;
System.out.print(currentNode.getValue() + " ");
// 然後把左右子節點入隊
if (currentNode.getLeftChild() != null) {
queue.add(currentNode.getLeftChild());
// 在入隊時，對下一層節點數進行修改！
nextLevelNodes++;
}
if (currentNode.getRightChild() != null) {
queue.add(currentNode.getRightChild());
// 在入隊時，對下一層節點數進行修改！
nextLevelNodes++;
}
// 目前層節點數為0時，輸出換行，并且把“這一行移到下一行”
// 其實就是把下一行的節點數指派給目前行節點數
if (currentLevelNodes == 0) {
System.out.println();
currentLevelNodes = nextLevelNodes;
}
}
}
測試代碼還是一樣，即樹結構一樣。
運作結果：
遞歸
思路：
- 向要分層的周遊二叉樹，首先想能不能用什麼容器把節點”分層“存儲？
- 定義一個二維數組，每一層存放每一層的節點，最後周遊數組即可得到每一層的節點
- 對于每一個傳進來的節點，首先判斷其是否為空，為空空操作
- 不為空根據上一次的操作結果，加上目前節點，存入指定的層數
圖解:
實作代碼:
// 遞歸方式實作層次周遊
public static void levelTraverseByRecursion(BinaryTree root) {
// 判斷根節點是否為空，為空空操作
if (root == null)
return;
// 定義一個雙層連結清單
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
// 使用bfs
recursion(root, 0, list);
// 輸對外連結表
System.out.println(list);
}
/**
* 按層次遞歸周遊二叉樹
*
* @param root
* 目前節點
* @param level
* 層數
* @param list
* 要存儲到的容器
*/
private static void recursion(BinaryTree root, int level,
ArrayList<ArrayList<Integer>> list) {
// 目前節點為空，空操作
if (root == null)
return;
// 若目前的層數大于等于連結清單的“層數”，那麼為連結清單“加層”
if (level >= list.size()) {
list.add(new ArrayList<Integer>());
}
// 把目前節點存到指定層數中
list.get(level).add(root.getValue());
// 遞歸把左子節點對應的樹存傳入連結表
recursion(root.getLeftChild(), level + 1, list);
// 遞歸把右子節點對應的樹存傳入連結表
recursion(root.getRightChild(), level + 1, list);
}
測試代碼:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.levelTraverseByRecursion(n1);
}
}
樹結構:
運作結果
【全文完】
參考資料：
Pre-Order Traversal of Binary Tree (Iterative)
Inorder Binary Tree Traversal (Iteratively)
Print a Binary Tree in Post Order Traversal (Iterative using Stack)
二叉樹後序周遊的非遞歸實作
二叉樹前序、中序、後序周遊非遞歸寫法的透徹解析
資料結構（C語言版）（第2版）-5.3.1周遊二叉樹
郝斌資料結構-第67-72個視訊，提取密碼:hvzr