二叉树遍历算法的应用

•6.3.5二叉树遍历算法的应用•1.统计二叉树中结点总数numb•假设用中根遍历方法统计结点总个数，设计一个公有函数作为对外接口，调用同名的私有递归函数实现此功能。•//公有函数•voidBiTree::injishu()•｛intnumb=0;•injishu(root,int&numb);//调用私有函数•cout\nnumb=numb;//输出结果}•算法6.8•//私有函数•voidBiTree::injishu(NodeType*t,int&m)•｛if(t!=NULL)•｛injishu(t-lch,m)；//中根遍历左子树•coutt-data””；//访问根结点•m++;//结点记数•injishu(t-rch,m)；//中根遍历右子树•｝｝传世为您整理•2.求二叉树的树深•首先看如下算法：•intBiTree::height(NodeType*p)•{if(p==NULL)return0;•else•{inthl=height(p-lch);•inthr=height(p-rch);•return1+(hlhr?hl:hr);•//1加上hl和hr的较大值•}•}2.求二叉树的树深首先看如下算法：intBiTree::height(NodeType*p){if(p==NULL)return0;else{inthl=height(p-lch);inthr=height(p-rch);return1+(hlhr?hl:hr);//1加上hl和hr的较大值}}3.二叉树的复制与拷贝假设已经有了一棵已经建立好的二叉树，怎样由它来复制另一个相同的二叉树？下列为私有递归函数，即复制二叉树的函数。NodeType*BiTree::copy(NodeType*p){NodeType*q;if(p==NULL)returnNULL;else{q=newNodeType;q-data=p-data;q-lch=copy(p-lch);q-rch=copy(p-rch);returnq;}};6.４线索二叉树如果二叉树分别进行先根遍历中根遍历和后根遍历，那么可得相应的序列.这实质上是对一个非线性结构进行的线性化操作。有时为了运算方便，需要记下树中结点按某次序遍历下的前趋和后继结点。能否在二叉链表中保存这种信息呢？6.4.1线索二叉树的基本概念具有n个结点的二叉树，有n－1条边，正是这些边指向其左孩子、右孩子。这意味着在二叉链表的2n个孩子指针域中只用到了n+1个域，还有另外n+1个指针域为空，或被闲置。现设法将这些空闲的指针域利用起来。当某结点无左孩子时，令左指针指向它的前趋结点；当该结点无右孩子时，令右指针指向它的后继结点。为了严格区分结点的孩子指针域究竟指向孩子结点还是指向前趋或后继结点，需在原结点结构中增加两个标志域。对一个已建好的二叉树的二叉链表进行线索化时规定（针对p结点）：(1)p有左孩子时，则令左特征域p-ltag＝0；(2)p无左孩子时，令p-ltag＝1；并且让p-lch指向p的前趋结点；(3)p有右孩子时，令p-rtag＝0；(4)p无右孩子时，令p-rtag＝1；并且让p-rch指向p的后继结点。ADHIFECBGADHIFECBGADHIFECBGADHIFECBGNULLNULL(a)(b)(c)(d)（a）二叉树；（b）先根线索二叉树；（c）中根线索二叉树；（d）后根线索二叉树6.5二叉树、树和森林6.5.1树的存贮结构ABCDEFGHI0112335551.双亲数组表示法树最常用的是孩子-兄弟二叉链表表示法，这种方法表示规范，不仅适用于多叉树的存储，也适用于森林的存储。孩子-兄弟二叉链表的结点结构是:(一个数据域和两个指针域，)一个指针指向它的长子，另一指针指向它的一个兄弟。6.5.2树与二叉树之间的转换1.一般树转化为二叉树将一般树转化为二叉树的思路，主要根据树的孩子-兄弟存储方式而来.步骤是：(1)加线：在各兄弟结点之间用虚线相链。理解:为每个结点的兄弟指针指向它的一个兄弟。(2)抹线：对每个结点仅保留它与其最左一个孩子的连线，抹去该结点与其它孩子之间的连线。理解:为每个结点仅有一个孩子指针，让它指向自己的长子。(3)旋转：把虚线改为实线从水平方向向下旋转45℃，成右斜下方向。原树中实线成左斜下方向。这样就树的形状成呈现出一棵二叉树。2.二叉树还原为一般树二叉树转换为一般树，此时的二叉树必须是没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。其还原过程也分为三步：（１）加线：若某结点i是双亲结点的左孩子，则将该结点i的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点i的双亲结点用虚线连接。（２）抹线：把原二叉树中所有双亲结点与其右孩子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟，抹去的连线是兄弟间的关系。（３）进行整理：把虚线改为实线，把结点按层次排列。6.5.3森林与二叉树的转换1.森林转换为二叉树将森林转换为二叉树的一般步骤为：（１）将森林中每棵子树转换成相应的二叉树。形成有若干二叉树的森林，（２）按森林图形中树的先后次序，依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树，这样整个森林就生成了一棵二叉树，实际上第一棵树的根结点便是生成后的二叉树的根结点。2.二叉树还原为森林将一棵由森林转换得到的二叉树还原为森林，其步骤是：（１）抹线：将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去，这样就得到包含有若干棵二叉树的森林。（２）还原：将每棵二叉树按二叉树还原一般树的方法还原为一般树。于是得到森林。这部分自己练习.6.6树的应用6.6.1二叉排序树1.二叉排序的定义和特点定义：二叉排序树(binarysorttree)或是空树；或是非空树。对于非空树：(1)若它的左子树不空，则左子树上各结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上各结点的值均大于等于它的根结点的值；(3)它的左、右子树又分别是二叉排序树。这种二叉排序树具有左小右大的特点。根据需要也可以构造左大右小的二叉排序树。1032818151969图6.18二叉排序树特点：对二叉排序树进行中序遍历，可得到一个由小到大的序例。例如对图6.18的二叉排序树进行中根遍历:则得到序列：2，3，6，8，9，10，15，18，19。2.二叉排序树的类定义现在采用二叉链表做为存储结构，其结点结构如下：typedefintElemType;structBstNode{ElemTypedata;//数据域structBstNode*lch,*rch;};建立二叉排序树，实质上是不断地进行插入结点的操作。设有一组数据：Ｋ={k1k2，……kn}，将它们一一输入建成二叉排序树。建立二叉排序树的思路:(1)让k1做根；(2)对于k2，若k2k1，令k2做k1的左孩子；否则令k2做k1的右孩子；(3)对于k3，从根k1开始比较。若k3k1，到左子树中进行查找；否则到右子树中进行查找；直到找到合适的位置进行插入。(4)对于k4，k5，……，kn，重复第（3）步，直到kn处理完为止。首先看建立二叉排序树的主体算法，它在类定义中是一个公有函数。voidBstree::creat()//建立二叉排序树{BstNode*s;intn,i;ElemTypek;cout\nn＝?;cinn;for(i=1;i=n;i++){cout\nkey=?i;cink;s=newBstNode;s-data=k;s-lch=NULL;s-rch=NULL;root=insertl(root,s);//调用插入函数}}在该算法中调用下列插入函数：root=insertl(root,s)。insertl(root,s)函数的作用是在二叉排序树t中，插入一个结点s。BstNode*Bstree::insertl(BstNode*t,BstNode*s){if(t==NULL)t=s;elseif(s-datat-data)t-lch=insertl(t-lch,s);//将s插入t的左子树elset-rch=insertl(t-rch,s);//将s插入t的右子树returnt;}该函数有两个形参并且函数带有返回值，它还是一个递归函数。这样的函数适合于做类的私有函数成员，不允许外部访问。在二叉排序树t中，插入一个结点s的算法也可以写成非递归函数。voidinsert2(BstNode*t，BstNode*s){if(t==NULL)t=s；else{p=t；while(p!=NULL){q＝p；//当P向子树结点移动时，q记P的双亲位置if(s-data＜p-data)p=p-lch；elsep=p-rch；}if(s-data＜q-data)q-lch=s；elseq-rch=s；//当p为空时，q就是可插入的地方}}假设给出一组数据{10，3，18，6，20，2}，对照上述算法生成二叉排序树的过程如果仍使用前边6个数据，但输入先后顺序改为｛2，3，6，10，18，20｝，那么生成的二叉排序树如何？请思考。图6.19二叉排序树的生成201010101010103318318636181836202206.6.2哈夫曼树及其应用1.结点的带权路径长度是从该结点到树根之间的路径长度与结点上权的乘积。2.树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。设一棵二叉树有n个叶子结点，每个叶子结点拥有一个权值Ｗ1，Ｗ2，......Ｗn，从根结点到每个叶子结点的路径长度分别为L1，L2......Ln，通常记作WPL＝∑Ｗk·Ｌk。哈夫曼树(也称最优树)是在具有同一组权值的叶子结点的不同二叉树中，带权路径长度最短的树。构造哈夫曼树的方法:对于已知的一组叶子的权值Ｗ1，Ｗ2......，Ｗn①首先把n个叶子结点看做n棵树（仅有一个结点的二叉树），把它们看做一个森林。②在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有n-1棵树。③重复第②步直到森林中只有一棵为止。此树就是哈夫曼树。现给一组(n=4)具体的权值2，4，5，8，下边是构造具体过程：小结:1.n个叶子构成的哈夫曼树其带权路径长度唯一吗？2.树形唯一吗？哈夫曼算法实现voidHuffTree::CreatHtree()//建立哈夫曼树{inti,j,x1,x2,m1,m2;for(i=1;in;i++){cout\n权值=;cinr[i].data;r[j].tag=0;r[j].lch=0;r[j].rch=0;}i=0;while(in-1)//合并n-1次{m1=m2=32767;//m1代表最小值变量，m2代表次小值变量；x1=x2=0;//x1,x2为最小值、次小值的下标号for(j=1;j=n+i;j++){if((r[j].datam1)&&(r[j].tag==0)){m2=m1;x2=x1;m1=r[j].data;x1=j;}elseif((r[j].datam2)&&(r[j].tag==0)){m2=r[j].data;x2=j;}}r[x1].tag=1;r[x2].tag=1;i++;r[n+i].data=r[x1].data+r[x2].data;//m1+m2r[n+i].tag=0;r[n+i].lch=x1;r[n+i].rch=x2;}}//哈夫曼树的根结点（在此是数组元素）的下标位置应是2*n-2,为什么?Else能不能少