????????數(shù)據(jù)結(jié)構(gòu)中的樹與二叉樹，是在建立非線性數(shù)據(jù)結(jié)構(gòu)方面極為重要的兩個(gè)概念。它們不僅能夠模擬出生活中各種實(shí)際問題的復(fù)雜關(guān)系，還常被用于實(shí)現(xiàn)搜索、排序、查找等算法，甚至成為一些大型軟件和系統(tǒng)中的基礎(chǔ)設(shè)施。
??????? 無論你是初學(xué)者還是進(jìn)階者，本文將為你提供簡單易懂、實(shí)用可行的知識(shí)點(diǎn)，幫助你更好地掌握樹和二叉樹在數(shù)據(jù)結(jié)構(gòu)和算法中的重要性，進(jìn)而提升算法解題的能力。接下來讓我們開啟數(shù)據(jù)結(jié)構(gòu)與算法的奇妙之旅吧。
目錄
樹和森林的概念
樹的常考性質(zhì)
二叉樹的定義及其性質(zhì)
二叉樹的表示
二叉樹遍歷
樹和森林的概念
樹的定義：樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點(diǎn)（node）和邊（edge）組成。樹的基本概念是以層次結(jié)構(gòu)來組織和表示數(shù)據(jù)。
在樹中，有一個(gè)特殊的節(jié)點(diǎn)被稱為根節(jié)點(diǎn)（root），它是樹的頂層節(jié)點(diǎn)，所有其他節(jié)點(diǎn)都直接或間接地與根節(jié)點(diǎn)相連。除了根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)可以有零個(gè)或多個(gè)子節(jié)點(diǎn)（child），子節(jié)點(diǎn)又可以有自己的子節(jié)點(diǎn)，形成了樹的分支結(jié)構(gòu)。沒有子節(jié)點(diǎn)的節(jié)點(diǎn)被稱為葉節(jié)點(diǎn)（leaf）或葉子節(jié)點(diǎn)，它們位于樹的最底層。節(jié)點(diǎn)之間的連接稱為邊，邊描述了節(jié)點(diǎn)之間的關(guān)系。每個(gè)節(jié)點(diǎn)可以有零條到多條邊連接到其子節(jié)點(diǎn)。任意兩個(gè)節(jié)點(diǎn)之間都存在唯一的路徑，通過路徑可以從一個(gè)節(jié)點(diǎn)到達(dá)另一個(gè)節(jié)點(diǎn)。
樹的結(jié)構(gòu)具有以下特點(diǎn)：
- 一個(gè)樹可以由零個(gè)或多個(gè)節(jié)點(diǎn)組成。
- 有且只有一個(gè)根節(jié)點(diǎn)，它是樹的起點(diǎn)。
- 每個(gè)節(jié)點(diǎn)可以有零個(gè)或多個(gè)子節(jié)點(diǎn)。
- 節(jié)點(diǎn)之間通過邊相連，形成層次結(jié)構(gòu)。
- 每個(gè)節(jié)點(diǎn)除了根節(jié)點(diǎn)外，都有且只有一個(gè)父節(jié)點(diǎn)。
樹的基本術(shù)語：
結(jié)點(diǎn)之間的關(guān)系描述
????????根節(jié)點(diǎn)（Root Node）：樹的頂層節(jié)點(diǎn)稱為根節(jié)點(diǎn)。根節(jié)點(diǎn)是樹的起點(diǎn)，它沒有父節(jié)點(diǎn)，其他所有節(jié)點(diǎn)都直接或間接地與根節(jié)點(diǎn)相連。
????????祖先節(jié)點(diǎn)（Ancestor Node）：對(duì)于一個(gè)節(jié)點(diǎn)，它的所有上級(jí)節(jié)點(diǎn)（包括父節(jié)點(diǎn)、父節(jié)點(diǎn)的父節(jié)點(diǎn)等等）都被稱為該節(jié)點(diǎn)的祖先節(jié)點(diǎn)。
????????子孫節(jié)點(diǎn)（Descendant Node）：對(duì)于一個(gè)節(jié)點(diǎn)，它的所有下級(jí)節(jié)點(diǎn)（包括子節(jié)點(diǎn)、子節(jié)點(diǎn)的子節(jié)點(diǎn)等等）都被稱為該節(jié)點(diǎn)的子孫節(jié)點(diǎn)。
????????父節(jié)點(diǎn)（Parent Node）：一個(gè)節(jié)點(diǎn)的直接上一級(jí)節(jié)點(diǎn)稱為其父節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都可以有零個(gè)或多個(gè)子節(jié)點(diǎn)，但只能有一個(gè)父節(jié)點(diǎn)（除了根節(jié)點(diǎn)）。
????????子節(jié)點(diǎn)（Child Node）：一個(gè)節(jié)點(diǎn)直接連接的下一級(jí)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)可以有零個(gè)或多個(gè)子節(jié)點(diǎn)。
????????兄弟節(jié)點(diǎn)（Sibling Node）：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)。兄弟節(jié)點(diǎn)在同一層級(jí)上。
????????葉節(jié)點(diǎn)（Leaf Node）：也稱為葉子節(jié)點(diǎn)，是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，位于樹的最底層。
????????層級(jí)（Level）：根節(jié)點(diǎn)在第一層，其直接子節(jié)點(diǎn)在第二層，以此類推。一個(gè)節(jié)點(diǎn)所在的層級(jí)數(shù)即為該節(jié)點(diǎn)的層級(jí)。
結(jié)點(diǎn)、樹的屬性描述
????????節(jié)點(diǎn)值（Node Value）：每個(gè)節(jié)點(diǎn)都可以攜帶一個(gè)值或數(shù)據(jù)，表示該節(jié)點(diǎn)所代表的實(shí)際含義或信息。
????????節(jié)點(diǎn)深度（Node Depth）：節(jié)點(diǎn)深度指的是該節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長度，即從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)過的邊的數(shù)量。根節(jié)點(diǎn)的深度為0。
????????節(jié)點(diǎn)高度（Node Height）：節(jié)點(diǎn)高度指的是該節(jié)點(diǎn)到其最遠(yuǎn)葉節(jié)點(diǎn)的路徑長度，即從該節(jié)點(diǎn)到達(dá)最遠(yuǎn)葉節(jié)點(diǎn)所經(jīng)過的邊的數(shù)量。葉節(jié)點(diǎn)的高度為0。
????????子樹（Subtree）：對(duì)于一個(gè)樹中的節(jié)點(diǎn)，可以以該節(jié)點(diǎn)為根構(gòu)成的子樹稱為該節(jié)點(diǎn)的子樹。
????????樹的大?。═ree Size）：指的是樹中包含的所有節(jié)點(diǎn)的總數(shù)。
????????樹的高度（Tree Height）：指的是樹中任意節(jié)點(diǎn)的高度的最大值。也可以理解為從根節(jié)點(diǎn)到最遠(yuǎn)葉節(jié)點(diǎn)的路徑長度的最大值。
有序樹、無序樹
????????有序樹（Ordered Tree）：有序樹是指樹中的子節(jié)點(diǎn)之間存在明確的順序關(guān)系。在有序樹中，每個(gè)子節(jié)點(diǎn)都有一個(gè)明確定義的位置，在遍歷和表示樹的時(shí)候需要按照順序來考慮。例如，家譜樹中的兄弟姐妹一般按照他們出生的先后順序排列。
????????無序樹（Unordered Tree）：無序樹是指樹中的子節(jié)點(diǎn)之間沒有明確的順序關(guān)系。在無序樹中，所有子節(jié)點(diǎn)都是平等的，沒有先后之分。例如，文件系統(tǒng)中的目錄結(jié)構(gòu)就是一種無序樹，其中的各個(gè)子目錄之間沒有特定的順序。
????????有序樹和無序樹的區(qū)別在于子節(jié)點(diǎn)的排列方式。在有序樹中，子節(jié)點(diǎn)的順序很重要，會(huì)影響到樹的結(jié)構(gòu)和含義；而在無序樹中，子節(jié)點(diǎn)的順序并不重要，只需要知道它們是該節(jié)點(diǎn)的子節(jié)點(diǎn)即可。
森林
森林（Forest）是指由多棵樹（Tree）組成的集合。簡單來說，森林可以看作是多個(gè)獨(dú)立的樹的集合。
森林的特點(diǎn)在于其中的樹之間是相互獨(dú)立的，彼此之間沒有直接的連接或關(guān)系。每棵樹都可以獨(dú)立地進(jìn)行遍歷和操作。
需要注意的是，森林和樹的層次結(jié)構(gòu)是不同的概念。樹是一種層次結(jié)構(gòu)，它具有唯一的根節(jié)點(diǎn)和從根節(jié)點(diǎn)到其他節(jié)點(diǎn)的確定路徑；而森林則是多個(gè)獨(dú)立的樹的集合，在森林中任意兩棵樹之間沒有直接的聯(lián)系。
樹的抽象數(shù)據(jù)類型：
樹的抽象數(shù)據(jù)類型定義了對(duì)樹進(jìn)行操作的基本操作集合，包括以下常見操作：
1）創(chuàng)建樹：創(chuàng)建一個(gè)空的樹數(shù)據(jù)結(jié)構(gòu)。
2）插入節(jié)點(diǎn)：在樹中插入一個(gè)新節(jié)點(diǎn)，并建立節(jié)點(diǎn)之間的關(guān)系。
3）刪除節(jié)點(diǎn)：從樹中刪除指定的節(jié)點(diǎn)，并調(diào)整節(jié)點(diǎn)之間的關(guān)系。
4）遍歷樹：按照特定的順序訪問樹中的節(jié)點(diǎn)，例如先序遍歷、中序遍歷、后序遍歷等。
5）查找節(jié)點(diǎn)：在樹中查找指定的節(jié)點(diǎn)。
6）獲取樹的屬性：獲取樹的高度、節(jié)點(diǎn)個(gè)數(shù)、根節(jié)點(diǎn)等屬性信息。
樹的抽象數(shù)據(jù)類型并不關(guān)注具體的實(shí)現(xiàn)方式，而是定義了可以對(duì)樹進(jìn)行的操作以及這些操作的預(yù)期行為。
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：??
樹的?？夹再|(zhì)
常見考點(diǎn)1：結(jié)點(diǎn)數(shù) = 總度數(shù) + 1
常見考點(diǎn)2：度為m的樹、m叉樹的區(qū)別
常見考點(diǎn)3：度為m的樹第i層至多有? 個(gè)結(jié)點(diǎn) (i 1)，同理m叉樹第i層至多有 個(gè)結(jié)點(diǎn) (i 1)：
常見考點(diǎn)4：高度為h的m叉樹至多有 個(gè)結(jié)點(diǎn)。
常見考點(diǎn)5：高度為h的m叉樹至少有h個(gè)結(jié)點(diǎn)。高度為h度為m的樹至少有h+m-1個(gè)結(jié)點(diǎn)。
常見考點(diǎn)6：具有n個(gè)結(jié)點(diǎn)的m叉樹的最小高度為
高度最小的情況——所有結(jié)點(diǎn)都有m個(gè)孩子：
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：???
二叉樹的定義及其性質(zhì)
二叉樹定義：
二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集合，其有以下兩種情況：
1）為空二叉樹，即 n = 0 的時(shí)候
2）由一個(gè)根結(jié)點(diǎn)和兩個(gè)互不相交的被稱為根的左子樹和右子樹組成。左子樹和右子樹又分別是一顆二叉樹。
特點(diǎn)：每個(gè)結(jié)點(diǎn)至多只有兩顆子樹；左右子樹不能顛倒。
二叉樹的五種狀態(tài)：
幾個(gè)特殊的二叉樹：
滿二叉樹：所有葉節(jié)點(diǎn)都在同一層，并且所有非葉節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)的二叉樹稱為滿二叉樹。
完全二叉樹：除了最后一層節(jié)點(diǎn)之外，所有節(jié)點(diǎn)都擁有兩個(gè)子節(jié)點(diǎn)，并且最后一層的節(jié)點(diǎn)都向左對(duì)齊的二叉樹稱為完全二叉樹。
二叉排序樹：(比如找關(guān)鍵字為60的結(jié)點(diǎn))
平衡二叉樹：樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1。
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：???
二叉樹的常考性質(zhì)：
常見考點(diǎn)1：設(shè)非空二叉樹中度為0、1和2的結(jié)點(diǎn)個(gè)數(shù)分別為 ，則
葉子結(jié)點(diǎn)比二分支結(jié)點(diǎn)多一個(gè)
常見考點(diǎn)2：二叉樹第i層至多有 個(gè)結(jié)點(diǎn)(i1);m叉樹第i層至多有 個(gè)結(jié)點(diǎn)(i1)
常見考點(diǎn)3：高度為h的二叉樹至多有 個(gè)結(jié)點(diǎn)（滿二叉樹）
高度為h的m叉樹至多有 個(gè)結(jié)點(diǎn)
完全二叉樹的常考性質(zhì)：
常見考點(diǎn)1：具有n個(gè)(n>0)結(jié)點(diǎn)的完全二叉樹的高度h為
或
常見考點(diǎn)2：對(duì)于完全二叉樹，可以由結(jié)點(diǎn)數(shù) n 推出度為 0、1和2的結(jié)點(diǎn)個(gè)數(shù)為、和
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：????
二叉樹的表示
在數(shù)據(jù)結(jié)構(gòu)中，二叉樹可以通過數(shù)組表示和鏈表存儲(chǔ)表示兩種方式來實(shí)現(xiàn)。下面分別對(duì)這兩種表示方式進(jìn)行簡述：
數(shù)組表示：
數(shù)組表示是將二叉樹的節(jié)點(diǎn)按照某種方式存儲(chǔ)在一個(gè)一維數(shù)組中。一般情況下，數(shù)組可以按照層次遍歷的順序存儲(chǔ)二叉樹的節(jié)點(diǎn)。假設(shè)根節(jié)點(diǎn)存儲(chǔ)在數(shù)組下標(biāo)為0的位置，那么對(duì)于任意一個(gè)節(jié)點(diǎn)的索引 i，其左子節(jié)點(diǎn)的索引為 2i+1，右子節(jié)點(diǎn)的索引為 2i+2。如果某個(gè)位置為空，可以使用特定的空值表示。
數(shù)組表示的優(yōu)點(diǎn)：
數(shù)組表示的優(yōu)點(diǎn)是存儲(chǔ)簡單，通過數(shù)組索引可以快速訪問到任意節(jié)點(diǎn)。缺點(diǎn)是當(dāng)二叉樹的形狀發(fā)生改變時(shí)，需要重新調(diào)整數(shù)組的大小，可能涉及到大量的元素移動(dòng)。
#include <stdio.h>
#include <stdlib.h>
// 二叉樹節(jié)點(diǎn)結(jié)構(gòu)體
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 構(gòu)建二叉樹的數(shù)組表示
struct TreeNode* build_binary_tree(int arr[], int size) {
struct TreeNode** tree = malloc(sizeof(struct TreeNode*) * size);
for (int i = 0; i < size; i++) {
if (arr[i] != -1) {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = arr[i];
node->left = NULL;
node->right = NULL;
tree[i] = node;
} else {
tree[i] = NULL;
}
}
for (int i = 0; i < size; i++) {
if (tree[i] != NULL) {
if (2 * i + 1 < size)
tree[i]->left = tree[2 * i + 1];
if (2 * i + 2 < size)
tree[i]->right = tree[2 * i + 2];
}
}
struct TreeNode* root = tree[0];
free(tree);
return root;
}
// 測試代碼
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
struct TreeNode* root = build_binary_tree(arr, size);
// 輸出測試結(jié)果
printf("root: %d\n", root->val);
printf("left child of root: %d\n", root->left->val);
printf("right child of root: %d\n", root->right->val);
return 0;
}鏈表存儲(chǔ)表示：
鏈表存儲(chǔ)表示是使用鏈表的方式來表示二叉樹。每個(gè)節(jié)點(diǎn)包含一個(gè)指向其父節(jié)點(diǎn)的指針，一個(gè)指向其左子節(jié)點(diǎn)的指針，一個(gè)指向其右子節(jié)點(diǎn)的指針。
鏈表存儲(chǔ)表示的優(yōu)點(diǎn)：
鏈表存儲(chǔ)表示的優(yōu)點(diǎn)是可以靈活地插入、刪除節(jié)點(diǎn)而不需要移動(dòng)其他節(jié)點(diǎn)，適用于頻繁變化的二叉樹結(jié)構(gòu)。缺點(diǎn)是訪問某個(gè)節(jié)點(diǎn)需要從根節(jié)點(diǎn)開始遍歷，效率相對(duì)較低。
#include <stdio.h>
#include <stdlib.h>
// 二叉樹節(jié)點(diǎn)結(jié)構(gòu)體
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 構(gòu)建二叉樹的鏈表存儲(chǔ)表示
struct TreeNode* build_binary_tree(int arr[], int size) {
if (size == 0) {
return NULL;
}
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = arr[0];
root->left = NULL;
root->right = NULL;
struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * size);
int front = 0;
int rear = 0;
queue[rear++] = root;
int i = 1;
while (i < size) {
struct TreeNode* node = queue[front++];
// 處理左子節(jié)點(diǎn)
if (arr[i] != -1) {
node->left = malloc(sizeof(struct TreeNode));
node->left->val = arr[i];
node->left->left = NULL;
node->left->right = NULL;
queue[rear++] = node->left;
}
i++;
// 處理右子節(jié)點(diǎn)
if (i < size && arr[i] != -1) {
node->right = malloc(sizeof(struct TreeNode));
node->right->val = arr[i];
node->right->left = NULL;
node->right->right = NULL;
queue[rear++] = node->right;
}
i++;
}
free(queue);
return root;
}
// 測試代碼
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
struct TreeNode* root = build_binary_tree(arr, size);
// 輸出測試結(jié)果
printf("root: %d\n", root->val);
printf("left child of root: %d\n", root->left->val);
printf("right child of root: %d\n", root->right->val);
return 0;
}二叉樹遍歷
遍歷：按照某種次序把所有結(jié)點(diǎn)都訪問一遍。根據(jù)二叉樹的遞歸特性要么是個(gè)空二叉樹，要么就是由“根結(jié)點(diǎn)+左子樹+右子樹”組成的二叉樹
根據(jù)二叉樹的三種遍歷規(guī)則，相關(guān)的具體案例如下：
再進(jìn)行具體的練習(xí)一遍：
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：
二叉樹的層序(次)遍歷：
其相應(yīng)的代碼實(shí)現(xiàn)如下：
由遍歷序列構(gòu)造二叉樹：
回顧重點(diǎn)，其主要內(nèi)容整理成如下內(nèi)容：?文章來源：http://www.zghlxwxcb.cn/news/detail-716709.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-716709.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--》解鎖數(shù)據(jù)結(jié)構(gòu)中樹與二叉樹的奧秘（一）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
