《数据结构c语言版 (5)》由会员分享，可在线阅读，更多相关《数据结构c语言版 (5)（52页珍藏版）》请在金锄头文库上搜索。
1、第 五 章 树与二叉树,退出,主要内容,5.1树的定义及基本术语5.2二叉树5.3遍历二叉树5.4线索二叉树5.5二叉排序树5.7哈夫曼树,51树的定义及基本术语,511树的定义,结点的度终端结点非终端结点结点的层次 树的度树的深度有序树、无序树森林,51树的定义及基本术语,511树的定义,孩子、双亲 子孙 祖先兄弟堂兄弟,511树的定义,定义： 树是一种常用的非线性结构。 树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。 由此可以看出，树的定义是递归。,51
2、1树的定义,5. 2 二叉树,定义：二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。 二叉树也可以用递归的形式定义。即：二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,5. 2 二叉树,二叉树的5种形态：,5. 2 二叉树,完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为
3、1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,521二叉树的性质,(1) 在二叉树的第i上至多有2i-1个结点（i=1）(2) 深度为k的二叉树至多有2k-1个结点。(3) 设任何一棵二叉树中，叶结点数为n0，度为1 的结点数为n1,度为2的结点数为n2，则有：n0=n2+1(4) 具有n个结点的完全二叉树其深度为：k= log2n+1,522 二叉树的存储结构,1、顺序存储 这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。顺序存储的二叉树的定义如下：#define N 50 /*树结点的最大个数*/typedef ele
4、mtype SQTREEN;,522 二叉树的存储结构,8,4 5 6 7,2 3,1,522 二叉树的存储结构,2、链式存储,在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示：,其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，item是数据元素的内容。 类型定义为： typedef struct BTNode EntryType item; struct BTNode *Lchild
5、,*Rchlid; BTNode,*BTree;,522 二叉树的存储结构,G H,D E F,B C,A, G H , D E F ,B C,A,BT,522 二叉树的存储结构,这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。,53 遍历二叉树,531二叉树的遍历算法 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、
6、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。,531二叉树的遍历算法,按根、左子树和右子树三部分进行遍历 根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,531二叉树的遍历算法,1）先序遍历 若二叉树为空，则结束遍历操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。,531二叉树的遍历算法,（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。,531二叉树的遍历算法,（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访
7、问根结点。,531二叉树的遍历算法,G H,D E F,B C,A,先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,下面我们再给出三种遍历二叉树的方法： （1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。,D G B A E C H F,G H,D E F,B C,A,（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。,G H
8、,D E F,B C,A,（3）利用堆栈实现先序遍历 首先访问根，然后访问左子树，对每一个结点，在访问完该结点后，沿其左链访问下来，直至左链为空。堆栈中存放所有访问结点的右子结点。,531二叉树的遍历算法,2、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。,按层次遍历该二叉树的序列为： ABCDEFGH,遍历的递归算法：1.先序void PreOrder(BTree BT) if (BT) Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); ,
9、（2）中序void InOrder(BTree BT) if (BT) InOrder(BT-Lchild); Visit(BT); InOrder(BT-Rchild); ,（3）后序遍历递归算法void PostOrder(BTree BT) if (BT) PostOrder(BT-Lchild); PostOrder(BT-Rchild); Visit(BT); ,532二叉树遍历算法的应用,例： 已知一棵二叉树的前序遍历结果为ABEDCFGHIJ中序遍历结果为EBCDAFHIGJ，写出这棵二叉树后序遍历结果。,5.4线索二叉树,利用空指针，使结点更紧密连结，加快遍历速度，便于查找前驱
10、后继。,定义结点的类型如下：typedef struct thread_tree int LThread, RThread; ElemType data; struct thread_tree *LChild, *RChild; ,建立线索二叉树,if 左指针为空 then LChild 指到该树*序遍历的前一个结点 将LThread 设为1 if 右指针为空 then RChild 指到该树*序遍历的后 一个结点 将RThread 设为1,5.5二叉排序树（二叉查找树）,二叉排序树的建立1.以第一个建立元素为根结点2.依序将元素根结点比较 a. 若元素值大于根结点，则将元素往根结点右子结点移
11、动；若此右子结点为空，将元素值存入，否则就重复比较，直到找到适当之空结点为止。 b.若元素值小于根结点，则将元素往根结点左子结点移动；若此左子结点为空，将元素值存入，否则就重复比较，直到找到适当之空结点为止。,Void create_btree(int *b_tree,int *nodelist, int len) int i; int level; b_tree1=nodelist1; for(i=2;i=len;i+) level=1; while(b_treelevel!=0) if(nodelistidata=findnode) return point; else if(point-datafindnode) point=point-left; else point=point-right; ,一般树转二叉树： 步骤： 1.保留所有结点与其左子结点的链接； 2.连接所有兄弟结点； 3.打断所有结点原本与右子结点的链接； 4.将兄弟结点顺时针旋转45o。,森林转化为二叉树：,57哈夫曼树及其应用,最优二叉树，带权路径长度最短。,路径（长度）：从树中一个结点到另一个结点之间的分支，构成这两个结点之间的路径，路径上的分支数目称之为路径长度。,
