03. 树与二叉树

树与二叉树

1. 树的基本概念

• 树：n（n≥0）个结点的有限集，根结点、子树、叶子结点、度、层次、深度
• 森林：若干棵互不相交的树的集合

2. 二叉树的定义与特征

• 每个结点最多有两个子结点（左、右）
• 满二叉树、完全二叉树、二叉排序树、平衡二叉树

3. 存储结构

• 顺序存储：用数组存储完全二叉树
• 链式存储：每个结点有数据域、左/右指针域

4. 二叉树的遍历

• 前序遍历（根左右）
• 中序遍历（左根右）
• 后序遍历（左右根）
• 层序遍历（按层次）

5. 线索二叉树

• 利用空指针存储前驱/后继信息，提高遍历效率

6. 树、森林的存储与遍历

• 孩子表示法、双亲表示法、孩子兄弟表示法
• 森林与二叉树的转换

7. 应用

• 二叉搜索树、平衡二叉树、哈夫曼树与哈夫曼编码

练习题

1. 简述树和二叉树的主要区别。
2. 二叉树的前序、中序、后序遍历顺序分别是什么？
3. 如何用数组存储完全二叉树？
4. 线索二叉树的作用是什么？
5. 哈夫曼树的主要应用是什么？