[研究生入学考试]数据结构.ppt

01/06/2002 数据结构讲义 第六章 二叉树 ⒈教学内容： 6.1 定义与性质 6.2 存储实现基本操作的实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 二叉树的应用 ⒉教学目的： ⑴ 理解二叉树定义、性质及其存储方法； ⑵ 掌握二叉树的二叉链表存储方式； ⑶ 理解并掌握二叉树的三种遍历算法； ⑷ 掌握二叉树的线索化方法； ⑸ 运用二叉树的遍历解决相关应用问题； 6.1 定义与性质 二叉树的基本概念 二叉树的主要性质 6.1.2 二叉树的主要性质 性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。 该性质可由数学归纳法证明。证明略。 性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。 证明 设第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为M，xi最多为2i-1，则有： 6.2 基本操作与存储实现 二叉树的存储 二叉树的基本操作及实现 6.2.1 二叉树的存储 1．顺序存储结构 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。 6.2.2 二叉树的基本操作及实现 二叉树的基本操作通常有以下几种： （1）Initiate（bt）建立一棵空二叉树。 （2）Create（x，lbt，rbt）生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。 （3）InsertL（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。 6.3 二叉树的遍历 二叉树的遍历方法及递归实现 二叉树遍历的非递归实现 由遍历序列恢复二叉树 不用栈的二叉树遍历的非递归方法 层次遍历 6.3.1 二叉树的遍历方法及递归实现 二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。 遍历是二叉树中经常要用到的一种操作。 通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。 6.3.2 二叉树遍历的非递归实现 递归程序虽然简洁，但可读性一般不好，执行效率也不高。因此，就存在如何把一个递归算法转化为非递归算法的问题。解决这个问题的方法可以通过对三种遍历方法的实质过程的分析得到。 6.3.5 层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于下图所示的二叉树，按层次遍历所得到的结果序列为： A B C D E F G 6.4 线索二叉树 线索二叉树的定义及结构 线索二叉树的基本操作实现 6.4.1 线索二叉树的定义及结构 1．线索二叉树的定义 按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排列为一个线性序列。但是，二叉树中每个结点在这个序列中的直接前驱结点和直接后继结点是什么，二叉树的存储结构中并没有反映出来，只能在对二叉树遍历的动态过程中得到这些信息。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，利用二叉树的二叉链表存储结构中的那些空指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索（thread），加了线索的二叉树称为线索二叉树。 线索二叉树将为二叉树的遍历提供许多遍历。 6.4.2 线索二叉树的基本操作实现 在线索二叉树中，结点的结构可以定义为如下形式： typedef char elemtype; typedef struct BiThrNode { elemtype data; struct BiThrNode *lchild; struct BiThrNode *rchild; unsigned ltag; unsigned rtag; }BiThrNodeType,*BiThrTree; 6.5 二叉树的应用 二叉树遍历的应用 最优二叉树――哈夫曼树 6.5.1 二叉树遍历的应用 1．查找数据元素 BiTree Search（BiTree bt，elemtype x） /*在bt为根结点指针的二叉树中查找数据元素x