‘’’
樹狀存儲(chǔ)基本概念

深度（層數(shù)）
度（子樹個(gè)數(shù)）
葉子
孩子
兄弟
堂兄弟

二叉樹：
滿二叉樹：
完全二叉樹：

存儲(chǔ)：順序，鏈?zhǔn)?/p>

樹的遍歷：按層遍歷，先序，中序，后序

‘’’
樹是計(jì)算機(jī)科學(xué)中的一種重要數(shù)據(jù)結(jié)構(gòu)。以下是關(guān)于樹的基本概念和類型的詳細(xì)介紹。

基本概念

• 深度（層數(shù)）：樹中某個(gè)節(jié)點(diǎn)的深度是從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)歷的邊的數(shù)目。根節(jié)點(diǎn)的深度為0。

• 度（子樹個(gè)數(shù)）：一個(gè)節(jié)點(diǎn)的度是該節(jié)點(diǎn)的子節(jié)點(diǎn)（或子樹）的個(gè)數(shù)。樹的度是指樹中所有節(jié)點(diǎn)的度的最大值。

• 葉子：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，即度為0的節(jié)點(diǎn)。

• 孩子：某個(gè)節(jié)點(diǎn)的直接下屬節(jié)點(diǎn)稱為該節(jié)點(diǎn)的孩子。

• 兄弟：具有同一個(gè)父節(jié)點(diǎn)的多個(gè)節(jié)點(diǎn)之間互稱為兄弟。

• 堂兄弟：具有同一祖父節(jié)點(diǎn)但不同父節(jié)點(diǎn)的節(jié)點(diǎn)之間互稱為堂兄弟。

二叉樹

二叉樹是一種特殊的樹形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。二叉樹有以下幾種特殊形式：

• 滿二叉樹：一個(gè)二叉樹如果除了葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，并且所有葉子節(jié)點(diǎn)都在同一層次上，那么這個(gè)二叉樹就是滿二叉樹。

• 完全二叉樹：一個(gè)二叉樹，如果除了最后一層外，每一層的節(jié)點(diǎn)都是滿的，并且最后一層的節(jié)點(diǎn)都從左到右連續(xù)排列，這樣的二叉樹就是完全二叉樹。

存儲(chǔ)方式

• 順序存儲(chǔ)：利用數(shù)組存儲(chǔ)二叉樹。通常按層次順序存儲(chǔ)，從根節(jié)點(diǎn)開始，依次存入數(shù)組的相應(yīng)位置。

• 鏈?zhǔn)酱鎯?chǔ)：利用鏈表存儲(chǔ)二叉樹。每個(gè)節(jié)點(diǎn)使用一個(gè)結(jié)構(gòu)體表示，結(jié)構(gòu)體包含數(shù)據(jù)域和兩個(gè)指針域，分別指向左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

樹的遍歷

• 按層遍歷：從樹的根節(jié)點(diǎn)開始，逐層遍歷樹中的所有節(jié)點(diǎn)。這種遍歷方式也稱為廣度優(yōu)先遍歷。

• 先序遍歷（前序遍歷）：先訪問根節(jié)點(diǎn)，然后遞歸地先序遍歷左子樹，最后遞歸地先序遍歷右子樹。

• 中序遍歷：先遞歸地中序遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遞歸地中序遍歷右子樹。

• 后序遍歷：先遞歸地后序遍歷左子樹，然后遞歸地后序遍歷右子樹，最后訪問根節(jié)點(diǎn)。

• 先中 和中后 能確定一顆樹

以下是樹的各種存儲(chǔ)方式和遍歷方式的示例代碼：

順序存儲(chǔ)示例

#define MAXSIZE 100typedef struct {int data[MAXSIZE];int size;
} SeqTree;

鏈?zhǔn)酱鎯?chǔ)示例

typedef struct TreeNode {int data;struct TreeNode *left, *right;
} TreeNode;

樹的遍歷示例

// 先序遍歷
void preOrder(TreeNode *root) {if (root != NULL) {printf("%d ", root->data);preOrder(root->left);preOrder(root->right);}
}// 中序遍歷
void inOrder(TreeNode *root) {if (root != NULL) {inOrder(root->left);printf("%d ", root->data);inOrder(root->right);}
}// 后序遍歷
void postOrder(TreeNode *root) {if (root != NULL) {postOrder(root->left);postOrder(root->right);printf("%d ", root->data);}
}// 按層遍歷
void levelOrder(TreeNode *root) {if (root == NULL) return;Queue q;initQueue(&q);enqueue(&q, root);while (!isEmpty(&q)) {TreeNode *node = dequeue(&q);printf("%d ", node->data);if (node->left != NULL) enqueue(&q, node->left);if (node->right != NULL) enqueue(&q, node->right);}
}

通過以上介紹，相信你對(duì)樹的基本概念、二叉樹及其特殊形式、存儲(chǔ)方式和遍歷方法有了更清晰的理解。