二叉树知识点最详细最全讲解
目錄
?
1.樹的介紹
1.1樹的定義
1.2樹的基本術語
1.3相關性質
2.二叉樹的介紹
2.1二叉樹的定義
2.2二叉樹與度為2的樹的區別
?2.3二叉樹的性質
3.二叉樹的種類
3.1滿二叉樹
? ? ? ? ? ? ?3.1.1定義
?
3.2完全二叉樹
? ? ? ? ? ? 3.2.1定義
? ? ? ? ? ? 3.2.2特點
3.3二叉查找樹
? ? ? ? ? ? ?3.3.1定義
? ? ? ?? ? ? 3.3.2特點
? ? ? ? ? ? ?3.3.3二叉查找樹C語言實現
3.4平衡二叉搜索樹
? ? ? ?? ? ? ?3.4.1定義
4.二叉樹的存儲方式
4.1鏈式存儲
4.2順序存儲
? ? ? ? ? ? ? ? 4.2.1數組存儲的遍歷
5.二叉樹的遍歷方式
? ? ? ? ? 5. 1、深度優先遍歷?
? ? ? ? ? ?5. 2、廣度優先遍歷
6.遍歷的實現（遞歸實現）
6.1遞歸算法三要素
6.2代碼實現（遞歸）
1.樹的介紹
1.1樹的定義
? ? ? ?樹是一種數據結構，它是由n（n>=1）個有限節點組成一個具有層次關系的集合。
? ? ? ? ? ? ??
? ? ? ? ? ?把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
? ? ? ? ? ? ? 1.每個節點有零個或多個子節點;
? ? ? ? ? ? ? 2.沒有父節點的節點稱為根節點;
? ? ? ? ? ? ? 3.每一個非跟節點有且僅有一個父節點;
? ? ? ? ? ? ? 4.除了根節點以外，每個子節點可以分為多個不想交的子樹。
1.2樹的基本術語
? ? ? ? ? ? 若一個節點有子樹，那么該節點稱為子樹根節點的“雙親“，子樹的跟是該節點的“孩子”。有相同雙親的節點互為“兄弟節點”。一個節點的所有子樹上的任何節點都是該節點的后裔。從根節點到某個節點的路徑上的所有節點都是該節點的祖先。
? ? ? ? ? ? 節點的度：節點擁有的子樹的數目。
? ? ? ? ? ? ?葉子：度為零的節點。
? ? ? ? ? ? ?分支節點：度不為零的節點。
? ? ? ? ? ? ?樹的度：樹中節點的最大的度。
? ? ? ? ? ? ?層次：根節點的層次為1，其余節點的層次等于該節點的雙親節點加1。
? ? ? ? ? ? ?樹的高度：樹中節點的最大層次。
? ? ? ? ? ? ?無序數：如果樹中節點的各子樹之間的次序是不重要的，可以交換位置。
? ? ? ? ? ? ?有序數：如果樹中結點的各子樹的次序是重要的，不可以交換位置。
? ? ? ? ? ? ?森林：0個或多個不相交的樹組成。對森林加上一個跟，森林即成為樹；刪去跟，樹即成為森林。
1.3相關性質
? ? ? ? ? ? ?
2.二叉樹的介紹
2.1二叉樹的定義
? ? ? ? ? ? ? ? 二叉樹是每個節點最多有兩個子樹的樹結構。它有五種基本形態：二叉樹可以是空集；根可以有空的左子樹或右子樹；活著左、右子樹皆為空。
?
2.2二叉樹與度為2的樹的區別
? ? ? ? ? ? ?1、度為2的的樹必須有三個節點以上(否則就不叫度為二了，一定要先存在)，二叉樹可以為空。
? ? ? ? ? ? ?2、二叉樹的度不一定為2,比如斜樹。
? ? ? ? ? ? ?3、二叉樹有左右節點區分，而度為2的樹沒有左右節點的區分。
?2.3二叉樹的性質
? ? ? ? ? ? ?性質1：二叉樹第i層上的節點數目最多為?2{i-1}?(i≥1)。
? ? ? ? ? ? ?性質2：深度為k的二叉樹至多有2{k}-1個節點（k>=1）。
? ? ? ? ? ? ?性質3：包含n個節點的二叉樹的高度至少為log2?(n+1)。
? ? ? ? ? ? ?性質4：在任意一顆二叉樹中，若終端節點的個數為n0，度為2的節點數為n2，則n0=n2+1。
3.二叉樹的種類
3.1滿二叉樹
? ? ? ? ? ? ?3.1.1定義
? ? ? ? ? ? ? ? ? ? ? ? ??高度為h，并且由2{h}?–1個結點的二叉樹，被稱為滿二叉樹。
3.2完全二叉樹
? ? ? ? ? ? 3.2.1定義
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?一顆二叉樹中，只有最下面兩層節點的度可以小于2，并且最下層的葉節點集中在靠左的若干位置上。
? ? ? ? ? ? ? ? ?3.2.2特點
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?葉子節點只能出現在最下層和次下層，且最下層的葉子節點集中在樹的左部。顯然，一顆滿二叉樹必定是一顆完全二叉樹，而完全而二叉樹不一定是滿二叉樹。
3.3二叉查找樹
? ? ? ? ? ? ?3.3.1定義
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?二叉查找樹（Binary Search Tree）,又被稱為二叉搜索樹。設x為二叉樹中的一個節點，x節點包含關鍵字Key，節點x的Key值記為Key[x]。如果y是x的左子樹中的一個節點，則Key[y]<=Key[x]；如果y是x的有子樹的一個節點，則Key[y]>=Key[x]。
? ? ? ?? ? ? ? 3.3.2特點
? ? ? ? ? ? ? ? ? ? ? ? ? ? 1、若任意節點的左子樹不空，則左子樹上所有的值均小于根節點的值
? ? ? ? ? ? ? ? ? ? ? ? ? ? 2、若任意節點的右子樹不空，則右子樹上所有節點的值均大于根節點的值（更大于左子樹上的值）
? ? ? ? ? ? ? ? ? ? ? ? ? ? 3、任意節點的左、右子樹也分別為二叉查找樹
? ? ? ? ? ? ? ? ? ? ? ? ? ? 4、沒有鍵值相等的節點
? ? ? ? ? ? ? ? 3.3.3二叉查找樹C語言實現
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3.3.3.1節點定義
typedef int Type;typedef struct BSTreeNode{Type key;//關鍵字（鍵值）struct BSTreeNode *left;//左孩子struct BSTreeNode *right;//右孩子struct BSTreeNode *parent;//父節點 }Node ,*BSTree;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?二叉查找樹的節點包含的基本信息：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1、key——關鍵值，是用來對二叉查找樹的節點進行排序的。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2、left——指向當前節點的左孩子。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3、right——指向當前孩子的右節點。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4、parent——指向當前節點的父節點。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?3.3.3.2創建節點
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
struct Node* create_bstree_node(Type key,Node *parent,Node *left, Node* right) {Node* p;if ((p = (Node *)malloc(sizeof(Node))) == NULL)return NULL;p->key = key;p->left = left;p->right = right;p->parent = parent;return p; }我這里只是寫了一部分，本篇文章的重點不在這里，想繼續研究或者想更深入了解的可以轉一下博主：https://www.cnblogs.com/skywang12345/p/3576328.html#a2
3.4平衡二叉搜索樹
? ? ? ?? ? ? ?3.4.1定義
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 平衡二叉樹搜索樹：又被稱為AVL(Adelson-Velsky and Landis)樹，且具有以下性質：它是一顆空樹或者它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一顆平衡二叉樹。如圖：
4.二叉樹的存儲方式
4.1鏈式存儲
? ? ? ? ? ? ? ? ?通過指針把分布在散落在各個地址的節點串聯在一起，鏈式存儲如圖所示：
4.2順序存儲
? ? ? ? ? ? ? ? 其實就是用數組來存儲二叉樹，順序存儲的方式如圖：
? ? ? ? ? ? ? ? 4.2.1數組存儲的遍歷
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如果父節點的數組下標是i,那么它的左孩子就是2 * i + 1,右孩子就是i * 2 + 2。（但是用鏈式表示的二叉樹更有利于我們理解，一般都是用鏈式存儲二叉樹）
5.二叉樹的遍歷方式
? ? ? ? ? 5. 1、深度優先遍歷?
? ? ? ? ? ? ? ? ? ?①前序遍歷（遞歸法，迭代法）中左右
? ? ? ? ? ? ? ? ? ?②中序遍歷（遞歸法，迭代法）左中右
? ? ? ? ? ? ? ? ? ?③后序遍歷（遞歸法，迭代法）左右中
? ? ? ? ? ?5. 2、廣度優先遍歷
? ? ? ? ? ? ? ? ? ? ①層次遍歷（迭代法）
6.遍歷的實現（遞歸實現）
6.1遞歸算法三要素
? ? ? ? ? ? ? ? ?1、確定遞歸函數的參數和返回值：確定哪些參數是遞歸的過程中需要處理的，那么就在遞歸函數里加上這個參數， 并且還要明確每次遞歸的返回值是什么進而確定遞歸函數的返回類型。
? ? ? ? ? ? ? ? ?2、確定終止條件：寫完了遞歸算法, ?運行的時候，經常會遇到棧溢出的錯誤，就是沒寫終止條件或者終止條件寫的不對，操作系統也是用一個棧的結構來保存每一層遞歸的信息，如果遞歸沒有終止，操作系統的內存棧必然就會溢出。
? ? ? ? ? ? ? ? 3、確定單層遞歸的邏輯：確定每一層遞歸需要處理的信息。在這里也就會重復調用自己來實現遞歸的過程。
? ? ? ? ? ? ? ? 以前序遍歷為例：
? ? ? ? ? ? ? ? ? ? ? 1、「確定遞歸函數的參數和返回值」：因為要打印出前序遍歷節點的數值，所以參數里需要傳入vector在放節點的數值，除了這一點就不需要在處理什么數據了也不需要有返回值，所以遞歸函數返回類型就是void，代碼如下：
void traversal(TreeNode* cur, vector<int>& vec)? ? ? ? ? ? ? 2、「確定終止條件」：在遞歸的過程中，如何算是遞歸結束了呢，當然是當前遍歷的節點是空了，那么本層遞歸就要要結束了，所以如果當前遍歷的這個節點是空，就直接return，代碼如下：
if (cur == NULL) return;? ? ? ? ? ? ? 3、「確定單層遞歸的邏輯」：前序遍歷是中左右的循序，所以在單層遞歸的邏輯，是要先取中節點的數值，代碼如下：
vec.push_back(cur->val); // 中 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右6.2代碼實現（遞歸）
? ? ? ? ? ? ? ? ?前序遍歷：
class Solution { public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val); // 中traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;} };? ? ? ? ? ? ? ? 中序遍歷：
class Solution { public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左vec.push_back(cur->val); // 中traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;} };? ? ? ? ? ? 后序遍歷：
class Solution { public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右vec.push_back(cur->val); // 中}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;} };? ? ? ?
此時可以做一做leetcode上三道題目練練手，分別是：
-
144.二叉樹的前序遍歷
-
145.二叉樹的后序遍歷
-
94.二叉樹的中序遍歷
此處是二叉樹的遍歷，此前我還有一篇文章是表達式的遍歷，也可以看看
總結
以上是生活随笔為你收集整理的二叉树知识点最详细最全讲解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 看看比尔·盖茨在关注什么
- 下一篇： 如何写windows系统已保护的内存区域