敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 目 录 6.1树的定义和基本术语 0 6.2二叉树.… 6.2.1二叉树的定义 6.2.2二叉树的性质 3 6.2.3二叉树的存储结构.. 4 6.3树和森林.. 5 6.4二叉树的先中后序遍历算法. 6 6.5先后引中序遍历的应用扩展 。,。。 8 6.5.1基于先序遍历的二叉树（二叉链的创建 8 6.5.2统计二叉树中叶子结点的数目8 6.5.3求二叉树的高度 .9 6.5.4释放二叉树的所有结点空间. 10 6.5.5删除并释放二叉树中以元素值为x的结点作为根的各子树 11 65.6求位于二叉树先序序列中第k个位置的结点的值12 6.5.7线索二叉树12 6.5.8树和森林的遍历14 6.6二叉树的层次遍历… ,。,。。。,,,,,,,,。,。。,。,。,。,,,。, 6.7判断一棵二叉树是否为完全二叉树 。,,,,,,,,,, 6.8哈夫曼树及其应用 18 6.8.1最优二叉树（哈夫曼树） .18 6.8.2哈夫曼编码 18 6.9遍历二叉树的非递归算法 .19 6.9.1先序非递归算法 .19 6.9.2中序非递归算法 .20 6.9.3后序非递归算法 .20 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第0页程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 0 页 第六章 树和二叉树 基本概念、遍历算法及其应用 目 录 6.1 树的定义和基本术语.................................................................................................0 6.2 二叉树......................................................................................................................1 6.2.1 二叉树的定义..................................................................................................1 6.2.2 二叉树的性质..................................................................................................3 6.2.3 二叉树的存储结构...........................................................................................4 6.3 树和森林..................................................................................................................5 6.4 二叉树的先|中|后序遍历算法.....................................................................................6 6.5 先|后|中序遍历的应用扩展........................................................................................8 6.5.1 基于先序遍历的二叉树(二叉链)的创建............................................................8 6.5.2 统计二叉树中叶子结点的数目.........................................................................8 6.5.3 求二叉树的高度..............................................................................................9 6.5.4 释放二叉树的所有结点空间...........................................................................10 6.5.5 删除并释放二叉树中以元素值为x的结点作为根的各子树............................... 11 6.5.6 求位于二叉树先序序列中第k个位置的结点的值.............................................12 6.5.7 线索二叉树...................................................................................................12 6.5.8 树和森林的遍历............................................................................................14 6.6 二叉树的层次遍历..................................................................................................15 6.7 判断一棵二叉树是否为完全二叉树..........................................................................16 6.8 哈夫曼树及其应用..................................................................................................18 6.8.1 最优二叉树(哈夫曼树)...................................................................................18 6.8.2 哈夫曼编码...................................................................................................18 6.9 遍历二叉树的非递归算法........................................................................................19 6.9.1 先序非递归算法............................................................................................19 6.9.2 中序非递归算法............................................................................................20 6.9.3 后序非递归算法............................................................................................20