二叉樹
- 1. 二叉樹
- 1.1 二叉樹的介紹
- 1.2 兩種特殊的二叉樹
- 1.3 二叉樹的性質
- 1.4 二叉樹的存儲
- 2. 二叉樹的基本操作
- 2.1 二叉樹的創建
- 2.2 二叉樹的優先遍歷
- 2.3 遞歸實現二叉樹遍歷
- 2.4 用非遞歸實現二叉樹遍歷
1. 二叉樹
1.1 二叉樹的介紹
二叉樹是一種數據結構，一顆二叉樹是節點的集合，即每個節點最多有兩個子節點，分別為左子節點和右子節點。二叉樹可以為空，或者是由一個根節點 和兩個指向左子樹和右子樹的指針。
1.2 兩種特殊的二叉樹
- 滿二叉樹：每層的節點數都達到最大值，則該二叉樹就是滿二叉樹 ，即如果一顆二叉樹的層數為K，且節點總數是2^k - 1，則它是滿二叉樹。
- 完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從0至n-1的結點一一對應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
1.3 二叉樹的性質
- 若規定根結點的層數為1，則一棵非空二叉樹的第i層上最多有2^i -1（i>0）個結點；
- 若規定只有根結點的二叉樹的深度為1，則深度為k的二叉樹的最大結點數是2^k -1(k>=0)；
- 對任何一顆二叉樹，如果葉結點個數為n0，度為2的非葉子結點個數為n2，則有n0 = n2+1；
- 具有n個結點的完全二叉樹，如果按照從上至下，從左至右的順序對所有結點從0開始編號，則對于序號為i的結點有：
- ** 若i>0，雙親序號：(i-2)/2；i = 0，i為根結點編號**，無雙親結點
- 若2i+1<n,左孩子序號：2i+1,否則無左孩子
- 若2i+2<n,右孩子序號：2i+2，否則無右孩子
1.4 二叉樹的存儲
二叉樹的存儲結構分為：順序存儲（即堆）和類似于鏈表的鏈式存儲。
二叉樹的鏈式存儲是通過一個一個的節點引用起來的，常見的表示方式有二叉和三叉表示方式（一般用孩子表示法）：
// 孩子表示法
class Node {int val; // 數據域Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
}
// 孩子雙親表示法
class Node {int val; // 數據域Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹Node parent; // 當前節點的根節點
}
2. 二叉樹的基本操作
2.1 二叉樹的創建
創建一個如下的二叉樹
public class BinaryTree {static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}//public TreeNode root;//創建二叉樹 創建成功后 返回根節點public TreeNode createTree() {TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;}
}
2.2 二叉樹的優先遍歷
二叉樹的優先遍歷是指按照一定順序訪問二叉樹中的所有節點。常見的三種優先遍歷方式包括：前序遍歷、中序遍歷和后序遍歷。可以使用遞歸實現、非遞歸實現這三種遍歷方式。
- NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點—>根的左子樹—>根的右子樹，即根-左-右。
- LNR：中序遍歷(Inorder Traversal)——根的左子樹—>根節點—>根的右子樹，即左-根-右。
- LRN：后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節點，即左-右-根。
2.3 遞歸實現二叉樹遍歷
- 前序遍歷：上圖該二叉樹的前序遍歷為：A B D E H C F G
思路：在遞歸之前先打印當前根結點的值，然后向左子樹遞出，每一次都需要對當前結點的值訪問，直到node為null時，左子樹結束遞出。當右子樹此時也為node==null，從葉子結點開始回歸，回歸到上一個結點的右子樹。
void preOrder(TreeNode root) {if (root == null) {return;}System.out.print(root.val+"");preOrder(root.left);preOrder(root.right);}
- 中序遍歷：D B E H A F C G
思路：向左子樹遞出，一直下去，直到node 為null 時，左子樹結束遞出。再來對當前節點的值進行訪問，接著繼續向著右子樹遞出，當右子樹此時也為 node == null 時，從葉子節點開始回歸，回歸到上一個節點的右子樹前先對當前節點的值進行訪問。
// 中序 ： 左 根 右void inOrder(TreeNode root) {if (root == null) {return;}inOrder(root.left);System.out.print(root.val+"");inOrder(root.right);}
- 后序遍歷：D H E B F G C A
向左子樹遞出，一直下去，直到 node 為 null 時，左子樹結束遞出。再接著繼續向著右子樹遞出，再來對當前節點的值進行訪問，當右子樹此時也為 node 為 null 時，從葉子節點開始回歸，回歸到對當前節點的值進行訪問
// 后序 ： 左 右 根void postOrder(TreeNode root) {if (root == null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+"");}
2.4 用非遞歸實現二叉樹遍歷
- 非遞歸前序遍歷：
思路：
void preOrderNor(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val+" ");cur = cur.left;}TreeNode top = stack.pop();cur = top.right;}}
- 非遞歸中序遍歷：
void inOrderNor(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while(cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.pop();System.out.print(top.val + " ");cur = top.right;}}
- 非遞歸后序遍歷：
void postOrderNor(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while (cur != null || !stack.isEmpty()) {while(cur != null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if (top.right == null || top.right == prev) {System.out.print(top.val + " ");stack.pop();prev = top; //記錄下最新被打印的那個節點}else {cur = top.right;}}}
)
)
