树零基础学数据结构学习教案.pptx

会计学1树零基础树零基础(jch)学数据结构学数据结构第一页，共84页。9.1 9.1 树树n n树是一种非线性的数据结构，树中的元素之间的关系是一对(y du)多的层次关系。本节主要介绍树的定义和树的抽象数据类型。第1页/共84页第二页，共84页。9.1.1 9.1.1 树的定义树的定义(dngy)(dngy)n n树是n(n0)个结点的有限序列。其中，n=0时，称为空树。当n0时，称为非空树，满足以下条件：n n（1）有且只有一个称为根的结点。n n（2）当n1时，其余(qy)n-1个结点可以划分为m个有限集合T1，T2，Tm，且这m个有限集合不相交，其中Ti（1im）又是一棵树，称为根的子树。第2页/共84页第三页，共84页。9.1.2 9.1.2 树的逻辑树的逻辑(lu j)(lu j)表示表示n n树的逻辑表示方法(fngf)可以分为四种：树形表示法、文氏图表示法、广义表表示法和凹入表示法。第3页/共84页第四页，共84页。9.1.2 9.1.2 树的抽象数据类型树的抽象数据类型n n1数据(shj)对象集合n n2基本操作集合第4页/共84页第五页，共84页。9.2 9.2 二叉树二叉树n n在对一般树进行深入的学习之前，先学习一下一种比较简单的树二叉树。本节的主要学习内容包括(boku)二叉树的定义、基本性质及二叉树的抽象数据类型。第5页/共84页第六页，共84页。9.2.1 9.2.1 二叉树的定义二叉树的定义(dngy)(dngy)n n二叉树是由n(n0)个结点构成(guchng)的另外一种树结构。二叉树中的每个结点最多只有两棵子树，并且二叉树中的每个结点都有左右次序之分，即次序不能颠倒。第6页/共84页第七页，共84页。9.2.1 9.2.1 二叉树的定义二叉树的定义(dngy)(dngy)第7页/共84页第八页，共84页。9.2.2 9.2.2 二叉树的性质二叉树的性质(xngzh)(xngzh)n n二叉树具有以下重要的性质。二叉树具有以下重要的性质。n n性质性质1 1 在二叉树中，第在二叉树中，第m(m1)m(m1)层上至多有层上至多有2m-12m-1个结点（规定根结点为第一个结点（规定根结点为第一层）。层）。n n性质性质2 2 深度深度(shnd)(shnd)为为k(k1)k(k1)的二叉树至多有的二叉树至多有2k-12k-1个结点。个结点。n n性质性质3 3 对任何一棵二叉树对任何一棵二叉树T T，如果叶子结点总数为，如果叶子结点总数为n0n0，度为，度为2 2的结点总数为的结点总数为n2n2，则有，则有n0=n2+1n0=n2+1。n n性质性质4 4 如果完全二叉树有如果完全二叉树有n n个结点，则深度个结点，则深度(shnd)(shnd)为为 。符号。符号 表表示不大于示不大于x x的最大整数。的最大整数。n n性质性质5 5 如果完全二叉树有如果完全二叉树有n n个结点，按照从上到下，从左到右的顺序对二叉个结点，按照从上到下，从左到右的顺序对二叉树中的每个结点从树中的每个结点从1 1到到n n进行编号，则对于任意结点进行编号，则对于任意结点i i有以下性质：有以下性质：第8页/共84页第九页，共84页。9.2.2 9.2.2 二叉树的性质二叉树的性质(xngzh)(xngzh)n n（1）如果(rgu)i=1，则序号i对应的结点就是根结点，该结点没有双亲结点。n n（2）如果(rgu)2in，则序号为i的结点没有左孩子结点。n n（3）如果(rgu)2i+1n，则序号为i的结点没有右孩子结点。第9页/共84页第十页，共84页。9.2.3 9.2.3 二叉树的抽象数据类型二叉树的抽象数据类型n n1数据对象(duxing)集合n n2基本操作集合第10页/共84页第十一页，共84页。9.3 9.3 二叉树的存储表示二叉树的存储表示(biosh)(biosh)与实现与实现n n二叉树的存储(cn ch)结构有两种：顺序存储(cn ch)表示和链式存储(cn ch)表示。本节的主要学习内容包括二叉树的顺序存储(cn ch)表示、二叉树的链式存储(cn ch)表示及二叉树的基本操作实现。第11页/共84页第十二页，共84页。9.3.1 9.3.1 二叉树的顺序存储二叉树的顺序存储n n我们已经(y jing)知道，完全二叉树中每个结点的编号可以通过公式计算得到，因此，完全二叉树的存储可以按照从上到下、从左到右的顺序依次存储在一维数组中。第12页/共84页第十三页，共84页。9.3.1 9.3.1 二叉树的顺序存储二叉树的顺序存储第13页/共84页第十四页，共84页。9.3.2 9.3.2 二叉树的链式存储二叉树的链式存储(cn(cn ch)ch)n n在二叉树中，每个结点有一个双亲结点和两个孩子结点。从一棵二叉树的根结点开始，通过结点的左右孩子地址(dzh)就可以找到二叉树的每一个结点。因此二叉树的链式存储结构包括三个域：数据域、左孩子指针域和右孩子指针域。其中，数据域存放结点的值，左孩子指针域指向左孩子结点，右孩子指针域指向右孩子的结点。第14页/共84页第十五页，共84页。9.3.2 9.3.2 二叉树的链式存储二叉树的链式存储(cn(cn ch)ch)第15页/共84页第十六页，共84页。9.3.2 9.3.2 二叉树的链式存储二叉树的链式存储(cn(cn ch)ch)n n二叉链表存储(cn ch)结构的类型定义描述如下：n ntypedef struct Node/*二叉链表存储(cn ch)结构类型定义*/n nn nDataType data;/*数据域*/n nstruct Node*lchild;/*指向左孩子结点*/n nstruct Node*rchild;/*指向右孩子结点*/n n*BiTree,BitNode;第16页/共84页第十七页，共84页。9.3.3 9.3.3 二叉树的基本二叉树的基本(jbn)(jbn)运运算算n n采用二叉链表存储结构表示的二叉树的基本运算实现如下所示。以下(yxi)算法的实现保存在文件“LinkBiTree.h”中。n n（1）二叉树的初始化操作。n nvoid InitBitTree(BiTree*T)n n/*二叉树的初始化操作*/n nn n*T=NULL;n n第17页/共84页第十八页，共84页。9.3.3 9.3.3 二叉树的基本二叉树的基本(jbn)(jbn)运运算算n n（2 2）二叉树的销毁）二叉树的销毁(xiohu(xiohu)操作。操作。n nvoid DestroyBitTree(BiTree*T)void DestroyBitTree(BiTree*T)n n/*/*销毁销毁(xiohu(xiohu)二叉树操作二叉树操作*/*/n n n nif(*T)if(*T)/*/*如果是如果是非空二叉树非空二叉树*/*/n n n n if(*T)-lchild)if(*T)-lchild)n n DestroyBitTree(&(*T)-lchild);DestroyBitTree(&(*T)-lchild);n n if(*T)-rchild)if(*T)-rchild)n n DestroyBitTree(&(*T)-rchild);DestroyBitTree(&(*T)-rchild);n n free(*T);free(*T);n n *T=NULL;*T=NULL;n n n n 第18页/共84页第十九页，共84页。9.3.3 9.3.3 二叉树的基本二叉树的基本(jbn)(jbn)运运算算n n（3 3）创建二叉树操作。）创建二叉树操作。n nvoid CreateBitTree(BiTree*T)void CreateBitTree(BiTree*T)n n/*/*递归创建二叉树递归创建二叉树*/*/n n n n DataType ch;DataType ch;n n scanf(“%c”,&ch);scanf(“%c”,&ch);n n if(ch=#)if(ch=#)n n *T=NULL;*T=NULL;n n else elsen n n n *T=(BiTree)malloc(sizeof(BitNode);*T=(BiTree)malloc(sizeof(BitNode);/*/*生成根结生成根结点点(ji di(ji di n)*/n)*/n n if(!(*T)if(!(*T)n n exit(-1);exit(-1);n n (*T)-data=ch;(*T)-data=ch;n n CreateBitTree(&(*T)-lchild);CreateBitTree(&(*T)-lchild);/*/*构造左子构造左子树树*/*/n n CreateBitTree(&(*T)-rchild);CreateBitTree(&(*T)-rchild);/*/*构造右子构造右子树树*/*/n n n n 第19页/共84页第二十页，共84页。9.3.3 9.3.3 二叉树的基本二叉树的基本(jbn)(jbn)运运算算n n（4）二叉树的左插入(ch r)操作。n nint InsertLeftChild(BiTree p,BiTree c)n n/*二叉树的左插入(ch r)操作*/n nn n if(p)/*如果指针p不空*/n n n n c-rchild=p-lchild;/*p的原来的左子树成为c的右子树*/n n p-lchild=c;/*子树c作为p的左子树*/n n return 1;n n n n return 0;n n第20页/共84页第二十一页，共84页。9.3.3 9.3.3 二叉树的基本二叉树的基本(jbn)(jbn)运运算算n n（5）二叉树的右插入操作。n nint InsertRightChild(BiTree p,BiTree c)n n/*二叉树的右插入操作*/n nn n if(p)/*如果指针p不空*/n n n n c-rchild=p-rchild;/*p的原来(yunli)的右子树作为c的右子树*/n n p-rchild=c;/*子树c作为p的右子树*/n n return 1;n n n n return 0;n n第21页/共84页第二十二页，共84页。9.3.3 9.3.3 二叉树的基本二叉树的基本(jbn)(jbn)运运算算n n（6）返回二叉树结点的指针操作。n n（7）返回二叉树的结点的左孩子元素(yun s)值操作。n n（8）返回二叉树的结点的右孩子元素(yun s)值操作。n n（9二叉树的左删除操作。n n（10）二叉树的右删除操作。第22页/共84页第二十三页，共84页。9.4 9.4 二叉树的遍历二叉树的遍历(bin l)(bin l)n n在二叉树的应用中，常常需要对二叉树中每个结点进行访问，即二叉树的遍历。本节的主要学习内容(nirng)包括二叉树的先序遍历、二叉树的中序遍历及二叉树的后序遍历。第23页/共84页第二十四页，共84页。9.4.1 9.4.1 二叉树遍历二叉树遍历(bin l)(bin l)的的定义定义n n二叉树的遍历，即按照(nzho)某种规律对二叉树的每个结点进行访问，使得每个结点仅被访问一次的操作。这里的访问，可以是对结点的输出、统计结点的个数等。n n二叉树的遍历过程其实也是将二叉树的非线性序列转换成一个线性序列的过程。二叉树是一种非线性的结构，通过遍历二叉树，按照(nzho)某种规律对二叉树中的每个结点进行访问，且仅访问一次，得到一个顺序序列。第24页/共84页第二十五页，共84页。9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历(bin(bin l)l)n n二叉树的先序遍历的递归定义如下：n n如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下(yxi)操作：n n（1）访问根结点。n n（2）先序遍历左子树。n n（3）先序遍历右子树。第25页/共84页第二十六页，共84页。9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历(bin(bin l)l)n n最后(zuhu)得到结点A的左子树先序序列：B、D、G、E、H、I、C、F、J。第26页/共84页第二十七页，共84页。9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历(bin(bin l)l)n nvoid PreOrderTraverse(BiTree T)n n/*先序遍历(bin l)二叉树的递归实现*/n nn n if(T)/*如果二叉树不为空*/n n n n printf(“%2c”,T-data);/*访问根结点*/n n PreOrderTraverse(T-lchild);/*先序遍历(bin l)左子树*/n n PreOrderTraverse(T-rchild);/*先序遍历(bin l)右子树*/n n n n第27页/共84页第二十八页，共84页。9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历(bin(bin l)l)n n先序遍历(bin l)的非递归实现第28页/共84页第二十九页，共84页。9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历(bin(bin l)l)n n二叉树的中序遍历的递归定义如下：n n如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下(yxi)操作：n n（1）中序遍历左子树。n n（2）访问根结点。n n（3）中序遍历右子树。第29页/共84页第三十页，共84页。9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历(bin l)(bin l)n n二叉树的中序序列二叉树的中序序列(xli)(xli)为：为：DD、GG、B B、HH、E E、I I、A A、F F、J J、C C。第30页/共84页第三十一页，共84页。9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历(bin(bin l)l)n nvoid InOrderTraverse(BiTree T)n n/*中序遍历二叉树的递归实现*/n nn n if(T)/*如果(rgu)二叉树不为空*/n nn nInOrderTraverse(T-lchild);/*中序遍历左子树*/n n printf(“%2c”,T-data);/*访问根结点*/n n InOrderTraverse(T-rchild);/*中序遍历右子树*/n n n n第31页/共84页第三十二页，共84页。9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历(bin(bin l)l)n n二叉树的中序遍历(bin l)非递归算法实现 第32页/共84页第三十三页，共84页。9.4.4 9.4.4 二叉树的后序二叉树的后序(hu x)(hu x)遍历遍历n n二叉树的后序遍历(bin l)的递归定义如下：n n如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：n n（1）后序遍历(bin l)左子树。n n（2）后序遍历(bin l)右子树。n n（3）访问根结点。第33页/共84页第三十四页，共84页。9.4.4 9.4.4 二叉树的后序二叉树的后序(hu(hu x)x)遍历遍历n n二叉树的后序二叉树的后序(hu x)(hu x)序列为：序列为：GG、DD、HH、I I、E E、B B、J J、F F、C C、A A。第34页/共84页第三十五页，共84页。9.4.4 9.4.4 二叉树的后序二叉树的后序(hu x)(hu x)遍历遍历n nvoid PostOrderTraverse(BiTree T)n n/*后序遍历二叉树的递归实现*/n nn n if(T)/*如果二叉树不为空*/n nn nPostOrderTraverse(T-lchild);/*后序遍历左子树*/n n PostOrderTraverse(T-rchild);/*后序遍历右子树*/n nprintf(“%2c”,T-data);/*访问(fngwn)根结点*/n n n n第35页/共84页第三十六页，共84页。9.4.4 9.4.4 二叉树的后序二叉树的后序(hu x)(hu x)遍历遍历n n后序遍历(bin l)的非递归实现第36页/共84页第三十七页，共84页。9.5 9.5 二叉树的遍历二叉树的遍历(bin l)(bin l)的的应用举例应用举例n n二叉树的遍历应用(yngyng)非常广泛，本节主要通过几个例子来说明二叉树遍历的典型应用(yngyng)。本节的主要学习内容包括利用二叉树的遍历思想，进行二叉树的创建、二叉树的输出、二叉树的结点的计数。第37页/共84页第三十八页，共84页。9.5.1 9.5.1 二叉树的创建二叉树的创建(chungjin)(chungjin)n n例9_1 编写算法，创建一个如图9.16所示的二叉树，并按照(nzho)先序遍历、中序遍历和后序遍历的方式输出二叉树的每个结点的值。n n1创建二叉树n n2测试代码部分第38页/共84页第三十九页，共84页。9.5.2 9.5.2 二叉树的输出二叉树的输出(shch)(shch)n n二叉树的打印输出方式，除了(ch le)按照先序遍历、中序遍历和后序遍历的输出方式外，还有按照层次输出和树状输出的方式。下面具体介绍这两种输出方式的实现算法。第39页/共84页第四十页，共84页。9.5.2 9.5.2 二叉树的输出二叉树的输出(shch)(shch)n n例9_2 创建(chungjin)一个二叉树，并按照层次输出二叉树的每个结点，并按照树状打印二叉树。例如，一棵二叉树如图9.22所示，按照层次输出的序列为：A、B、C、D、E、F、G、H、I，按照树状输出的二叉树如图9.23所示。n n1按层次输出二叉树的结点n n2按树状打印二叉树n n3测试代码部分第40页/共84页第四十一页，共84页。9.5.2 9.5.2 二叉树的输出二叉树的输出(shch)(shch)第41页/共84页第四十二页，共84页。9.5.2 9.5.2 二叉树的输出二叉树的输出(shch)(shch)n n按层次(cngc)输出结点程序流程图第42页/共84页第四十三页，共84页。9.5.3 9.5.3 二叉树的计数二叉树的计数(j sh)(j sh)n n二叉树的遍历也常常用来对二叉树进行计数。下面通过实例说明统计二叉树的叶子结点数目(shm)、非叶子结点数目(shm)等应用。n n1统计二叉树的叶子结点个数n n2统计二叉树的非叶子结点个数n n3计算二叉树的深度n n4测试代码部分第43页/共84页第四十四页，共84页。9.5.3 9.5.3 二叉树的计数二叉树的计数(j sh)(j sh)n n例9_3 创建一个二叉树，计算二叉树的叶子结点数目、非叶子结点数目和二叉树的深度(shnd)。例如，图9.26所示的二叉树的叶子结点数目为5个，非叶子结点数目为7个，深度(shnd)为5。第44页/共84页第四十五页，共84页。9.5.3 9.5.3 二叉树的计数二叉树的计数(j sh)(j sh)n n1统计二叉树的叶子(y zi)结点个数第45页/共84页第四十六页，共84页。9.5.3 9.5.3 二叉树的计数二叉树的计数(j sh)(j sh)n n2统计二叉树的非叶子(y zi)结点个数第46页/共84页第四十七页，共84页。9.5.3 9.5.3 二叉树的计数二叉树的计数(j sh)(j sh)n n3计算(j sun)二叉树的深度第47页/共84页第四十八页，共84页。9.6 9.6 二叉树的线索二叉树的线索(xin su)(xin su)化化n n在二叉树中，采用二叉链表作为存储结构，只能(zh nn)找到结点的左孩子结点和右孩子结点，不能找到该结点的直接前驱结点和后继结点信息。要找到结点的直接前驱或者直接后继，必须对二叉树进行遍历，第48页/共84页第四十九页，共84页。9.6.1 9.6.1 二叉树的线索二叉树的线索(xin(xin su)su)化定义化定义n n为了能够在二叉树的遍历过程中，直接能够找到结点的直接前驱(qinq)结点或者直接后继结点，可以在结点的定义中再增加两个指针域：一个用来指示结点的前驱(qinq)，另一个用来指向结点的后继。n n在二叉链表的存储结构中，具有n个结点的二叉链表有n+1个空指针域（根据二叉树的分支特点可以证明）。由此，可以利用这些空指针域存放结点的直接前驱(qinq)和直接后继的信息。第49页/共84页第五十页，共84页。9.6.1 9.6.1 二叉树的线索二叉树的线索(xin(xin su)su)化定义化定义第50页/共84页第五十一页，共84页。9.6.1 9.6.1 二叉树的线索二叉树的线索(xin(xin su)su)化定义化定义n ntypedef enum Link,ThreadPointerTag;/*Link=0表示指向孩子结点，Thread=1表示指向前驱结点或后继结点*/n ntypedef struct Node/*线索二叉树存储结构类型定义*/n nn nDataType data;/*数据(shj)域*/n nstruct Node*lchild,rchild;/*指向左孩子结点的指针和右孩子结点的指针*/n nPointerTag ltag,rtag;/*标志域*/n n*BiThrTree,BiThrNode;第51页/共84页第五十二页，共84页。9.6.2 9.6.2 二叉树的线索二叉树的线索(xin(xin su)su)化化n n二叉树的线索化就是利用二叉树中结点的空指针(zhzhn)域表示结点的前驱或后继信息。而要得到结点的前驱信息和后继信息，需要对二叉树进行遍历，同时将结点的空指针(zhzhn)域修改为其直接前驱或直接后继信息。因此，二叉树的线索化就是对二叉树的遍历过程。第52页/共84页第五十三页，共84页。9.6.2 9.6.2 二叉树的线索二叉树的线索(xin(xin su)su)化化第53页/共84页第五十四页，共84页。9.6.3 9.6.3 线索线索(xin su)(xin su)二叉树二叉树的遍历的遍历n n1查找指定结点的中序直接前驱n n2查找指定结点的中序直接后继n n3中序遍历(bin l)线索二叉树第54页/共84页第五十五页，共84页。9.6.4 9.6.4 线索二叉树的应用线索二叉树的应用(yngyng)(yngyng)举例举例n n例9_4 建立(jinl)如图9.30所示的二叉树，并将其中序线索化。任给一个结点，找到结点的中序前驱和中序后继。例如，结点D的中序直接前驱是G，其中序直接后继是A。n n1二叉树的线索化n n2测试代码部分第55页/共84页第五十六页，共84页。9.7 9.7 树、森林树、森林(snln)(snln)与二叉与二叉树树n n树、森林和二叉树本身都是树的一种(y zhn)，它们之间是可以相互转换的。本节的主要学习内容包括树的存储结构、森林与二叉树的转换、树与森林的遍历。第56页/共84页第五十七页，共84页。9.7.1 9.7.1 树的存储树的存储(cn ch)(cn ch)结构结构n n1双亲(shungqn)表示法第57页/共84页第五十八页，共84页。9.7.1 9.7.1 树的存储树的存储(cn ch)(cn ch)结构结构n n树的双亲(shungqn)表示法存储表示描述如下。n n#define MaxSize 200n ntypedef struct PNode/*双亲(shungqn)表示法的结点定义*/n nn n DataType data;n n int parent;/*指示结点的双亲(shungqn)*/n nPNode;n ntypedef struct/*双亲(shungqn)表示法的类型定义*/n nn n PNode nodeMaxSize;n n int num;/*结点的个数*/n nPTree;第58页/共84页第五十九页，共84页。9.7.1 9.7.1 树的存储树的存储(cn ch)(cn ch)结构结构n n2孩子(hi zi)表示法第59页/共84页第六十页，共84页。9.7.1 9.7.1 树的存储树的存储(cn ch)(cn ch)结构结构n n树的孩子表示法的类型定义如下。树的孩子表示法的类型定义如下。n n#define MaxSize 200#define MaxSize 200n ntypedef struct CNodetypedef struct CNode/*/*孩子结点的类型定义孩子结点的类型定义*/*/n n n n int child;int child;n n struct CNode*next;struct CNode*next;/*/*指向指向(zh(zh xin xin)下一个结下一个结点点*/*/n nChildNode;ChildNode;n ntypedef structtypedef struct/*n/*n个结点数个结点数据与孩子链表的指针构成一个结构据与孩子链表的指针构成一个结构*/*/n n n n DataType data;DataType data;n n ChildNode*firstchild;ChildNode*firstchild;/*/*孩子链表的指针孩子链表的指针*/*/n nDataNode;DataNode;n ntypedef structtypedef struct/*/*孩子表示孩子表示法类型定义法类型定义*/*/n n n nDataNode nodeMaxSize;DataNode nodeMaxSize;n nint num,root;int num,root;/*/*结点的个结点的个数，根结点在顺序表中的位置数，根结点在顺序表中的位置*/*/n nCTree;CTree;第60页/共84页第六十一页，共84页。9.7.1 9.7.1 树的存储树的存储(cn ch)(cn ch)结构结构n n3孩子(hi zi)兄弟表示法第61页/共84页第六十二页，共84页。9.7.1 9.7.1 树的存储树的存储(cn ch)(cn ch)结构结构n n树的孩子(hi zi)兄弟表示法的类型定义如下。n ntypedef struct CSNode/*孩子(hi zi)兄弟表示法的类型定义*/n nn n DataType data;n n struct CSNode*firstchild,*nextsibling;/*指向第一个孩子(hi zi)和下一个兄弟*/n nCSNode,*CSTree;第62页/共84页第六十三页，共84页。9.7.2 9.7.2 树转换树转换(zhunhun)(zhunhun)为二为二叉树叉树n n从树的孩子兄弟表示和二叉树的二叉链表表示来看，它们在物理上的存储方式是相同的，也就是说，从它们的相同的物理结构可以得到一棵树，也可以得到一棵二叉树。因此，树与二叉树存在着一种对应关系。n n树中双亲结点的孩子结点是无序的，二叉树中的左右孩子是有序的。按照以下步骤，可以将一棵树转换为对应的二叉树。n n（1）在树中的兄弟结点之间加一条连线。n n（2）在树中，只保留双亲结点与第一个孩子结点之间的连线，将双亲结点与其它孩子结点的连线删除。n n（3）将树中的各个(gg)分支，以某个结点为中心进行旋转，子树以根结点成对称形状。第63页/共84页第六十四页，共84页。9.7.2 9.7.2 树转换树转换(zhunhun)(zhunhun)为二为二叉树叉树第64页/共84页第六十五页，共84页。9.7.2 9.7.2 树转换树转换(zhunhun)(zhunhun)为二为二叉树叉树第65页/共84页第六十六页，共84页。9.7.3 9.7.3 森林森林(snln)(snln)转换为二转换为二叉树叉树n n森林是由若干(rugn)棵树组成的集合，树可以转换为二叉树，那么森林也可以转换为对应的二叉树。森林转换为对应的二叉树的步骤如下：n n（1）把森林中的所有树都转换为对应的二叉树。n n（2）从第二棵树开始，将转换后的二叉树作为前一棵树根结点的右孩子，插入到前一棵树中。然后将转换后的二叉树进行相应的旋转。第66页/共84页第六十七页，共84页。9.7.3 9.7.3 森林森林(snln)(snln)转换为二转换为二叉树叉树第67页/共84页第六十八页，共84页。9.7.4 9.7.4 二叉树转换二叉树转换(zhunhun)(zhunhun)为树和森林为树和森林n n二叉树转换为树或者森林，就是将树和森林转换为二叉树的逆过程。将一棵二叉树转换为树或者森林的步骤如下：n n（1）在二叉树中，将某结点的所有右孩子结点、右孩子的右孩子结点都与该结点的双亲结点用线条连接。n n（2）删除掉二叉树中双亲结点与右孩子结点的原来的连线(lin xin)。n n（3）调整转换后的树或森林，使结点的所有孩子结点处于同一层次。第68页/共84页第六十九页，共84页。9.7.4 9.7.4 二叉树转换二叉树转换(zhunhun)(zhunhun)为树和森林为树和森林第69页/共84页第七十页，共84页。9.7.5 9.7.5 树和森林树和森林(snln)(snln)的遍的遍历历n n1树的遍历(bin l)n n2森林的遍历(bin l)第70页/共84页第七十一页，共84页。9.8 9.8 哈夫曼树哈夫曼树n n哈夫曼树，也称最优二叉树。它是一种带权路径长度最短的树，应用非常广泛。本节的主要学习内容包括哈夫曼树的定义(dngy)、哈夫曼编码及哈夫曼编码算法的实现。第71页/共84页第七十二页，共84页。9.8.1 9.8.1 哈夫曼树的定义哈夫曼树的定义(dngy)(dngy)n n1路径(ljng)和路径(ljng)长度n n2树的带权路径(ljng)长度n n3哈夫曼树第72页/共84页第七十三页，共84页。9.8.1 9.8.1 哈夫曼树的定义哈夫曼树的定义(dngy)(dngy)n n例如，假设给定一组权值1,3,6,9，按照哈夫曼构造的算法(sun f)对集合的权重构造哈夫曼树的过程如图9.42所示。第73页/共84页第七十四页，共84页。9.8.2 9.8.2 哈夫曼编码哈夫曼编码(bin m)(bin m)n n哈夫曼编码常应用在数据通信中，在数据传送时，需要将字符转换为二进制的字符串。n n在传送电文时，希望电文的代码尽可能的短。如果按照每个字符进行长度不等进行编码，将出现频率高的字符采用(ciyng)尽可能短的编码，则电文的代码长度就会减少。第74页/共84页第七十五页，共84页。9.8.3 9.8.3 哈夫曼编码哈夫曼编码(bin m)(bin m)算算法的实现法的实现n n下面利用哈夫曼编码的设计思想，通过一个实例实现哈夫曼编码的算法实现。n n例9_5 假设一个字符序列为A,B,C,D，对应的权重(qun zhn)为1,3,6,9。设计一个哈夫曼树，并输出相应的哈夫曼编码。第75页/共84页第七十六页，共84页。9.8.3 9.8.3 哈夫曼编码哈夫曼编码(bin m)(bin m)算算法的实现法的实现n ntypedef struct/*哈夫曼树类型定义*/n nn nunsigned int weight;n nunsigned int parent,lchild,rchild;n nHTNode,*HuffmanTree;n ntypedef char*HuffmanCode;/*存放(cnfng)哈夫曼编码*/第76页/共84页第七十七页，共84页。9.8.3 9.8.3 哈夫曼编码算法哈夫曼编码算法(sun(sun f)f)的实现的实现n n1哈夫曼编码的实现(shxin)n n2查找权值最小和次小的两个结点n n3测试代码部分第77页/共84页第七十八页，共84页。9.9 9.9 树与二叉树的应用树与二叉树的应用(yngyng)(yngyng)举例举例n n本节将通过几个(j)具体实例来说明二叉树与树的使用。本节的主要学习内容包括相似二叉树、由二叉树的先序和中序序列确定一棵二叉树、树的孩子兄弟表示法。第78页/共84页第七十九页，共84页。9.9.1 9.9.1 相似相似(xin s)(xin s)二叉树二叉树n n相似二叉树指的是二叉树的结构相似。假设存在(cnzi)两棵二叉树T1和T2，T1和T2都是空二叉树或者T1和T2都不为空树，且T1和T2的左、右子树的结构分别相似。则称T1和T2是相似二叉树。第79页/共84页第八十页，共84页。9.9.2 9.9.2 由先序和中序、中序和由先序和中序、中序和后序后序(hu x)(hu x)确定二叉树确定二叉树n n1由先序序列和中序序列确定(qudng)一棵二叉树n n2由中序序列和后序序列确定(qudng)一棵二叉树n n3程序举例第80页/共84页第八十一页，共84页。9.9.2 9.9.2 9.9.2 9.9.2 由先序和中序、中序和后序由先序和中序、中序和后序由先序和中序、中序和后序由先序和中序、中序和后序(hu x)(hu x)(hu x)(hu x)确定二叉树确定二叉树确定二叉树确定二叉树第81页/共84页第八十二页，共84页。9.9.3 9.9.3 树的孩子兄弟链表应用树的孩子兄弟链表应用(yngyng)(yngyng)举例举例n n例9_7 利用孩子兄弟表示法创建一棵树，对树进行层次遍历(bin l)、先序遍历(bin l)，并求出树的深度。n n1孩子兄弟链表的相关操作n n2测试代码部分第82页/共84页第八十三页，共84页。9.10 9.10 小结小结(xioji)(xioji)n n本章主要介绍了一种非线性的数据结构树。n n树在数据结构中占据着非常重要的地位，树反映的是一种层次结构的关系。在树中，每个结点只允许(ynx)有一个直接前驱结点，允许(ynx)有多个直接后继结点，结点与结点之间是一种一对多的关系。n n树的定义是递归的。一棵树或者为空，或者是由m棵子树T1，T2，Tm组成，这m棵子树又是由其它子树构成。树中的孩子结点没有次序之分，是一种无序树。第83页/共84页第八十四页，共84页。