《数据结构c语言版5》由会员分享，可在线阅读，更多相关《数据结构c语言版5（51页珍藏版）》请在金锄头文库上搜索。
1、第第 五五 章章 树与二叉树树与二叉树退出退出1主要内容主要内容n n5.1树的定义及基本术语树的定义及基本术语n n5.2二叉树二叉树n n5.3遍历二叉树遍历二叉树n n5.4线索二叉树线索二叉树n n5.5二叉排序树二叉排序树n n5.7哈夫曼树哈夫曼树251树的定义及基本术语树的定义及基本术语n n5 51 11 1树的定义树的定义结点的度结点的度终端结点终端结点非终端结点非终端结点结点的层次结点的层次 树的度树的度树的深度树的深度有序树、无序树有序树、无序树森林森林 351树的定义及基本术语树的定义及基本术语n n5 51 11 1树的定义树的定义孩子、双亲孩子、双亲 子孙子孙 祖先
2、祖先兄弟兄弟堂兄弟堂兄弟4511树的定义树的定义n n定义：定义： 树是一种常用的非线性结构。树是一种常用的非线性结构。 树树是是n（n0）个结点的有限集合。若）个结点的有限集合。若n=0，则称为则称为空树空树；否则，有且仅有一个特定的；否则，有且仅有一个特定的结点被称为结点被称为根根，当，当n1时，其余结点被分成时，其余结点被分成m（m0）个互不相交的子集）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。，每个子集又是一棵树。 由此可以看出，树的定义是递归。由此可以看出，树的定义是递归。5511树的定义树的定义65. 2 二叉树二叉树n n定义：定义：定义：定义：二叉树二叉树二叉树
3、二叉树是另一种树形结构。它与树形结构是另一种树形结构。它与树形结构是另一种树形结构。它与树形结构是另一种树形结构。它与树形结构的区别是：的区别是：的区别是：的区别是： （1 1）每个结点最多有两棵子树；）每个结点最多有两棵子树；）每个结点最多有两棵子树；）每个结点最多有两棵子树； （2 2）子树有左右之分。）子树有左右之分。）子树有左右之分。）子树有左右之分。 二叉树也可以用递归的形式定义。即：二叉树二叉树也可以用递归的形式定义。即：二叉树二叉树也可以用递归的形式定义。即：二叉树二叉树也可以用递归的形式定义。即：二叉树是是是是n n（n n0 0）个结点的有限集合。当）个结点的有限集合。当）个
4、结点的有限集合。当）个结点的有限集合。当n=0n=0时，称为时，称为时，称为时，称为空二叉树；当空二叉树；当空二叉树；当空二叉树；当n0n0时，有且仅有一个结点为二叉树时，有且仅有一个结点为二叉树时，有且仅有一个结点为二叉树时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一的根，其余结点被分成两个互不相交的子集，一的根，其余结点被分成两个互不相交的子集，一的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又个作为左子集，另一个作为右子集，每个子集又个作为左子集，另一个作为右子集，每个子集又个作为左子集，另一个作为右子集，每个子集又是一个二叉树
5、。是一个二叉树。是一个二叉树。是一个二叉树。75. 2 二叉树二叉树二叉树的5种形态：85. 2 二叉树二叉树9n n 完全二叉树完全二叉树：有一棵深度为：有一棵深度为h，具有，具有n个结点的二叉树，若将它与一棵同深度的满个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为结点分别与满二叉树中编号为1n的结点位置的结点位置一一对应，则称这棵二叉树为一一对应，则称这棵二叉树为完全二叉树完全二叉树。10521二叉树的性质二叉树的性质n
6、n(1) (1) 在二叉树的第在二叉树的第在二叉树的第在二叉树的第i i上至多有上至多有上至多有上至多有2 2i-1i-1个结点（个结点（个结点（个结点（i=1i=1）n n(2) (2) 深度为深度为深度为深度为k k的二叉树至多有的二叉树至多有的二叉树至多有的二叉树至多有2 2k k-1-1个结点。个结点。个结点。个结点。n n(3) (3) 设任何一棵二叉树中，叶结点数为设任何一棵二叉树中，叶结点数为设任何一棵二叉树中，叶结点数为设任何一棵二叉树中，叶结点数为n0n0，度为，度为，度为，度为1 1 的的的的结点数为结点数为结点数为结点数为n1,n1,度为度为度为度为2 2的结点数为的结点
7、数为的结点数为的结点数为n2n2，则有：，则有：，则有：，则有：n0=n2+1n0=n2+1n n(4) (4) 具有具有具有具有n n个结点的完全二叉树其深度为：个结点的完全二叉树其深度为：个结点的完全二叉树其深度为：个结点的完全二叉树其深度为：k= k= loglog2 2n+1n+111522 二叉树的存储结构二叉树的存储结构1 1、顺序存储、顺序存储、顺序存储、顺序存储 这这这这种种种种存存存存储储储储结结结结构构构构适适适适用用用用于于于于完完完完全全全全二二二二叉叉叉叉树树树树。其其其其存存存存储储储储形形形形式式式式为为为为：用用用用一一一一组组组组连连连连续续续续的的的的存存存
8、存储储储储单单单单元元元元按按按按照照照照完完完完全全全全二二二二叉叉叉叉树树树树的的的的每每每每个个个个结结结结点编号的顺序存放结点内容。点编号的顺序存放结点内容。点编号的顺序存放结点内容。点编号的顺序存放结点内容。顺序存储的二叉树的定义如下：顺序存储的二叉树的定义如下：顺序存储的二叉树的定义如下：顺序存储的二叉树的定义如下：#define N 50 /*#define N 50 /*树结点的最大个数树结点的最大个数树结点的最大个数树结点的最大个数* */ /typedef elemtype SQTREEN;typedef elemtype SQTREEN;12522 二叉树的存储结构二叉树
9、的存储结构84 5 6 72 3113522 二叉树的存储结构二叉树的存储结构n n2 2、链式存储链式存储链式存储链式存储 在顺序存储结构中，利用编号表示元素的位置及元素在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。使用链式存储结构。 常见的二叉树结点结构如下所示：常见的二叉树结点结构如下所
10、示：14 其中，其中，Lchild和和Rchild是分别指向该结点左孩是分别指向该结点左孩子和右孩子的指针，子和右孩子的指针，item是数据元素的内容。是数据元素的内容。 类型定义为：类型定义为： typedef struct BTNode EntryType item; struct BTNode *Lchild,*Rchlid; BTNode,*BTree;15522 二叉树的存储结构二叉树的存储结构G HD E FB CA G H D E F B CABT16522 二叉树的存储结构二叉树的存储结构n n 这种存储结构的特点是寻找孩子结点容易，这种存储结构的特点是寻找孩子结点容易，这种存
11、储结构的特点是寻找孩子结点容易，这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，双亲比较困难。因此，若需要频繁地寻找双亲，双亲比较困难。因此，若需要频繁地寻找双亲，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，可以给每个结点添加一个指向双亲结点的指针域，可以给每个结点添加一个指向双亲结点的指针域，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。其结点结构如下所示。其结点结构如下所示。其结点结构如下所示。1753 遍历二叉树遍历二叉树n n5 53 31 1二叉树的遍历算法二叉树的遍历算法二叉树的遍历算法二叉
12、树的遍历算法 二叉树是一种非线性的数据结构，在对它进行操作时，二叉树是一种非线性的数据结构，在对它进行操作时，二叉树是一种非线性的数据结构，在对它进行操作时，二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个总是需要逐一对每个数据元素实施操作，这样就存在一个总是需要逐一对每个数据元素实施操作，这样就存在一个总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历操作顺序问题，由此提出了二叉树的遍历操作。所
13、谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅二叉树就是按某种顺序访问二叉树中的每个结点一次且仅二叉树就是按某种顺序访问二叉树中的每个结点一次且仅二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看一次的过程。这里的访问可以是输出、比较、更新、查看一次的过程。这里的访问可以是输出、比较、更新、查看一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。元素内容等等各种操作。元素内容等等各种操作。元素内容等等各种操作。 二叉树的遍历方式分为两大类：一类按根、左子树和二叉树的遍历方式分为两大类：一类按根、左子树和二叉树的遍历
14、方式分为两大类：一类按根、左子树和二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。右子树三个部分进行访问；另一类按层次访问。右子树三个部分进行访问；另一类按层次访问。右子树三个部分进行访问；另一类按层次访问。18531二叉树的遍历算法二叉树的遍历算法1.1.按根、左子树和右子树三部分进行遍历 根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。19531二叉树的遍历算法二叉树的遍历算法1）先序遍历先序遍历 若二叉树为空，则结束遍历操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。20531二叉树的遍历算法二叉树的遍历算法（2）中序遍历中
15、序遍历若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。21531二叉树的遍历算法二叉树的遍历算法（3）后序遍历）后序遍历若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历左子树；后序遍历右子树；后序遍历右子树；访问根结点。访问根结点。22531二叉树的遍历算法二叉树的遍历算法23G HD E FB CA先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA24下面我们再给出三种遍历二叉树的方法
16、：下面我们再给出三种遍历二叉树的方法： （1）对一棵二叉树中序遍历时，若我们将）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。是该二叉树的中序遍历序列。25D G B A E C H F G HD E FB CA26（2 2）任何一棵二叉树都可以将它的外部轮廓用一）任何一棵二叉树都可
17、以将它的外部轮廓用一）任何一棵二叉树都可以将它的外部轮廓用一）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条线绘制出来，我们将它称为二叉树的包线，这条线绘制出来，我们将它称为二叉树的包线，这条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。条包线对于理解二叉树的遍历过程很有用。条包线对于理解二叉树的遍历过程很有用。条包线对于理解二叉树的遍历过程很有用。G HD E FB CA27（3）利用堆栈实现先序遍历）利用堆栈实现先序遍历 首先访问根，然后访问左子树，对每一个结首先访问根，然后访问左子树，对每一个结点，在访问完该结点后，沿其
18、左链访问下点，在访问完该结点后，沿其左链访问下来，直至左链为空。堆栈中存放所有访问来，直至左链为空。堆栈中存放所有访问结点的右子结点。结点的右子结点。G HD E FB CA28531二叉树的遍历算法二叉树的遍历算法n n2 2、按层次遍历二叉树按层次遍历二叉树按层次遍历二叉树按层次遍历二叉树 实现方法为从上层到下层，每层中从左实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。每个结点的遍历序列。29G HD E FB CA按层次遍历该二叉树的序列
19、为：按层次遍历该二叉树的序列为： ABCDEFGH30遍历的递归算法：遍历的递归算法：1.先序先序void PreOrder(BTree BT) if (BT) Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); 31（2 2）中序）中序）中序）中序void InOrder(BTree BT)void InOrder(BTree BT) if (BT) if (BT) InOrder(BT-Lchild); InOrder(BT-Lchild); Visit(BT); Visit(BT); InOrder(BT-Rchild); InOrd
20、er(BT-Rchild); 32（3 3）后序遍历递归算法）后序遍历递归算法）后序遍历递归算法）后序遍历递归算法void PostOrder(BTree BT)void PostOrder(BTree BT) if (BT) if (BT) PostOrder(BT-Lchild); PostOrder(BT-Lchild); PostOrder(BT-Rchild); PostOrder(BT-Rchild); Visit(BT); Visit(BT); 33532二叉树遍历算法的应用二叉树遍历算法的应用例：例： 已知一棵二叉树的前序遍历结果为已知一棵二叉树的前序遍历结果为ABEDCFGH
21、IJ中序遍历结果为中序遍历结果为EBCDAFHIGJ，写出这棵二叉树后序遍历，写出这棵二叉树后序遍历结果。结果。 345.4线索二叉树线索二叉树 利用空指针，使结点更紧密连结，加快遍历利用空指针，使结点更紧密连结，加快遍历速度，便于查找前驱后继。速度，便于查找前驱后继。LThread LChildDataRChildRThread1：引线：引线0：指针：指针前驱前驱后继后继35定义结点的类型如下：定义结点的类型如下：typedef struct thread_treetypedef struct thread_tree int LThread, RThread; int LThread, RT
22、hread; ElemType data; ElemType data; struct thread_tree *LChild, *RChild; struct thread_tree *LChild, *RChild; 36建立线索二叉树建立线索二叉树 if 左指针为空左指针为空 then LChild 指到该树指到该树*序遍历的前一个结点序遍历的前一个结点 将将LThread 设为设为1 if 右指针为空右指针为空 then RChild 指到该树指到该树*序遍历的后序遍历的后 一个结点一个结点 将将RThread 设为设为137G HD E FB CA385.5二叉排序树（二叉查找树）二
23、叉排序树（二叉查找树）二叉排序树的建立二叉排序树的建立二叉排序树的建立二叉排序树的建立1. 1.以第一个建立元素为根结点以第一个建立元素为根结点以第一个建立元素为根结点以第一个建立元素为根结点2. 2.依序将元素根结点比较依序将元素根结点比较依序将元素根结点比较依序将元素根结点比较 a. a. 若元素值大于根结点，则将元素往根结点右子若元素值大于根结点，则将元素往根结点右子若元素值大于根结点，则将元素往根结点右子若元素值大于根结点，则将元素往根结点右子结点移动；若此右子结点为空，将元素值存入，结点移动；若此右子结点为空，将元素值存入，结点移动；若此右子结点为空，将元素值存入，结点移动；若此右子
24、结点为空，将元素值存入，否则就重复比较，直到找到适当之空结点为止。否则就重复比较，直到找到适当之空结点为止。否则就重复比较，直到找到适当之空结点为止。否则就重复比较，直到找到适当之空结点为止。 b.b.若元素值小于根结点，则将元素往根结点左子结若元素值小于根结点，则将元素往根结点左子结若元素值小于根结点，则将元素往根结点左子结若元素值小于根结点，则将元素往根结点左子结点移动；若此左子结点为空，将元素值存入，否点移动；若此左子结点为空，将元素值存入，否点移动；若此左子结点为空，将元素值存入，否点移动；若此左子结点为空，将元素值存入，否则就重复比较，直到找到适当之空结点为止。则就重复比较，直到找到
25、适当之空结点为止。则就重复比较，直到找到适当之空结点为止。则就重复比较，直到找到适当之空结点为止。39Void 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
26、; 42一般树转二叉树：一般树转二叉树： 步骤：步骤： 1.保留所有结点与其左子结点的链接；保留所有结点与其左子结点的链接； 2.连接所有兄弟结点；连接所有兄弟结点； 3.打断所有结点原本与右子结点的链接；打断所有结点原本与右子结点的链接； 4.将兄弟结点顺时针旋转将兄弟结点顺时针旋转45o。43森林转化为二叉树：森林转化为二叉树：森林转化为二叉树：森林转化为二叉树：4457哈夫曼树及其应用哈夫曼树及其应用最优二叉树，带权路径长度最短。最优二叉树，带权路径长度最短。路径（长度）：路径（长度）：从树中一个结点到另一个结点之间的分支，构从树中一个结点到另一个结点之间的分支，构成这两个结点之间的路径
27、，路径上的分支数目称之为路径长度。成这两个结点之间的路径，路径上的分支数目称之为路径长度。树的路径长度：树的路径长度：从树根到每一个结点的路径长度之和。从树根到每一个结点的路径长度之和。树的带权路径长度：树的带权路径长度：树中所有叶子结点的带权路径长度之和。树中所有叶子结点的带权路径长度之和。带权路径长度：带权路径长度：从根结点到该结点之间路径长度与该结点上权从根结点到该结点之间路径长度与该结点上权的乘积。的乘积。45哈夫曼算法哈夫曼算法1. 根据给定的根据给定的n个权值，对应结点构成个权值，对应结点构成n棵二棵二叉树，每棵二叉树都只有一个带权值的根叉树，每棵二叉树都只有一个带权值的根结点，其
28、左右子树均为空；结点，其左右子树均为空；2. 选取两棵结点的权值最小的树作为左右子选取两棵结点的权值最小的树作为左右子树，构造一棵新的二叉树，一般结点按左树，构造一棵新的二叉树，一般结点按左小右大排列，且置新的二叉树的根结点的小右大排列，且置新的二叉树的根结点的权值为其左右子树上根的权值之和。权值为其左右子树上根的权值之和。3. 用新的二叉树代替这两棵树。用新的二叉树代替这两棵树。4. 重复重复2、3，直到合并成一棵树。，直到合并成一棵树。46哈夫曼编码哈夫曼编码例：例：0：30%，1：20%，2：15%，3：10%，4：10%，5：5%，6：5%，7：5%47习题习题n n1. 1.假设在树
29、中，结点假设在树中，结点假设在树中，结点假设在树中，结点x x是结点是结点是结点是结点y y的双亲时的双亲时的双亲时的双亲时, ,用用用用(x,y)(x,y)来表示树边来表示树边来表示树边来表示树边. .已知一棵树已知一棵树已知一棵树已知一棵树边的集合为边的集合为边的集合为边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树用树
30、用树用树形表示法出此树，并回答下列问题：形表示法出此树，并回答下列问题：形表示法出此树，并回答下列问题：形表示法出此树，并回答下列问题： (1) (1)哪个是根结点哪个是根结点哪个是根结点哪个是根结点? ? (2) (2)哪些是叶结点哪些是叶结点哪些是叶结点哪些是叶结点? ? (3) (3)哪个是哪个是哪个是哪个是g g的双亲的双亲的双亲的双亲? ? (4) (4)哪些是哪些是哪些是哪些是g g的祖先的祖先的祖先的祖先? ? n n (5) (5)哪些是哪些是哪些是哪些是g g的孩子的孩子的孩子的孩子? ?n n (6) (6)哪些是哪些是哪些是哪些是e e的子孙的子孙的子孙的子孙? ? n
31、n (7) (7)哪些是哪些是哪些是哪些是e e的兄弟的兄弟的兄弟的兄弟? ?哪些是哪些是哪些是哪些是f f的兄弟的兄弟的兄弟的兄弟? ? n n(8)(8)结点结点结点结点b b和和和和n n的层次各是多少的层次各是多少的层次各是多少的层次各是多少? ? n n(9)(9)树的深度是多少树的深度是多少树的深度是多少树的深度是多少? ? n n(10)(10)以结点以结点以结点以结点c c为根的子树的深度是多少为根的子树的深度是多少为根的子树的深度是多少为根的子树的深度是多少? ? n n(11) (11) 树的度数是多少树的度数是多少树的度数是多少树的度数是多少? ? 48n n2.画出具有
32、3个结点的二叉树的所有不同形态。n n3.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，.nm个度为m的结点，问该树中有多少片叶子? n n4.高度为h的完全二叉树至少有多少个结点?至多有多少个结点? n n5.试找出分别满足下面条件的所有二叉树： (1)前序序列和中序序列相同； (2)中序序列和后序序列相同； (3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。49n n6.高度为h的严格二叉树至少有多少个结点?至多有多少个结点? 答：所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。 n n7.现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。n n 8.假设二叉树包含的结点数据为1，3，7，12。 n n(1)画出两棵高度最大的二叉树； n n(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。n n50 9.有一份电文中共使用有一份电文中共使用5个字符，个字符，a、b、c、d、e，出现的频率依次为，出现的频率依次为4、7、5、2、9，试画出哈夫曼树，并求出每个字符的哈夫试画出哈夫曼树，并求出每个字符的哈夫曼编码。曼编码。51
