961全部内容連結
文章目錄
- 二叉樹及其性質
-
- 二叉樹的定義
- 幾種特殊的二叉樹
- 二叉樹的性質
-
- 完全二叉樹的性質
- 二叉樹的Java定義
- 二叉樹的周遊
-
- 二叉樹的前序周遊（遞歸）
- 二叉樹的前序周遊（非遞歸）
- 二叉樹的中序周遊（遞歸）
- 二叉樹的中序周遊（非遞歸）
- 二叉樹的後序周遊（遞歸）
- 二叉樹的後序周遊（非遞歸）
- 二叉樹的層序周遊
- 普通樹與二叉樹的轉換
-
- 普通樹轉二叉樹方法
- 普通樹轉二叉樹（遞歸）
- 普通樹轉二叉樹（非遞歸）
- 二叉樹轉普通樹（遞歸）
- 二叉樹轉普通樹（非遞歸）
二叉樹及其性質
二叉樹的定義
- 二叉樹的定義：每個節點至多有兩棵子樹，即二叉樹中不存在度大于2的節點
- 二叉樹是有序樹，即左右子樹不能颠倒
幾種特殊的二叉樹
- 滿二叉樹：一棵高度為 2h-1 個節點的二叉樹，稱為滿二叉樹。就是說，除了最後一層，其他層的節點的度必須都為2。說白了就是把二叉樹畫滿。
複旦大學961-資料結構-第二章-樹（2）-二叉樹的周遊，普通樹與二叉樹的轉換二叉樹及其性質二叉樹的周遊普通樹與二叉樹的轉換 - 完全二叉樹：相對于滿二叉樹而言，沒那麼滿，少了幾個節點（隻能最後幾個節點少）的二叉樹，為完全二叉樹。
複旦大學961-資料結構-第二章-樹（2）-二叉樹的周遊，普通樹與二叉樹的轉換二叉樹及其性質二叉樹的周遊普通樹與二叉樹的轉換 - 二叉排序樹：左子樹的所有節點的關鍵字均小于根節點關鍵字，右子樹的所有關鍵字均大于根節點關鍵字。且左右子樹也是二叉排序樹。
複旦大學961-資料結構-第二章-樹（2）-二叉樹的周遊，普通樹與二叉樹的轉換二叉樹及其性質二叉樹的周遊普通樹與二叉樹的轉換 - 平衡二叉樹：樹上任意一個節點的左右子樹的深度之差不大于1
二叉樹的性質
1. 非 空 二 叉 樹 上 的 葉 子 結 點 數 等 于 度 為 2 的 結 點 數 加 1 ， 即 n 0 = n 2 + 1 2. 非 空 二 叉 樹 上 第 k 層 上 至 多 有 2 k − 1 個 節 點 ( k ≥ 1 ) 3. 高 度 為 h 的 二 叉 樹 至 多 有 2 h − 1 個 結 點 \begin{aligned} & 1. 非空二叉樹上的葉子結點數等于度為2的結點數加1，即 n_0 = n_2+1 \\ & 2. 非空二叉樹上第k層上至多有 2^{k-1}個節點 (k\ge 1) \\ & 3. 高度為h的二叉樹至多有 2^h -1 個結點 \\ \end{aligned} 1.非空二叉樹上的葉子結點數等于度為2的結點數加1，即n0=n2+12.非空二叉樹上第k層上至多有2k−1個節點(k≥1)3.高度為h的二叉樹至多有2h−1個結點
完全二叉樹的性質
對完全二叉樹，從上到下，從左到右的順序依次編号 1,2,…n，則有以下關系：
1. 當 i > 1 時 ， 其 雙 親 的 編 号 為 ⌊ i / n ⌋ 2. 當 i 為 偶 數 時 ， 為 左 孩 子 ， 當 i 為 奇 數 時 ， 為 右 孩 子 3. 當 i ≤ ⌊ n / 2 ⌋ ， 則 節 點 i 為 分 支 節 點 ， 否 則 為 葉 子 結 點 4. 高 度 為 ⌊ log 2 n ⌋ + 1 \begin{aligned} & 1. 當i>1時，其雙親的編号為 ~ \lfloor i/n \rfloor \\ & 2. 當i為偶數時，為左孩子，當i為奇數時，為右孩子 \\ & 3. 當 i \le \lfloor n/2 \rfloor ，則節點i為分支節點，否則為葉子結點 \\ & 4. 高度為 \lfloor \log_2n\rfloor +1 \end{aligned} 1.當i>1時，其雙親的編号為 ⌊i/n⌋2.當i為偶數時，為左孩子，當i為奇數時，為右孩子3.當i≤⌊n/2⌋，則節點i為分支節點，否則為葉子結點4.高度為⌊log2n⌋+1
二叉樹的Java定義
class BinaryNode<AnyType> {
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
public BinaryNode(AnyType x) {
this.element = x;
}
}
二叉樹的周遊
二叉樹的前序周遊（遞歸）
public static void preOrder(BinaryNode root) {
if (root == null) return;
System.out.print(root.element + " "); // 輸出根節點
preOrder(root.left); // 通路左節點
preOrder(root.right); // 通路右節點
}
二叉樹的前序周遊（非遞歸）
public static void preOrder(BinaryNode root) {
Stack stack = new Stack(); // 初始化棧
BinaryNode node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
System.out.print(node.element + " "); // 輸出根節點
stack.add(node); // 根節點入棧
node = node.left; // 通路根節點左子樹
} else {
BinaryNode temp = (BinaryNode)stack.pop(); //左子樹為空，其父節點出棧（擷取該父節點）
node = temp.right; // 通路其右節點
}
}
}
基本思路：
- 初始化棧，用于存放結點指針。
- 通路根節點，若根節點不為空，則輸出根節點内容，然後将根節點入棧，然後對其左子樹做同樣操作
- 第2步一直循環，直到左子樹為空，然後從棧頂彈出一個節點，然後對其右子樹重複2步驟，直到最後棧為也空
易錯點：
- while循環時，node!=null 的條件一定要加，否則，通路右節點後的下一輪循環時，棧有可能是空的，若沒有 node!=null 的條件，則會無法通路右子樹
- 根節點可以在外部通路後入棧，也可以和上面代碼一樣不通路，等到到循環中也會對其通路
- 節點出棧後不能對其通路，因為在入棧之前就已經通路過了
- 棧頂出站後，别忘了強制類型轉換
二叉樹的中序周遊（遞歸）
public static void inOrder(BinaryNode root) {
if (root == null) return;
inOrder(root.left); // 通路左節點
System.out.print(root.element + " "); // 輸出根節點
inOrder(root.right); // 通路右節點
}
二叉樹的中序周遊（非遞歸）
public static void inOrder(BinaryNode root) {
Stack stack = new Stack(); //初始化棧
BinaryNode node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
stack.push(node); // 根節點入棧
node = node.left; // 通路左節點
} else {
BinaryNode tempNode = (BinaryNode) stack.pop(); // 當該節點為空時，彈出該節點的父節點（即該節點的父節點沒有左孩子）
System.out.print(tempNode.element + " "); // 輸出該節點的父節點
node = tempNode.right; // 通路其右節點
}
}
}
基本思路：
- 初始化棧，用于存放結點指針
- 從根節點開始，若根節點存在，則入棧，然後對其左子樹做同樣步驟
- 若發現左子樹為空，則從棧中彈出一個節點，輸出，然後對其右子樹重複2步驟，直到棧為空
二叉樹的後序周遊（遞歸）
public static void postOrder(BinaryNode root) {
if (root == null) return;
postOrder(root.left); // 通路左節點
postOrder(root.right); // 通路右節點
System.out.print(root.element + " "); // 輸出根節點
}
二叉樹的後序周遊（非遞歸）
/**
* 1. 從根節點開始，依次往下周遊左孩子，并入棧
* 2. 若左孩子為空，通路棧頂，判斷棧頂的右孩子是否為空，若不為空，且沒有被通路過，則重複1.
* 3. 若右孩子為空，或被通路過，則棧頂出棧并輸出。
*/
public static void postOrder(BinaryNode root) {
Stack stack = new Stack(); // 初始化棧
BinaryNode node = root;
BinaryNode rightNode = null; // 用于判斷右節點是否被周遊過
while (node != null || stack.size() > 0) {
if (node != null) { // 節點不為空，入棧，并通路其左孩子
stack.add(node);
node = node.left;
} else {
BinaryNode topNode = (BinaryNode) stack.peek(); // 讀棧頂元素
if (topNode.right != null && topNode.right != rightNode) { // 棧頂的右孩子不為空且沒有被通路過
node = topNode.right; // 通路棧頂右孩子，并入棧
stack.add(node);
node = node.left; // 重複1，通路棧頂右孩子的左孩子
} else {
stack.pop(); // 棧頂的右孩子為空，或被通路過，則棧頂出棧，并輸出
System.out.print(topNode.element + " ");
rightNode = topNode; // 記錄目前節點，以便于棧頂元素判斷右孩子是否被通路過
node = null; // 每次出棧通路完一個節點，就相當于周遊完以該節點為根的子樹，需将node重置為null，這樣下一輪，就會認為左子樹為空，然後去判斷右子樹去了，否則，左孩子就會不斷地入棧出棧，陷入死循環。
}
}
}
}
基本思路：
- 從根節點開始，依次往下周遊左孩子，并入棧
- 若左孩子為空，通路棧頂，判斷棧頂的右孩子是否為空，若不為空，且沒有被通路過，則對右孩子重複1.
- 若右孩子為空，或被通路過，則棧頂出棧并輸出。
易錯點：
- 初始化時，要初始化一個節點變量，用于存放上次被通路的右孩子指針。用于判斷是否右孩子被通路過
- 每次通路（輸出）完節點後，需要将目前的node變量置空，以便可以再對上面的結點出棧，否則就在卡在“輸出目前節點，然後下一輪，目前節點不為空，入棧，通路左子樹，左子樹為空，且右子樹通路過了，棧頂出棧，輸出目前節點，然後無限循環下去”。
while中的判斷思路，這個到考場容易想不起來，容易亂：
- 節點是否為空，若不為空，則入棧，然後通路其左節點
-
若節點為空，然後再分情況讨論
2.1 棧頂節點（相當于該空節點的父節點）的右子樹不為空，且沒有被通路過，則通路其右子樹，然後再通路其右子樹的左子樹，結束進入下一輪循環
2.2 若棧頂節點右子樹為空，則出棧，輸出棧頂節點，然後記錄最近通路過的節點（rightNode），将node置空，結束進入下一輪循環。
二叉樹的層序周遊
public static void levelOrder(BinaryNode root) {
if (root == null) return;
Queue q = new ArrayDeque(); // 初始化隊列
q.add(root); // 根節點入隊
while (q.size() > 0) {
BinaryNode tempNode = (BinaryNode) q.poll(); // 如果隊列不為空，出隊并輸出
System.out.print(tempNode.element+ " ");
if (tempNode.left != null) q.add(tempNode.left); // 将該節點的左孩子和右孩子依次入隊
if (tempNode.right != null) q.add(tempNode.right);
}
}
普通樹與二叉樹的轉換
普通樹Java定義
public class TreeNode<AnyType> {
AnyType element;
TreeNode<AnyType> firstChild;
TreeNode<AnyType> nextSibling; // sibling: 兄弟姐妹
public TreeNode (AnyType x) {
this.element = x;
}
}
普通樹轉二叉樹方法
- 在兄弟節點之間加一連線。
- 對每個節點，隻保留它與第一個孩子的連線，而與其他孩子的連線全部抹掉
- 以樹根為軸心，順時針旋轉45°
二叉樹轉普通樹反過來即可
普通樹轉二叉樹（遞歸）
private static void transferToBinaryTree(TreeNode treeNode, BinaryNode binaryNode) {
if (treeNode.firstChild != null) {
binaryNode.left = new BinaryNode(treeNode.firstChild.element);
transferToBinaryTree(treeNode.firstChild, binaryNode.left);
}
if (treeNode.nextSibling != null) {
binaryNode.right = new BinaryNode(treeNode.nextSibling.element);
transferToBinaryTree(treeNode.nextSibling, binaryNode.right);
}
}
/**
* 1. 首先構造根節點。然後開始遞歸
* 2. 判斷firstChild是否為空，若不為空，則連結到二叉樹的左孩子，遞歸進入下一層firstChild，否則到3
* 3. 判斷nextSibling（右兄弟）是否為空，若不為空，則連結到二叉樹的右孩子，遞歸進入下一層nextSibling，否則退出到上層遞歸。
*/
public static BinaryNode transferToBinaryTree(TreeNode treeRoot) {
if (treeRoot == null) return null;
BinaryNode binaryRoot = new BinaryNode(treeRoot.element);
transferToBinaryTree(treeRoot, binaryRoot);
return binaryRoot;
}
普通樹轉二叉樹（非遞歸）
todo ，應該不考，有時間再弄
二叉樹轉普通樹（遞歸）
private static void transferToTree(BinaryNode binaryNode, TreeNode treeNode) {
if (binaryNode.left != null) {
treeNode.firstChild = new TreeNode(binaryNode.left.element);
transferToTree(binaryNode.left, treeNode.firstChild);
}
if (binaryNode.right != null) {
treeNode.nextSibling = new TreeNode(binaryNode.right.element);
transferToTree(binaryNode.right, treeNode.nextSibling);
}
}
/**
* 1. 構造普通樹的根節點，然後開始遞歸
* 2. 判斷是否有左孩子，若有左孩子，則連結到tree的左節點，然後遞歸進入下一層，否則進入3
* 3. 判斷是否有右孩子，若有右孩子，則連結到tree的nextSibling（右兄弟），然後遞歸下一層。
*/
public static TreeNode transferToTree(BinaryNode root) {
if (root == null) return null;
TreeNode treeNode = new TreeNode(root.element);
transferToTree(root, treeNode);
return treeNode;
}
二叉樹轉普通樹（非遞歸）
todo，應該不考，有時間弄