- 二叉樹
-
- 一 . 概念
- 二 . 二叉樹的性質
- 三 . 常見的二叉樹
-
- 3.1 滿二叉樹
- 3.2 完全二叉樹
- 3.3 二分搜尋樹(BST)
- 3.4 其他常見的二叉樹
- 四 . 二叉樹的周遊
-
- 4.1. 前序周遊(先序周遊)
- 4.2 二叉樹的中序周遊
- 4.3 二叉樹的後序周遊
- 4.4 二叉樹的層序周遊
二叉樹
一 . 概念
一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵别稱為左子樹和右子樹的二叉 樹組成。
二叉樹的特點：
- 每個節點最多有兩棵子樹，即二叉樹不存在度大于 2 的結點。
- 二叉樹的子樹有左右之分，其子樹的次序不能颠倒，是以二叉樹是有序樹。
二 . 二叉樹的性質
- 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 (i>0)個結點
- 若規定隻有根節點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是 (k>=0)
- 對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉節點個數為 n2,則有n0＝n2＋1
- 具有n個節點的完全二叉樹的深度k為 上取整
對于具有n個節點的完全二叉樹，如果按照從上至下從左至右的順序對所有節點從0開始編号，則對于序号為i 的結點有：
(1) 若i>0，雙親序号：(i-1)/2；i=0，i為根節點編号，無雙親節點
(2)若2i+1<n，左孩子序号：2i+1，否則無左孩子
(3)若2i+2<n，右孩子序号：2i+2，否則無右孩子
三 . 常見的二叉樹
3.1 滿二叉樹
滿二叉樹：每一層的節點個數都是最大值，每一層節點個數都是滿的。
資料結構--二叉樹的概念及周遊方法二叉樹
3.2 完全二叉樹
完全二叉樹 ：完全二叉樹的節點編号和滿二叉樹完全一緻 ----堆-優先級隊列
1.完全二叉樹除了最深的一層，其他層的節點全部是滿的
2.最後一層的節點都是靠左排列的
資料結構--二叉樹的概念及周遊方法二叉樹 資料結構--二叉樹的概念及周遊方法二叉樹
3.3 二分搜尋樹(BST)
二分搜尋樹(BST) ：節點的值之間有一個大小關系
左子樹節點值 < 根節點值 < 右子樹節點值
二分搜尋樹的中序周遊就是一個遞增的數組
在二分搜尋樹中查找一個元素，就是二分查找
3.4 其他常見的二叉樹
平衡二叉樹：該樹中任意一個節點的左右子樹高度差 <= 1
AVL -> 嚴格平衡的BST
RBTree -> “黑節點”嚴格平衡的BST
四 . 二叉樹的周遊
所謂周遊(Traversal)是指沿着某條搜尋路線，依次對樹中每個節點均做一次且僅做一次通路。通路節點所做的操作依賴于具體的應用問題(比如：列印節點内容、節點内容加1)。
周遊是二叉樹上最重要的操作之一，是二叉樹上進行其它運算之基礎，一般有以下幾種周遊方式：
1.前序周遊(Preorder Traversal 亦稱先序周遊)——通路根結點—>根的左子樹—>根的右子樹。
2.中序周遊(Inorder Traversal)——根的左子樹—>根節點—>根的右子樹。
3.後序周遊(Postorder Traversal)——根的左子樹—>根的右子樹—>根節點。
4.層序周遊(Level Traversal)——第一層從左到右周遊—>第二層從左到右周遊—>第三層從左到右周遊…
4.1. 前序周遊(先序周遊)
所謂的二叉樹的先序周遊，就是“根左右”的周遊方式，即先輸出根節點再一路向左子樹周遊，每通路到一個根節點就輸出一個值，最後再通路并輸出右子樹的節點。
如上圖，先通路根節點，再遞歸通路左子樹，最後遞歸通路右子樹
代碼實作如下：
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"");
preOrder(root.left);//輸出左孩子
preOrder(root.right);//輸出右孩子
}
疊代寫法為：
public List perorderTraversal(TreeNode root){
List ret = new ArrayList<>();
if(root == null){
return null;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode cur = stack.pop();
ret.add(cur.val);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
return ret;
}
4.2 二叉樹的中序周遊
二叉樹的中序周遊：就是先遞歸通路左子樹，再通路根節點，最後通路右子樹
代碼實作為：
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val +"");
inOrder(root.right);
}
疊代寫法：
public List inorderTravesal(TreeNode root){
List ret = new ArrayList<>();
if(root == null){
return null;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//此時向左走到底
cur = stack.pop();
ret.add(cur.val);
cur = cur.right;
}
return ret;
}
4.3 二叉樹的後序周遊
二叉樹的後序周遊：先遞歸通路左子樹，再遞歸通路右子樹，最後通路根節點
代碼實作為：
public void postOrder(TreeNode root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val +"");
}
疊代寫法：
public List postorderTravesal(TreeNode root){
List ret = new ArrayList<>();
if(root == null){
return null;
}
TreeNode prev = null;
TreeNode cur = root;
Deque<TreeNode> stack = new LinkedList<>();
while (cur != null || !stack.isEmpty()){
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//此時已經從左走到底
cur = stack.pop();
if(cur.right == null || cur.right == prev){
ret.add(cur.val);
prev = cur;
cur = null;
}else{
//此時cur.right != null || cur.right != prev
//右子樹沒處理
stack.push(cur);
cur = cur.right;
}
}
return ret;
}
4.4 二叉樹的層序周遊
二叉樹的層序周遊：從第一層開始逐層從左到右周遊節點
代碼實作：
public void levelOrder(TreeNode root){
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
System.out.print(node.val +"");
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
}
}