数据结构第6章 树和二叉树.ppt

1、第六章 树和二叉树,内容,树的类型 二叉树定义 二叉树的存储结构 二叉树的遍历 线索二叉树 树和森林表示方法 树和森林的遍历 哈夫曼树与哈夫曼编码,6.1 树的类型,数据对象D D具有相同的数据元素集合 数据关系 若D为空集，则树为空树，否则： D中存在唯一称位根的数据元素root 当n1时，其余结点可分为m个不相交的有限集T1,T2,.Tm,其中每一子集本身又是一棵符合本定义的树，称为根的子树。,基本术语,结点：数据元素+若个指向子树的分支 结点的度：分支的个数 树的度：树中所有结点中度的最大值 叶结点：度为0的结点 分支结点：度大于0的结点 从根到结点的路径：由根结点所经分支和结点构成 孩

2、子结点，双亲结点，兄弟结点，祖先结点，子孙结点,结点的层次： 根结点层次为1，第k层结点的子树根结点的层次为k+1 例：F在第3层，它的根B在第2层 树的深度 树中叶子结点所在的最大层次(上述树深=4) 森林：数棵互不想交的树集合 任何一棵非空树是一个二元组 Tree=(root,F) root 根结点 F 子树森林（F=T1Tm）其中Ti=(rooti,Fi),森林,H,K,深度：4,有向树,有确定的根 树根和子树根之间是有向关系,A,B,E,F,C,D,第1层,有序树和无序树,子树之间是否存在次序关系 不考虑子树次序，则下列树是相同的,基本操作,查找 插入 删除,查找,root(t)/返回

3、根结点指针 value(t,cur_e) /返回当前结点值 parent(t,cur_e) /返回当前结点的双亲 leftChild(t,cur_e) /返回当前结点的左孩子 rightSibLing(t,cur_e)/兄弟 treeEmpty(t) treeDepth(t) traverseTree(t,visit();,插入,initTree( SqBiTree bt;,例：seBiTree.cpp void createBiTree(SqBiTree bt,int *list) / 将list=9,6,3,8,5,2,9,4,7,10 建立一棵二叉树 int i,level; bt1=l

4、ist1; /第1 个元素为根 for (i=2;i=list0;+i)/数组元素个数在list0 level=1; while (btlevel!=0) /从第1层开始 if (listibtlevel) /比根小放在左子树 level *=2; else /否则放在右子树 level = level*2+1; btlevel=listi; ,二叉树的链式存储表示,二叉链表 三叉链表 双亲链表 线索链表 链结点结构 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode, *BiTree;,

5、二叉链表,BiTree t;t-data=A;t-lchild=pb;t-rchild=pc,t,pb,pc,三叉链表,结点多了一个指向父结点的指针,A,B,C,D,*parent data *lchild *rchild,双亲链表,分别有指向双亲指针和判别左右孩子的数据区 例：B结点位置1，指向双亲位置0，是双亲的左孩子,0,1,2,3,线索链表,利用结点空闲的链接域存指向前驱和后继的指针,二叉链表基本操作,createBiTree( preOrder(结点左子树); preOrder(结点右子树); 中序和后序遍历 inOrder(t) postOrder(t) 例：biTreeTrave

6、rse.cpp,中序遍历的非递归描述,inOrder(t) initStack(s); p=t; while (p|!stackEmpty(s) if (p) push(s,p);p=p-lchild; /访问左孩子 else pop(s,p); print(p-data); /访问结点 p=p-rchild; /访问右孩子 ,说明,栈的数据类型改放二叉树指针 typedef struct BiTNode /二叉树结点类型 TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; typedef struct LNode

7、/链栈结点类型 BiTree data; /结点数据放二叉树结点指针 struct LNode *next; LNode,*StackPtr; 例：InOrder.cpp,从先序遍历和中序遍历构建,例： 先序遍历：A BD CEF 中序遍历：BD A ECF,应用1,建立二叉链表（先序） 结点，左子树，右子树：用字符串表示 空树：“.” 根：”A.” 树：“AB.D.CE.F.”,A B . D . . C E . . F . .,叶子结点数：3 深度：3,算法（createBiTree.cpp）,Status createBiTree(BiTree ,应用2：统计二叉树叶子的数目,Statu

8、s countBiLeaf(BiTree t,int /递归中引用同一变量可以使用参数或函数值 例：countBiLeaf.cpp,应用3：求二叉树的高度,int depthBiTree(BiTree t) int ldepth,rdepth,val; if (!t) val=0; /空树高度为0 else ldepth=depthBiTree(t-lchild); rdepth=depthBiTree(t-rchild); val =1 + getMax(ldepth,rdepth); return val; 例：depthBiTree.cpp,应用4：复制二叉树copyBiTree.cpp

9、,Status copyBiTree(BiTree t,BiTree ,应用5：表达式计算,二叉树表示的一个表达式，例： 先序遍历：+35 对应表达式的前缀表示 中序遍历： 3+5 对应表达式的中缀表示 后序遍历：35+ 对应表达式的后缀表示,+,3,5,例,（a+b)*c-d/e 先序：-*+abc/de 中序： a+b*c-d/e(与原有出入) 后序： ab+c*de/-,先序遍历计算算法,int calculateBiTree(BiTree t) 如果是叶结点 return (t-data); 否则 op1=calculateBiTree(t-lchild); op2=calculate

10、BiTree(t-rchild); return getValue(t-data,op1,op2); ,例：计算：4*8+6/2,前缀式：+*48/62 二叉树的前序+*4.8./6.2.(数字是叶子无子树) 后缀式：48*62/+ calExpression.cpp 前缀式输入，先序遍历计算,6.5 线索二叉树,遍历二叉树得结果：结点的线性序列 指向线性序列的前驱和后继的指针称线索 包含的线索存储结构为“线索链表” 相应的二叉树为“线索二叉树” 线索二叉树有先序线索二叉树、中序线索二叉树和后序线索二叉树,利用空链域存放前驱和后继指针 如先序遍历的指针表示,叶子结点有二个空域 分子度为1的有一

11、个空域,先序遍历：ABCDEFGHI 先序线索树找后继容易，找前序困难，如找结点F的前驱需知道双亲E及其左孩子,中序线索二叉树,找结点前驱方法：1）结点无左孩子，就是线索，指向的结点为前驱，如结点6的前驱是结点52）结点有左孩子，则左孩子的右孩子，一直找右孩子，至线索为止，如结点4的前驱是结点3找结点后继方法：1）结点无右孩子，线索指的就是后继，如结点6的后继就是结点72）结点有右孩子，则右孩子的左孩子，一直找左孩子，至线索为止，如结点5的后继是结点6,线索二叉树结点结构,链表结构线索二叉树有一个头结点,iTag=0 lchild指左孩子 iTag=1 lchild指线索,1 1,二叉树为空的

12、头结点,0 1,二叉树不空的头结点,root,最后结点,数据类型,typedef enum Link,Thread PointTag; typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; PointTag lTag,rTag; /可定义为整数 BiThrNode,*BiThrTree;,线索二叉树建立(线索化),线索二叉树常用于中序遍历 算法 遍历二叉树 访问当前结点，左子树是否空，是 设左标志为1，指针指向前驱 右子树是否空，是 设右标志为1，指针指向后继,算法,Status inOrderTh

13、reading(BiThrTree 线索化右子树 ,thr,t,Status inOrderThreading(BiThrTree ,1 1,0 1,thr,thr,0 1,pre,t,中序遍历,void inThreading(BiThrTree /线索化右子树 例：inOrderThreading.cpp,Status inOrderTraverse_Thr(BiThrTree t) /t是线索头结点 /中序遍历线索树 BiThrTree p; p=t-lchild; /指向根结点 while (p!=t) while (p-lTag=Link) p=p-lchild; /到无左孩子 pr

14、intf(%c ,p-data); while (p-rTag=Thread 遍历时间复杂度O(n),5,4,6,8,7,1,3,2,0 1,遍历路线 (红线),先找头,t,遍历中序线索二叉树,找前驱 若左标志1，即前驱；否则 访问左子树，访问的最后1个结点是前驱 找后继 若右标志1，即后继；否则 遍历右子树，访问的第1个结点是后继,6.6 树和森林,树的三种存储结构,双亲表示 孩子链表 孩子兄弟链表,双亲表示,typedef struct int data; int parent; PTNode; typedef struct PTNode nodesMAX; int r,n;/根位置和结点

15、数目 PTree;,孩子链表,typedef struct CTNode int child; struct CTNode *next; *ChildPtr; typedef struct TElemType data; ChildPtr firstChild; CTBox; typedef struct CTBox nodesMAX; int r,n; CTree;,孩子兄弟链表,typedef struct CSNode int data; struct CSNode *firstChild, *nextSibling; CSNode,*CSTree;,说明,孩子兄弟链表和二叉链表相似,但

16、含义不同 根无右子树 利于将二叉树算法运用于树,森林,树去掉根结点就是森林,A,B,G,D,H,I,J,C,E,F,森林和二叉树关系,森林转换成二叉树F=T1,T2,Tn B=root,LBT,RBT 若F=,则B=;否则 第一棵树的根ROOT(T1)转换成二叉树的根root,子树森林转换成左子树LBT;森林T2,.,Tn转换成RBT 二叉树转换成森林 若B=则F=;否则 二叉树的根root转换成第一棵树的根T1; B的左子树LBT转换成T1树结点(t11,t12,t1m) B的右子树RBT转换成森林(T2,T3,Tn),森林转换成二叉树,A,B,G,D,H,I,J,C,E,F,E,F,G,H

17、,I,J,G,H,I,J,森林转换成二叉树规则,若F=，则B=; 否则 由ROOT(T1);对应得到Node(root); 由（t11,t12,.,t1m） 对应得到LBT 由 (T2,T3,.,Tn) 对应得到RBT,二叉树转换成森林,二叉树转换成森林规则,若B=，则F=; 否则 由Node(root)对应得到ROOT(T1); 由LBT对应得到（t11,t12,.,t1m）； 由RBT对应得到(T2,T3,.,Tn),6.7 树和森林的遍历,树的遍历,先根遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 后根遍历 若树不空，则先依次遍历各棵子树 ，然后访问根结点。 层次遍历 若树

18、不空，则自上而下、自左而右访问树中每个结点,树先根遍历,ABEFCDGHIJK 先树根，再子树,A,B,D,C,E,F,G,H,I,K,J,二叉树先序遍历ABEFCDGHIJK,树后根遍历,EFBCIJKHGDA 先子树，后树根,二叉树中序遍历EFBCIJKHGDA,层次遍历,ABCDEFGHIJK,树的先根遍历等同于二叉树的先序遍历 树的后根遍历等同于二叉树的中序遍历 树无中根遍历,森林的遍历,森林由三部分组成 森林中第一棵树的根结点 森林中第一棵树的子树森林 森林中其它树构成的森林,森林的先序遍历,先序遍历（依次从左到右对森林中的每一棵树进行先根遍历） 若森林不空，则 访问森林中第1棵树的

19、根结点 先序遍历森林中第1棵树子树森林 先序遍历森林中其他树构成的森林,森林的先序遍历和二叉树的先序遍历,第1棵树的根 第1棵树的子树 其他树 ABCDEFGHIJ,二叉树的先序遍历ABCDEFGHIJ,森林的中序遍历,中序遍历（依次从左到右对森林中的每一棵树进行后根遍历） 若森林不空，则 中序遍历森林中第1棵树的子树森林 访问森林中第1棵树的根结点 中序遍历森林中其他树构成的森林,森林的中序遍历和二叉树的中序遍历,第1棵树的子树 第1棵树的根 其他树 BCDAFEHJIG,二叉树的中序遍历BCDAFEHJIG,森林的先序遍历等同于二叉树的先序遍历 森林的中序遍历等同于二叉树的中序遍历,例1：

20、建树的存储结构算法,输入有序对建立树 （#，A） （A，B） （A，C） （A，D） （C，E） （C，F） （F，G） （#，#）,A,B,E,C,F,D,G,每输入一有序对，结点进队列，为了在输入下一有序对时寻找父结点，当有序对的父结点发生变化，父结点出队列。,void createTree(CSTree / createTree.cpp,树遍历算法的应用,例2：求树的深度的算法 int treeDepth(CSTree t) if (!t) return 0; else h1=treeDepth(t-firstChild);/子树 h2=treeDepth(t-nextSibling);

21、/兄弟 return (max(h1+1,h2); ,例3：输出树中所有从根到叶子的路径的算法,void allPath(Bitree t,Stack ,A,B,E,C,F,G,H,D,I,J,K,ABEABCFGHABCDIJK,A,B,E,C,F,G,H,D,I,J,K,A A A,B B B,E C C,F D,G I,H J,K,二叉树无左子树的结点都是树的叶子结点 退栈的结点要增加, 访问右结点时，结点要退栈（B,G,C,I）,void outPath(Bitree t,Stack ,6.8 哈夫曼树与哈夫曼编码,最优树的定义 如何构造最优树 前缀编码,最优树的定义,结点的路径长度

22、从根结点到该结点的路径上分支的数目 树的路径长度 树中每个结点的路径长度之和,A,B,C,D,B结点路径长度：1D结点路径长度：2 树的路径长度：4,树的带权路径长度 树中所有叶子结点的带权路径长度之和 WPL(T)= WkLk(所有叶子结点) 叶子结点有权值:W,WPL(T)=7*2+5*2+2*3+4*3+9*2=60,WPL(T)=7*4+9*4+5*3+4*2+2*1=89,二棵树，5个叶子结点，权值相同，但带权路径长度不同,在所有含n个叶子结点并带相同权值的m叉树中，必存在一棵其带权路径长度最小值的树，称为最优树,权值的含义,是由问题决定的 例如，测量一批零件的合格率，结果如下： 判定树表示 带权路径长度的含义是比较次数，为使比较次数最小，构造最优树,哈夫曼树,n个带权叶子结点构成的二叉树中，带权路径长度最小的二叉树 构成哈夫曼树算法 给定n个权值w1,w2,wn构成n棵只带wi的根结点F=T,T2,Tn，左右子树空 在F中选根结点权值最小二两棵，分别作为左右子树构成一棵新二叉树，使新二叉树根结点的权值为其左右子树根结点权值之和 F中删除这二棵树，同时加入刚生成的新树 重复2,3步骤，直至F中只有一棵树为止,前缀编码(哈夫曼树应用),等长码 设字符A B C D在电文中出现的概率同，给以相同长度的编码，如：00 01 10 11 不等长码