一、树的基本概念

1. 树的结构定义

• 递归定义：
  • 空树（n=0）
  • 非空树（n≥1）：
    • 唯一根结点
    • m个互不相交的子树（m≥0）

2. 核心术语

术语	说明	图示示例
结点的度	结点的子树个数
树的度	树中所有结点的最大度数	二叉树度为2
叶结点	度为0的结点	树结构末端结点
分支结点	度≠0的结点	包含子树的结点
树的深度	根到叶结点的最大层数（根为1）	3层树深度为3

---

二、二叉树核心特性

1. 二叉树定义

• 每个结点最多两个子树
• 子树有明确左右之分（不可互换）

2. 特殊二叉树类型

类型	特征	示例
斜树	所有结点只有左/右子树
满二叉树	所有分支结点都有左右子树，叶子在同一层
完全二叉树	层序编号与满二叉树对应，最后一层结点左对齐

3. 重要性质

1. 层节点数：第i层最多2^i-1个结点（i≥1）
2. 总节点数：深度k的树最多2^k-1个结点
3. 叶节点关系：n₀ = n₂ +1（n₀：叶结点，n₂：度为2结点）
4. 完全二叉树深度：⌊log₂n⌋+1

---

三、二叉树存储结构

1. 顺序存储

#define MAX_SIZE 100
typedef struct {int data[MAX_SIZE];  // 按层序存储int size;
} SeqBinaryTree;// 完全二叉树示例
int parent(int i) { return i/2; }
int left(int i) { return 2*i; }
int right(int i) { return 2*i+1; }

2. 链式存储

typedef struct BiTNode {int data;struct BiTNode *lchild, *rchild;
} BiTNode;BiTNode* CreateNode(int val) {BiTNode *new = (BiTNode*)malloc(sizeof(BiTNode));new->data = val;new->lchild = new->rchild = NULL;return new;
}

---

四、遍历算法实现

五、二叉树结构定义

typedef char DATATYPE;typedef struct BiTNode {DATATYPE data;                   // 结点数据struct BiTNode *lchild;          // 左孩子指针struct BiTNode *rchild;          // 右孩子指针
} BiTNode;

---

六、核心操作实现

1. 二叉树创建（先序输入）

char dat[] = "ABD##E##CF##G##";  // 示例输入（#表示空结点）
int inx = 0;void CreateTree(BiTNode **root) {char c = dat[inx++];if ('#' == c) {*root = NULL;return;}*root = (BiTNode*)malloc(sizeof(BiTNode));if (NULL == *root) {perror("malloc failed");exit(EXIT_FAILURE);}(*root)->data = c;CreateTree(&((*root)->lchild));  // 递归创建左子树CreateTree(&((*root)->rchild));  // 递归创建右子树
}

输入示例：

A         --> 根
├─B       --> 左子树
│ ├─D     --> B的左子树
│ └─E     --> B的右子树
└─C       --> 右子树├─F     --> C的左子树└─G     --> C的右子树

---

七、遍历算法实现

1. 递归遍历

// 先序遍历
void PreOrderTraverse(BiTNode *root) {if (root) {printf("%c ", root->data);    // 访问根PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);}
}// 中序遍历
void InOrderTraverse(BiTNode *root) {if (root) {InOrderTraverse(root->lchild);printf("%c ", root->data);    // 访问根InOrderTraverse(root->rchild);}
}// 后序遍历
void PostOrderTraverse(BiTNode *root) {if (root) {PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c ", root->data);    // 访问根}
}

遍历结果：

先序：A B D E C F G 
中序：D B E A F C G 
后序：D E B F G C A 

---

 八、内存管理

1. 二叉树销毁（后序释放）

void DestroyBiTree(BiTNode *root) {if (root) {DestroyBiTree(root->lchild);  // 递归释放左子树DestroyBiTree(root->rchild);  // 递归释放右子树free(root);  // 释放当前结点root = NULL;  // 避免野指针}
}

内存释放顺序：

D → E → B → F → G → C → A

---

九、应用扩展接口

1. 计算二叉树深度

int TreeDepth(BiTNode *root) {if (!root) return 0;int left = TreeDepth(root->lchild);int right = TreeDepth(root->rchild);return (left > right ? left : right) + 1;
}

2. 统计结点数量

int CountNodes(BiTNode *root) {if (!root) return 0;return 1 + CountNodes(root->lchild) + CountNodes(root->rchild);
}

2. 二叉搜索树

// 查找操作（递归）
BiTNode* BSTSearch(BiTNode *root, int key) {if(!root || root->data == key) return root;if(key < root->data)return BSTSearch(root->lchild, key);elsereturn BSTSearch(root->rchild, key);
}

---

十、复杂度对比

操作	平均复杂度	最坏情况
遍历	O(n)	O(n)
查找（BST）	O(log n)	O(n)（退化成链）
插入/删除	O(log n)	O(n)