二叉樹基礎
二叉樹是一種常見的數據結構，由節點組成，每個節點最多有兩個子節點，左子節點和右子節點。二叉樹可以用來表示許多實際問題，如計算機程序中的表達式、組織結構等。以下是一些二叉樹的概念：
- 二叉樹的深度：從根節點到葉子節點的最長路徑的長度稱為二叉樹的深度，也稱為高度。
- 二叉樹的度：一個節點擁有的子節點數量稱為該節點的度。二叉樹的度為2，即每個節點最多只有兩個子節點。
- 二叉樹的遍歷：二叉樹的遍歷是指按照一定順序訪問樹中的所有節點。常用的遍歷方式有前序遍歷、中序遍歷和后序遍歷。
- 二叉查找樹：二叉查找樹是一種特殊的二叉樹，它的左子樹中所有節點的值都小于根節點的值，而右子樹中所有節點的值都大于根節點的值。
二叉樹的定義：
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(nullptr),right(nullptr) {}}
- 二叉樹的基本操作：包括二叉樹的創建、遍歷、搜索等。
- 二叉查找樹的實現及應用：包括二叉查找樹的創建、插入、刪除、查找等操作。
- 平衡二叉樹：為了解決二叉查找樹在某些情況下退化為鏈表的問題，出現了平衡二叉樹，如 AVL 樹和紅黑樹等。
- 線段樹：線段樹是一種特殊的二叉樹，用于解決區間查詢的問題，如區間最大值、區間和等。
- 樹狀數組：樹狀數組也是一種特殊的二叉樹，用于解決前綴和、區間和等問題。
1基礎介紹
1.基礎術語
結點的度：結點的字數個數，比如二叉樹的度為2（一個節點最多有2個字數個數）。
樹的度：數的所有結點中最大的度數。
葉結點：度為0的結點。
父結點，子結點，兄弟結點（具有同一個父結點的各結點）。
路徑和路徑的長度：從結點n1到nk,路徑所包含的邊的個數為路徑的長度。
祖先結點，子孫結點。
結點的層次：規定根結點在1層，然后后面的結點層次都依次加一。
樹的深度：樹中國所有結點的最大層次是這棵樹的深度。
二叉樹T：一個有窮的結點集合，二叉樹的子樹有左右順序之分。
2.二叉樹的定義
二叉樹T：一個有窮的結點集合，二叉樹的子樹有左右順序之分
特殊的二叉樹：斜二叉樹，滿二叉樹，完全二叉樹（連續結點）
3.二叉樹的性質
①個二叉樹第i層的最大結點數為: 2^(i-1),（i≥1）
②深度為k的二叉樹有最大結點總數為:(2^k)-1, k≥1。(1+2 ^1+2 ^2 …2 ^i )
③0對任何非空二叉樹T，若n0表示葉結點的個數、n2是度為2的非葉結點個數，那么兩者滿足關系n0=n2 +1。
（n0+n1+n2-1） = 0n0+n1+2n2
4.二叉樹的遍歷
根據遍歷結點的順序，分為前序遍歷（NLR）,中序遍歷（LNR）,后續遍歷（LRN）。樹的遍歷復雜度為o(n)。
所以看樹的前序數組第一個是根結點，后續遍歷數組最后一個是根結點，再把該根結點拿到中序遍歷數組中去比對就可以劃分左右子樹。
4.1 前序遍歷
如果二叉樹為空，什么都不做，否則：
1）訪問根節點；
2）先序遍歷左子樹
3）先序遍歷右子樹*/
void PreOrder(BiTree T){if(T!= null){vist(T);//訪問根結點NPreOrder(T->lchild);//訪問左子樹L 遞歸PreOrder(T->rchild);//訪問右子樹R}
}
4.2 中序遍歷
/*inorder:
如果二叉樹為空，什么都不做，否則：
1）中遍歷左子樹
2）訪問根節點；
3）中序遍歷右子樹*/
void InOrder(BiTree T){if(T!= null){InOrder(T->lchild);//訪問左子樹L 遞歸vist(T);//訪問根結點NInOrder(T->rchild);//訪問右子樹R}
}
4.3 后序遍歷
/*Postorder:
如果二叉樹為空，什么都不做，否則：
1）后序遍歷左子樹
2）后序遍歷右子樹
3）訪問根節點；*/void PostOrder(BiTree T){if(T!= null){PostOrder(T->lchild);//訪問左子樹L 遞歸PostOrder(T->rchild);//訪問右子樹Rvist(T);//訪問根結點N}
}
4.4層序遍歷
2.遍歷基礎
1.DFS（Depth First Search）:遞歸法得到最終的數組（深度優先算法）
其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，如果遇到死路就往回退，回退過程中如果遇到沒探索過的支路，就進入該支路繼續深入，每個節點只能訪問一次。
深度優先搜索應用：先序遍歷，中序遍歷，后序遍歷。二叉樹的前序、中序、后序遍歷，本質上可以認為是深度優先遍歷。是一種回溯思想。
2.BFS（Breadth First Search）:迭代法實現層序遍歷，每次遍歷二叉樹的某一層。
它并不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。基本過程，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則算法中止。一般用隊列數據結構來輔助實現算法。
廣度優先搜索應用：層序遍歷、最短路徑、求二叉樹的最大高度、由點到面遍歷圖、拓撲排序
在我們解題過程中二叉樹有兩種主要的形式：滿二叉樹和完全二叉樹。
二叉樹分類
滿二叉樹
如果一棵二叉樹只有度為0的結點和度為2的結點，并且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。
如圖所示：
這棵二叉樹為滿二叉樹，也可以說深度為k，有2^k-1個節點的二叉樹。
完全二叉樹
在完全二叉樹中，除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第 h 層（h從1開始），則該層包含 1~ 2^(h-1) 個節點。（連續）
平衡二叉搜索樹
平衡二叉搜索樹：又被稱為AVL（Adelson-Velsky and Landis）樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
如圖：
最后一棵 不是平衡二叉樹，因為它的左右兩個子樹的高度差的絕對值超過了1。
二叉搜索樹
前面介紹的樹，都不用管數值的，而二叉搜索樹是要參考數值的，二叉搜索樹是一個有序樹。
若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
它的左、右子樹也分別為二叉排序樹
下面這兩棵樹都是搜索樹：
二叉搜索樹中序遍歷是從小到大的有序數組。
C++中map、set、multimap，multiset的底層實現都是平衡二叉搜索樹，所以map、set的增刪操作時間時間復雜度是logn，注意我這里沒有說unordered_map、unordered_set，unordered_map、unordered_set底層實現是哈希表。
（文章部分參考代碼隨想錄,鏈接: link
