数据结构c语言版 (5).ppt

《数据结构c语言版 (5).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章树与二叉树退出主要内容5.1树的定义及基本术语5.2二叉树5.3遍历二叉树5.4线索二叉树5.5二叉排序树5.7哈夫曼树5．1树的定义及基本术语5．1．1树的定义结点的度终端结点非终端结点结点的层次树的度树的深度有序树、无序树森林5．1树的定义及基本术语5．1．1树的定义孩子、双亲子孙祖先兄弟堂兄弟5．1．1树的定义定义：树是一种常用的非线性结构。树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，..

2、.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。5．1．1树的定义5.2二叉树定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。5.2二叉树二叉树的5种形态：ø5.2二叉树完全二叉树：有一棵深度为h，具有n个结点的二叉树，

3、若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。5．2．1二叉树的性质(1)在二叉树的第i上至多有2i-1个结点（i>=1）(2)深度为k的二叉树至多有2k-1个结点。(3)设任何一棵二叉树中，叶结点数为n0，度为1的结点数为n1,度为2的结点数为n2，则有：n0=n2+1(4)具有n个结点的完全二叉树其深度为：k=[log2n]+15．2．2二叉树的存储结构1、顺序存储这种存储结构适用

4、于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。顺序存储的二叉树的定义如下：#defineN50/*树结点的最大个数*/typedefelemtypeSQTREE[N];5．2．2二叉树的存储结构845672315．2．2二叉树的存储结构2、链式存储在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结

5、点结构如下所示：其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，item是数据元素的内容。类型定义为：typedefstructBTNode{EntryTypeitem;structBTNode*Lchild,*Rchlid;}BTNode,*BTree;5．2．2二叉树的存储结构GHDEFBCA^G^^H^^D^E^F^B^CABT5．2．2二叉树的存储结构这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如

6、下所示。5．3遍历二叉树5．3．1二叉树的遍历算法二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。5．3．1二叉树的遍历算法按根、左子树和右子树三部分进行遍历根据根访问的位置不同分别被称为先序遍历、中序遍历和后

7、序遍历。5．3．1二叉树的遍历算法1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。5．3．1二叉树的遍历算法（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。5．3．1二叉树的遍历算法（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。5．3．1二叉树的遍历算法GHDEFBCA先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA下面我们再给出三种遍历二叉树的方法：（1

8、）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。DGBAECHFGHDEFBCA（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程