一、樹的基本概念

1. 樹的定義
   樹（Tree）是由 n（n ≥ 0）個節點組成的有限集合，當 n = 0 時稱為空樹。非空樹中：

   • 有且僅有一個根節點（Root）；

   • 其余節點可以劃分為若干個互不相交的子樹，每個子樹本身也是一棵樹。

2. 樹的節點與術語

   • 節點包含數據和若干分支；

   • 度（Degree）：節點擁有的子樹數量；

   • 葉子節點：度為 0 的節點；

   • 非終端節點：度不為 0 的節點（又稱分支節點）；

   • 孩子（Child）與雙親（Parent）：節點間的直接連接關系；

   • 兄弟節點（Sibling）：同一雙親下的節點；

   • 祖先與子孫：從根到某節點的路徑上所有節點為祖先，某節點下所有子節點為子孫。

3. 其他概念

   • 層次（Level）：根為第一層，孩子為第二層，以此類推；

   • 深度（Depth）或高度：節點最大層次；

   • 有序樹與無序樹：若子樹順序不能交換則為有序樹，否則為無序樹。

---

二、樹的存儲結構

樹的存儲可分為：

• 順序結構（如數組）；

• 鏈式結構（如鏈表）；
  實際開發中，樹通常采用鏈式結構實現。

---

三、二叉樹的基本概念

1. 定義
   二叉樹是每個節點最多有兩個子樹（左子樹和右子樹）的樹結構。這兩個子樹有先后順序，不能顛倒。二叉樹可能為空，也可能只有一個根節點。

2. 特點

   • 節點度最大為 2；

   • 必須區分左子樹和右子樹，即使只有一個孩子；

   • 子樹順序不可交換。

3. 二叉樹的五種基本形態

   • 空二叉樹；

   • 只有根節點；

   • 只有左子樹；

   • 只有右子樹；

   • 同時有左右子樹。

---

四、特殊的二叉樹

1. 斜樹

   • 左斜樹：每個節點只有左子樹；

   • 右斜樹：每個節點只有右子樹。

2. 滿二叉樹
   滿足：

   • 所有非葉子節點都有左右兩個子樹；

   • 所有葉子節點都在同一層；

   • 特點：整棵樹結構完全對稱，節點數最多。

3. 完全二叉樹
   滿足：

   • 葉子只出現在最下兩層；

   • 最下層葉子靠左連續；

   • 最后一層若不滿，葉子也必須靠左；

   • 同樣節點數下，深度最小。

---

五、二叉樹的性質（重點公式）

1. 第 i 層最多有 2^(i-1) 個節點（i≥1）

2. 深度為 k 的二叉樹最多有 2^k - 1 個節點

3. 葉子數 = 度為 2 的節點數 + 1

4. n 個節點的完全二叉樹深度為 log?(n) + 1

5. 編號為 i 的節點：

   • 若 i=1，它是根節點；

   • 左孩子編號為 2i；

   • 右孩子編號為 2i + 1（若存在）；

   • 雙親編號為 i / 2（i > 1 時）。

---

六、二叉樹的遍歷方式

1. 前序遍歷：根 → 左 → 右

2. 中序遍歷：左 → 根 → 右

3. 后序遍歷：左 → 右 → 根

注：遍歷時雖然“根”在描述中寫在前面，但實際執行順序是遞歸的，需要先進入子樹再處理根節點。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char DataType;typedef struct BiTNode
{DataType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode;char data[] = "Abd#g###ce#h##fi###";int ind = 0;void CreateTree(BiTNode **root)
{char c = data[ind++];if('#' == c){*root = NULL;return ;}else{*root = malloc(sizeof(BiTNode));if(*root == NULL){printf("malloc errror\n");*root = NULL;return ;}(*root)->data = c;CreateTree(&(*root)->lchild);CreateTree(&(*root)->rchild);}return ;
}
//根左右
void PreOrderTraverse(BiTNode *root)
{if(NULL == root){return ;}else{printf("%c", root->data);PreOrderTraverse((*root).lchild);PreOrderTraverse((*root).rchild);}return ;
}
//左根右
void InOrderTraverse(BiTNode *root)
{if(NULL == root){return ;}else{InOrderTraverse(root->lchild);printf("%c", root->data);InOrderTraverse(root->rchild);return ;}
}//左右根
void PostOrderTraverse(BiTNode *root)
{if (NULL == root){return;}PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c", root->data);return;
}void DestroyTree(BiTNode *root)
{if (NULL == root){return;}DestroyTree(root->lchild);DestroyTree(root->rchild);free(root);root = NULL;return;
}int main(int argc, char const *argv[])
{BiTNode *root;CreateTree(&root);PreOrderTraverse(root);printf("\n");InOrderTraverse(root);printf("\n");PostOrderTraverse(root);printf("\n");DestroyTree(root);root = NULL;return 0;
}