一、树的基本概念

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;
}