二叉树、树和森林

内容

• 二叉树、树和森林的定义；
• 二叉树的实现（包括顺序存储结构和链式存储结构）、二叉树的遍历；
• 二叉树结构下的应用及扩展，例如二叉检索树、2-3-4树、B树、B+树、Huffman编码以及堆；
• 平衡二叉树的定义、平衡因子的定义以及平衡二叉树的旋转操作；
• 树和森林的存储结构、树和森林的遍历以及森林与二叉树的转换；
• 森林结构的应用，例如并查集。

要求

• 掌握二叉树、树和森林的定义以及它们之间的异同点；
• 掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力；
• 理解二叉树采用顺序存储结构和链式存储结构的差异性；
• 掌握利用二叉树及其扩展下的检索技术；
• 掌握Huffman编码、堆的实现及应用；
• 理解平衡二叉树的意义；
• 掌握平衡二叉树的旋转操作；
• 掌握树、森林能够采用的各种存储方式的差异性；
• 掌握树和森林与二叉树的转换；
• 掌握树、森林在遍历方面和二叉树的不同以及相关性；
• 理解并查集的意义，以及掌握并查集的基本操作的实现。