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

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

二叉樹(shù)：
滿(mǎn)二叉樹(shù)：
完全二叉樹(shù)：

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

樹(shù)的遍歷：按層遍歷，先序，中序，后序

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

基本概念

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

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

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

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

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

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

二叉樹(shù)

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

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

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

存儲(chǔ)方式

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

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

樹(shù)的遍歷

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

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

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

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

• 先中 和中后 能確定一顆樹(shù)

以下是樹(shù)的各種存儲(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;

樹(shù)的遍歷示例

// 先序遍歷
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);}
}

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