第7章 树和二叉树 7.1 仿真指针 7.2 树 7.3 二叉树 7.4 链式存储结构的二叉树设计 7.5 二叉树遍历游标类 第7章 树和二叉树 7.1 仿真指针 7.2 树 7.3 二叉树 7.4 链式存储结构的二叉树设计 7.5 二叉树遍历游标类 7.6 线索二叉树 7.7 堆 7.8 哈夫曼树
7.1 仿真指针 在链式存储结构中，我们实现数据元素之间的次序关系依靠指针。在使用数组存储数据元素时，我们可在存储数据元素的数组中增加一个或几个数组下标域，这些数组下标域的值表示了该数组中某个数据元素的下标。由于在数组中增加的数组下标域仿真了链式存储结构中的指针域，所以这种存储结构也称作仿真指针。
图7―1(a）是一个有5个数据元素的常规链式存储结构的表。图7―1（b）和（c）是图7―1(a)的仿真指针结构，其中数组的data域存放数据元素，数组的next域为该元素的后续元素在数组中的下标值，next域值为-1表示链尾。图7―1（b）和(c）是相同表结构的两个不同数组存储方式。由于图7―1（b）和（c）的链表是一种静态存储结构，所以也称作静态链表。
仿真指针也可用于存储如树和二叉树的非线性结构。当仿真指针用于存储树或二叉树时通常需要一个以上的仿真指针域。在7. 2 仿真指针也可用于存储如树和二叉树的非线性结构。当仿真指针用于存储树或二叉树时通常需要一个以上的仿真指针域。在7.2.4节讨论的树的存储结构中，所有存储结构既可使用常规指针结构实现，也可使用仿真指针结构实现。7.8节讨论的哈夫曼树将使用仿真指针存储结构实现。
图7―1 链表 (a)常规链表；（b）静态链表一；（c）静态链表二
7.2 树 7.2.1 树的定义 树（Tree）是由n（n≥0）个有限结点构成的集合。n=0的树称为空树；对n>0的树T有： 7.2 树 7.2.1 树的定义 树（Tree）是由n（n≥0）个有限结点构成的集合。n=0的树称为空树；对n>0的树T有： （1）有一个特殊的结点称为根结点，根结点没有前驱结点； （2）当n>1时，除根结点外其他结点被分成m（m>0）个互不相交的集合T1,T2,…,Tm。其中，每一个集合Ti（1≤i≤m）本身又是一棵称为根结点的子树的树。
显然，树是递归定义的，即在树的定义中用到了树自身，因此，在包含树结构的算法中将会频繁地出现递归。 图7―2是树的例子。其中，图7―2(a）是一棵空树，即T={}；图7―2（b）是一棵只有根结点的树，即T={A}；图7―2（c）是一棵有12个结点的树，即T={A,B,C,D,E,F,G,H,I,J,K,L}。
图7―2 树的示例
下面介绍树的常用术语。 结点（Node）。在树中通常把数据元素和构造数据元素之间关系的指针合起来称作结点。 例如，图7―2（b）中有1个结点，图7―2中（c）有12个结点。 结点的度。结点所拥有的子树的个数称为该结点的度。例如，在图7―2（c）中结点A的度为3，结点B的度为2，结点J的度为0。 叶结点。度为0的结点称为叶结点，叶结点也称作终端结点。例如，在图7―2（c）中结点J,F,K,L,H,I均为叶结点。
分支结点。度不为0的结点称为分支结点，分支结点也称作非终端结点。显然，一棵树中除叶结点外的所有结点都是分支结点。 孩子结点。树中一个结点的子树的根结点称作这个结点的孩子结点。例如，在图7-2（c）中结点B,C,D是结点A的孩子结点。孩子结点也称作后继结点。 双亲结点。若树中某结点有孩子结点，则该结点就称作他的孩子结点的双亲结点。例如，在图7―2（c）中结点A是结点B,C,D的双亲结点。双亲结点也称作前驱结点。
兄弟结点。具有相同的双亲结点的结点称为兄弟结点。例如，在图7―2（c）中结点B,C,D的具有相同双亲的结点A，所以结点B,C,D互相之间称为兄弟结点。 祖先结点。从根结点到树中某结点所经过的所有分支结点称为该结点的祖先结点。例如，在图7―2（c）中结点J的祖先结点有结点E,B,A。一个树中根结点是该树中所有其他结点的祖先结点。
子孙结点。某一结点的所有孩子结点，以及这些孩子结点的孩子结点称为该结点的子孙结点。例如，在图7―2（c）中结点E,F,J是结点B的子孙结点。一个树中所有结点都是根结点的子孙结点。 树的度。树中所有结点的度的最大值称为该树的度。例如，图7―2（c）树中结点A的度等于3是该树中所有结点的度的最大值，所有该树的度为3。 结点的层次。从根结点到树中某结点所经路径上的分支数称为该结点的层次。通常规定根结点的层次是0，这样其他结点的层次就是他的双亲结点的层次加1。
树的深度。树中所有结点的层次的最大值称为该树的深度，空树的深度规定为-1。图7-2(a）树的深度等于-1；图7―2（b）树的深度等于0；图7―2（c）树的深度等于3。 无序树。树中任意一个结点的各个子树之间的次序构成无关紧要，即交换树中任意一个结点的各个子树的次序均和原树相同的树称为无序树。树均定义为无序树。 有序树。树中任意一个结点的各个子树都是有次序的树称为有序树。下面要讨论的二叉树就是一种有序树，因为二叉树中任意一个结点的任意一个子树都确切地定义为是该结点的左子树或是其右子树。
森林。m（m≥0）棵树的集合称为森林。自然界中树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，空树集合称作包含m=0棵树的森林；一棵树称作包含m=1棵树的森林；把一个根结点的子树个数大于1的树的根结点删除，则树就变成了包含m>1棵树的森林。 树结构表示了数据元素之间的层次关系，最常见的例子就是如图7―3所示的计算机中的磁盘文件目录。
图7―3 计算机中的一个磁盘文件目录
7.2.2 树的表示方法 树的表示方法主要有三种，各用于不同的目的： 1.树的直观表示法 图7―2就是一棵以直观表示法表示的树。树的直观表示法主要用于直观描述树的逻辑结构，本书中的树均以直观表示法表示。 2.树的形式化表示法 树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树T为T=（D，R）。
其中D为树T中结点的集合，R为树T中结点之间关系的集合。当树T为空树时D=Φ ；当树T不为空树时有D={Root}∪DF，其中Root为树T的根结点，DF为树T的根Root的子树集合，DF可由下式表示： DF=D1∪D2∪…∪Dm （1≤i,j≤m,Di∩Dj= Φ ） 当树T中结点个数n≤1时，R= Φ ；当树T中结点个数n>1时有 R={〈Root,ri〉,i=1,2,…,n-1} 其中，Root是树T的非终端结点，ri是结点Root的子树Ti的根结点，〈Root,ri〉表示了结点Root和结点ri的父子关系。
3.树的凹入表示法 树的凹入表示法是一种结点逐层凹入的表示方法。树的凹入表示法还可分为横向凹入表示和竖向凹入表示。图7―2（c）树的横向凹入表示如图7―4所示。树的凹入表示法主要用于树的屏幕和打印机显示。
图7―4 一棵树的横向凹入表示
7.2.3 树的基本操作 树的操作主要分为三大类：第一类，寻找满足某种特定关系的结点；第二类，插入或删除某个结点；第三类，遍历树中每个结点。 1.第一类操作 ·寻找根结点使之成为当前结点； ·寻找当前结点的双亲结点使之成为当前结点； ·寻找当前结点的第一个孩子结点使之成为当前结点； ·寻找当前结点的下一个兄弟结点使之成为当前结点。
2.第二类操作 ·在树的当前结点上插入一个新结点，使新插入结点成为当前结点的第i个孩子结点； ·删除树的当前结点的第i个孩子结点； ·在树的当前结点上插入一个新子树，使新插入子树成为当前结点的第i棵子树； ·删除树的当前结点的第i棵子树。
3.第三类操作 ·按某种方式遍历一棵树显示树中每个结点的数据域值； ·按某种方式遍历一棵树寻找数据元素域为某一值的结点。 对于前两类操作比较容易理解，对于第三类的遍历操作我们再作以下详细讨论。树的遍历操作是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。对于线性结构，通过for循环或while循环就可访问其中的每一个数据元素且每一个数据元素只被访问一次。
下面的先根遍历和后根遍历算法都是递归的。 (1)先根遍历。先根遍历算法为： ·访问根结点； ·按照从左到右的次序先根遍历根结点的每一棵子树。 对于图7―2（c）树先根遍历得到的结点序列为： A B E J F C G K L D H I (2)后根遍历。后根遍历算法为： ·按照从左到右的次序后根遍历根结点的每一棵子树； ·访问根结点。
对于图7―2（c）树后根遍历得到的结点序列为： J E F B K L G C H I D A 此外，树的遍历算法还有层序遍历。树的层序遍历是要求按照从根结点至叶结点、从第一棵子树至最后一棵子树的次序访问树的结点。对于图7―2（c）树层序遍历得到的结点序列为： A B C D E F G H I J K L 限于篇幅，我们在此不再详细讨论树的层序遍历算法，有兴趣的读者可参考7.3.3节的二叉树的层序遍历算法自己设计。
7.2.4 树的存储结构 1.双亲表示法 双亲表示法是用7.1节讨论的仿真指针结构存储树。具体方法是用一组连续的存储单元（数组）存储树中的所有结点，每一个结点有两个域：一个域是数据元素域，一个域是指示其双亲结点在数组中下标序号的仿真指针域。
图7―5是一棵树及其双亲表示法仿真指针存储结构。图7―5（b）中的data域是数据元素域，parent域是指示其双亲结点在数组中下标序号的仿真指针域。结点A是根结点，无双亲结点，所以仿真指针域parent的值为-1；结点B的双亲结点是结点A，结点A在数组中的下标序号是0，所以仿真指针域parent的值为0，其他的类推。
图7―5 树及其双亲表示法仿真指针存储结构 (a）一棵树; （b）双亲表示法仿真指针存储结构
双亲表示法的仿真指针域也可改为常规的指针域。双亲表示法对于实现前述的树的基本操作中寻找双亲结点和寻找根结点使它们各自成为当前结点操作很方便，但对于实现寻找第一个孩子结点和寻找下一个兄弟结点使它们各自成为当前结点操作却很不方便。
2.孩子表示法 由于树中每个结点的子树个数（即结点的度）不同，如果按各个结点的度设计变长结构，则每个结点的孩子结点指针域个数增加使算法实现非常麻烦。孩子表示法可按树的度（即树中所有结点度的最大值）设计结点的孩子结点指针域个数。同样，结点的孩子结点指针域可以是仿真指针，也可以是常规指针。图7―6是图7―5(a）所示树的常规指针的孩子表示法。其中，结点的孩子结点指针域个数是按树的度设计的，该树的度为3，所以每个结点的孩子结点指针域个数为3。
图7―6 树的常规指针的孩子表示法
3.双亲孩子表示法 树的存储结构若把双亲表示法和孩子表示法结合起来可使之兼有这两种存储结构的优点。可有许多种结合双亲表示法和孩子表示法的存储结构方法。一种双亲孩子表示法是在图7-5（b）所示的仿真指针双亲表示法的基础上，给数组的每个结点增加一个指向该结点所有孩子结点链表的常规指针。图7-5(a）树的双亲孩子表示法的存储结构如图7―7所示。显然，图7―7的双亲孩子表示法的存储结构是仿真指针和间接地址两种存储结构方法的结合。
图7―7 双亲孩子表示法的一种结构
4.孩子兄弟表示法 孩子兄弟表示法是为每个结点设计三个域：一个数据元素域，一个该结点的第一个孩子结点指针域，一个该结点的下一个兄弟结点指针域。此种孩子兄弟表示法的两个指针域通常都是常规指针。图7―5（a）树的孩子兄弟表示法如图7―8所示。
图7―8 孩子兄弟表示法
7.2.5 树类 本节我们以树的孩子兄弟表示法为存储结构设计一个树类。孩子兄弟表示法存储结构表示的树的每个结点的结构包括三个域：数据域、第一个孩子结点指针域和下一个兄弟结点指针域。 ＃include<stdlib.h> template<classT>classTree; template<classT>classTreeNode { friend classTree<T>; //树类为友元
private: TreeNode<T>*firstChild;//第一个孩子结点指针域 TreeNode<T>*nextSibling;//下一个兄弟结点指针域 public: Tdata;//数据域 //构造函数 Tree Node(Tvalue,TreeNode<T>*fc=NULL, TreeNode<T>*ns=NULL) :data(value),firstChild(fc),nextSibling(ns){} //访问指针域的成员函数
Tree Node<T>*&First Child(void) {returnfirst Child;} Tree Node<T>*&Next Sibling(void) {return nextSibling;} };
树类的数据成员有根结点指针和当前结点指针；树类的共有成员函数为前一节讨论的树的三大类基本操作；树类的私有成员函数是为方便树类的共有成员函数设计的。访问指针域的成员函数First Child()和Next Sibling( )的返回值类型设计为指针的引用类型是十分必要的，这不仅可取得该指针所指结点的值，而且还可以给该结点赋值。
template<classT>class Tree { private: //数据成员 Tree Node<T>*root; //根结点指针 Tree Node<T>*current; //当前结点指针 //私有成员函数
Void Pre Order Tree(Tree Node<T>*&t); Int Current(Tree Node<T>*&t); //使当前结点为t所指结点 //在树root中回溯查找结点s的双亲结点。 Tree Node<T>*Search Parent(Tree Node<T>*&root,Tree Node<T>*&s); public:
//构造函数和析构函数 Tree(){root=current=NULL;} //构造函数 ~Tree(){Delete Sub Tree(root);} //析构函数 //第一类操作的成员函数 int Root();//使根结点为当前结点 int Parent()//使当前结点的双亲结点为当前结点 int First Child(); //使当前结点的第一个孩子结点为当前结点 int Next Sibling();//使当前结点的兄弟结点为当前结点
//第二类操作的成员函数 void Insert Child(Tvalue); //把value插入到当前结点的最后一个结点 void Delete SubTree(Tree Node<T>*&t);//删除以t为根结点的子树 int Delete Child(inti);//删除当前结点的第i个孩子结点 //第三类操作的成员函数 void Display Tree();//按先根遍历次序显示树的数据域值
1.构造函数和析构函数 析构函数是通过调用删除以Root为根结点树的成员函数Delete Sub Tree(Root)来实现删除以Root为根结点的树的。要删除树中的所有结点也需要遍历树，Delete Sub Tree(t)算法是一个二叉树中序遍历的递归算法。即先删除根结点的左子树，然后删除根结点，删除根结点时把右子树指针保存起来，最后删除右子树。 对于一棵如图7―9（a）所示的树，按孩子兄弟表示法建立的树的结构如图7-9（b）所示。
图7―9 树及其孩子兄弟表示法结构 （a）树；（b）孩子兄弟表示法结构
template<classT> voidTree<T>::Delete Sub Tree(Tree Node<T>*&t) { if(t==NULL)return; TreeNode<T>*q=t->first Child,*p; while(q!=NULL) p=q->next Sibling;
Delete Sub Tree(q); q=p; } deletet; } 对于图7―9（b）所示的树，Delete Sub Tree(Root)执行时系统运行时栈的状态和删除操作如图7―10所示，图中的A,B,C,D,E,F表示指向结点A,B,C,D,E,F的指针。箭头所指为运行时栈的当前栈顶，操作指的是执行Delete Sub Tree(Root)中的deletet语句。
图7―10 执行Delete Sub Tree(root)时的系统运行 时栈状态和删除操作
如果在算法Delete Sub Tree(t)中的deletet语句前加如下一句语句: cout<<t.data<<""; 那么，若程序的主函数建立了如图7―9（b）所示的树，当析构函数调用Delete Sub Tree(Root)时，屏幕会显示出所删除结点的序列为： E F B C D A
2.以控制当前结点位置为特征的第一类操作的成员函数 template<classT> int Tree<T>::Current(TreeNode<T>*&t) //使当前结点为t所指结点 { if(t==NULL)return 0; current=t; return 1; }
template<class T> Int Tree<T>::Root()//使根结点为当前结点 { if(root==NULL) { current=NULL; return0; } Return Current(root);
template<class T> Int Tree<T>::FirstChild() { if(current!=NULL&¤t->first Child!=NULL) Return Current(current->first Child); else return0; } Int Tree<T>::Next Sibling()
{ if(current!=NULL&¤t->next Sibling!=NULL) Return Current(current->next Sibling); else return(); } template<class T> Int Tree<T>::Parent()
//使当前结点的双亲结点为当前结点 { if(current==NULL) current=root; return0; } Tree Node<T>*p=Search Parent(root,current); if(p==NULL)return0; Elsereturn Current(p);; }
template<classT> Tree Node<T>*Tree<T>::Search Parent(Tree Node<T>*&root,Tree Node<T>*&s) //在树root中回溯查找结点s的双亲结点 //查找到时使current指向s结点的双亲结点 { if(root==NULL)return NULL; if(root->First Child()==s||root->Next Sibling()==s) returnroot;
Tree Node<T>*p; if((p=Search Parent(root->First Child(),s))!=NULL)returnp; if((p=Search Parent(root->Next Sibling(),s))!=NULL)returnp; Return NULL;//失败时返回空使算法回溯 }
注意递归算法Search Parent(Root,s)也是6 注意递归算法Search Parent(Root,s)也是6.6节讨论过的一个回溯算法。当本层递归调用未查找到根结点的First Child()指针或根结点的Next Sibling()等于s指针，且root→First Child()指针和root→Next Sibling()的递归调用均失败时算法返回空，从而引起算法回溯到上一层的递归调用处继续查找。
3. 以插入和删除结点为特征的的第二类操作的成员函数 为简化算法，我们这里设计的插入新结点成员函数是建立一个新结点作为当前结点的最后一个孩子结点。算法分三种情况：当为空树时，当前结点无孩子时和当前结点已有孩子时。算法如下：
template<class T> Void Tree<T>::Insert Child(Tvalue) //把value插入到当前结点的最后一个结点 { //建立数据域值为value的结点由new Node指针指示 Tree Node<T>*new Node=new Tree Node<T>(value); if(root==NULL)//当为空树时 root=current=new Node;
return; } if(current->first Child==NULL)//当当前结点无孩子时 current->first Child=new Node; else//当当前结点已有孩子时 { Tree Node<T>*p=current->first Child; while(p->next Sibling!=NULL)p=p->next Sibling; p->next Sibling=new Node;
} Current(new Node);//使新建立的结点为当前结点 } 删除以t为根结点的树的成员函数Delete Sub Tree(t)前面已讨论过。删除树的当前结点的第i个孩子结点分为删除当前结点的第一个孩子结点和删除当前结点的非第一个孩子结点两种情况；每种情况又分为要删除的孩子结点存在和要删除的孩子结点不存在两种情况。当要删除的孩子结点存在且找到后，首先把要删除的孩子结点脱链；然后，调用前述的Delete Sub Tree(t)成员函数，删除该孩子结点。
template<class T> Int Tree<T>::Delete Child(inti) { Tree Node<T>*r=NULL; if(i=1) //当删除当前结点的第一棵子树时 r=current->first Child; if(r==NULL)return0; //要删除子树为空返回 current->first Child=r->next Sibling; //脱链要删除的子树
} else//当删除当前结点的其他子树时 { intk=1; Tree Node<T>*p=current->first Child; while(p!=NULL&&k<=i-1)//寻找指向要删除子树的指针 p=p->next Sibling; k++; }
if(p!=NULL) //所寻找的指向要删除子树的指针找到 { r=p->next Sibling; if(r!=NULL) p->next Sibling=r->next Sibling; //脱链要删除的子树 elsereturn0; //要删除子树为空返回 } elsereturn0; //所寻找的指向要删除子树的指针未找到 }
Delete SubTree(r); //删除找到的要删除的子树 return1; //删除成功 }
4.以遍历操作为特征的第三类操作的成员函数 私有成员函数Pre Order Tree(t)是一个按先根遍历树次序显示数据域值的算法。为简化算法设计，本算法只支持C++的固有类型，否则输出语句cout<<t->data就要重新设计成重载的输出流。 template<class T> void Tree<T>::Pre OrderTree(Tree Node<T>*&t) { if(t==NULL)return;
cout<<t->data<<"";//显示根结点数据 if(t->first Child!=NULL)//先根遍历子树 Pre OrderTree(t->first Child); if(t->next Sibling!=NULL) PreOrder Tree(t->next Sibling); } template<classT> Void Tree<T>::Display Tree() { Pre Order Tree(root);//按先根遍历次序显示树的数据域值 }
若要按后根遍历次序显示树的数据域值，Display Tree()应调用如下的按后根遍历次序显示子树t的数据域值的成员函数。 template<class T> void Tree<T>::Pos Order Tree(Tree Node<T>*&t) { if(t==NULL)return; if(t->first Child!=NULL)//后根遍历子树 Pos Order Tree(t->first Child);
cout<<t->data<<"";//显示根结点数据 if(t->next Sibling!=NULL) Pos Order Tree(t->next Sibling); } 上述树类放在文件Tree.h中。
例7―1 设计一个测试程序：首先，建立一个图7―9(a）所示的树；然后，按先根遍历次序显示结点数据域值；最后，显示析构函数按后根遍历释放结点的次序。 一个实用的树类应当包括更多的功能更强的树操作成员函数，由于我们设计的树类只包括最基本的树操作成员函数，所以建立树的过程稍微复杂了一点。测试程序如下：
＃include<iostream.h> ＃include"Tree.h" Void main(void) { Tree<char>t; t.Insert Child(′A′); for(int i=0;i<3;i++) t.Root();
t.Insert Child(′B′+i); } for(i=0;i<2;i++) { t.Root(); t.First Child(); t.Insert Child(′E′+i); } cout<<"按先根遍历显示的结点次序为："<<endl; t.Display Tree();
cout<<endl<<"析构函数按后根遍历释放结点的次序为："<<endl; } 程序的运行结果如下： 按先根遍历显示的结点次序为： A B E F C D 析构函数按后根遍历释放结点的次序为： E F B C D A
7.3 二 叉 树 7.3.1 二叉树的定义 二叉树（Binary Tree）是n（n≥0）个有限结点构成的集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点和两个互不相交的、分别称作左子树和右子树的子二叉树构成。
显然，二叉树是一种有序树。二叉树中某个结点既使只有一棵子树也要区分是左子树还是右子树。因此，图7―11（a）和（b）应是两棵不同的二叉树。 图7―11 两棵不同的二叉树 （a）二叉树1；（b）二叉树2
二叉树中所有结点的形态共有5种：空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。 满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称作满二叉树。图7―12(a）的二叉树是一棵满二叉树。
图7―12 两种特殊的二叉树 （a）满二叉树；（b）完全二叉树
完全二叉树。如果一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同，这样的二叉树称作完全二叉树。图7―12（b）的二叉树是一棵完全二叉树。比较图7―12（b）和（a）可知，图7―12（b）的二叉树10个结点与图7―12（a）满二叉树的前10个结点的结构相同，因此图7-12（b）的二叉树是完全二叉树。显然，满二叉树一定是完全二叉树。
7.3.2 二叉树的性质 性质1 若规定根结点的层次为0，则一棵非空二叉树的第i层上最多有2i（i≥0）个结点。 归纳法证明 当层次n=0时，二叉树在根结点只有一个结点，20=1，结论成立；当层次n=t时结论成立，即第t层上最多有2t个结点；当层次n=t+1时，根据二叉树的定义，第t层上的每个结点最多有2个子结点，所以第t+1层上最多有2t*2=2t+1个结点。
性质2 若规定空树的深度为-1，则深度为k的二叉树的最大结点数是2k+1-1（k≥-1）个。 证明 当深度为k=-1时是空二叉树，空二叉树应当一个结点也没有，有2-1+1-1=20-1=0，结论成立；当深度为k≥0时是非空二叉树，具有层次i=0,1,2,…,k，由性质1知，第i层上最多有2i（i≥0）个结点，所以整个二叉树中所具有的最大结点数为
性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0=n2+1。 此外，在二叉树中，除根结点外的所有结点都有一个惟一的进入分支。设M为二叉树中的分支数，则有 M=n-1
从二叉树的结构可知，二叉树的所有进入分支是由度为1的结点和度为2的结点发出的，每个度为1的结点发出一个分支，每个度为2的结点发出两个分支，所以又有 M=n1+2n2 综合以上三式可以得到n0=n2+1。
性质4 具有n个结点的完全二叉树的深度k为不超过lb2(n+1)-1的最大整数。 2k-1<n≤2k+1-1 移项有 2k<n+1≤ 2k+1 对不等式求对数，有 k<lb(n+1)≤k+1
性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对所有结点从0开始顺序编号，则对于任意的序号为i的结点，有： （1）如果i>0，则序号为i结点的双亲结点的序号为(i-1)/2（“/”表示整除）；如果i=0，则序号为i的结点为结点，无双亲结点； （2）如果2i+1<n，则序号为i结点的左孩子结点的序号为2i+1；如果2i+1≥n，则序号为i结点无左孩子； （3）如果2i+2<n，则序号为i结点的右孩子结点的序号为2i+2；如果2i+2≥n，则序号为i结点无右孩子。
证明 我们首先用归纳法证明（2）和（3）。 当i=0时，如果2i+1=1<n，由完全二叉树的定义知二叉树中存在两个或两个以上的结点，因此其左孩子结点存在且序号为1；反之，如果2i+1=1≥n，说明二叉树中不存在两个结点，因此其左孩子结点不存在。同理，如果2i+2=2<n，由完全二叉树的定义知二叉树中存在三个或三个以上的结点，因此其右孩子结点存在且序号为2；反之，如果2i+2=2≥n，说明二叉树中不存在三个结点，因此其右孩子结点不存在。
假设对于序号为j（0≤j≤i）的结点，如果2j+1<n，则序号为j结点的左孩子结点的序号为2j+1；如果2j+1≥n，则序号为j结点无左孩子。同样，如果2j+2<n，则序号为j结点的右孩子结点的序号为2j+2；如果2j+2≥n，则序号为j结点无右孩子。 当i=j+1时，根据二叉树的定义，若其左孩子结点存在，则其左孩子结点序号一定等于序号为j结点的右孩子的序号加1，即其左孩子结点序号为(2j+2)+1=2(j+1)+1，且有2(j+1)+1<n；反之，如果2(j+1)+1≥n时说明序号为j+1结点无左孩子。
同理，当i=j+1时，根据二叉树的定义，若其右孩子结点存在，则其右孩子结点序号一定等于序号为j+1结点的左孩子的序号加1，即其右孩子结点序号为(2(j+1)+1)+1=2(j+1)+2,且有2(j+1)+2<n；反之，如果2(j+1)+2≥n时说明序号为j+1结点无右孩子。 因此（2）和（3）得以证明。
综合（2）和（3）即可证明（1）。当i=0时，显然该结点为根结点，无双亲结点；当i>0时，设序号为i结点的序号为m，如果i结点是m结点的左孩子结点，根据（2）有i=2m+1，即m=(i-1)/2；如果i结点是m结点的右孩子结点，根据（3）有i=2m+2，即m=(i-2)/2=(i-1)/2-1/2，因右孩子结点序号一定是偶数，所以有m=(i-2)/2=(i-1)/2（“/”表示整除）。 性质5是二叉树顺序存储结构的基础。7.7节要讨论的堆和第9章要讨论的堆排序就是二叉树顺序存储结构的一个典型应用。
性质5是二叉树顺序存储结构的基础。7.7节要讨论的堆和第9章要讨论的堆排序就是二叉树顺序存储结构的一个典型应用。
7.3.3 二叉树的操作 二叉树是由一个根结点和两个互不相交的、分别称作左子树和右子树的子二叉树构成。因此，二叉树的操作和树的操作多数基本类同，只在子树操作上略有不同。 二叉树的操作也分为三大类：第一类，找满足某种特定关系的结点；第二类，插入或删除某个结点；第三类，遍历树中每个结点。
1.第一类操作 ·寻找根结点使之成为当前结点； ·寻找当前结点的双亲结点使之成为当前结点； ·寻找当前结点的左孩子结点使之成为当前结点； ·寻找当前结点的右孩子结点使之成为当前结点。
2.第二类操作 ·在二叉树的当前结点上插入一个新结点，使新插入结点成为当前结点的左孩子结点； ·在二叉树的当前结点上插入一个新结点，使新插入结点成为当前结点的右孩子结点； ·在二叉树的当前结点上插入一个新子树，使新插入子树成为当前结点的左子树； ·在二叉树的当前结点上插入一个新子树，使新插入子树成为当前结点的右子树； ·删除二叉树的当前结点的左孩子结点；
·删除二叉树的当前结点的右孩子结点； ·删除二叉树的当前结点的左子树； ·删除二叉树的当前结点的右子树。 孩子结点和子树的区别是孩子结点只是一个结点，子树是结点下面可能还有子树结点。显然，子树的概念包含了孩子结点的概念。但子树的操作需要更多的参数，所以我们设计为两个操作。
3.第三类的操作 ·按某种方式遍历一棵二叉树显示二叉树中每个结点的数据域值； ·按某种方式遍历一棵二叉树寻找数据元素域为某一值的结点。 由二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D,L,R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，则共有六种组合： LDR,DLR,LRD,RDL,DRL,RLD。
由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以我们只讨论六种组合的前三种：LDR,DLR,LRD。根据遍历算法对访问根结点处理的位置我们称这三种遍历算法分别为中序遍历（LDR）、前序遍历（DLR）和后序遍历（LRD）。
(1)中序遍历（LDR）的递归算法。若二叉树为空则算法结束；否则： ·中序遍历根结点的左子树； ·访问根结点； ·中序遍历根结点的右子树。 对于图7―11（b）所示的二叉树，中序遍历访问结点的次序为：DGBAECF
(2)前序遍历（DLR）的递归算法。若二叉树为空则算法结束；否则： ·访问根结点； ·前序遍历根结点的左子树； ·前序遍历根结点的右子树。 对于图7―11（b）所示的二叉树，前序遍历访问结点的次序为：ABDGCEF。
(3)后序遍历（LRD）的递归算法。若二叉树为空则算法结束；否则： ·后序遍历根结点的左子树； ·后序遍历根结点的右子树； ·访问根结点。 对于图7―11（b）所示的二叉树，后序遍历访问结点的次序为：GDBEFCA。
由于二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，所以一个二叉树的遍历序列不能决定一棵二叉树，例如图7―11（a）和(b）的前序遍历序列是相同的，但他们是两棵不同的二叉树。但某些不同的遍历序列可以惟一地确定一棵二叉树。可以证明，给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一地确定一棵二叉树。
一棵二叉树虽然不能像单链表那样，除根结点和最后一个结点外每个结点都有一个惟一的前驱结点和惟一的后继结点，但当一棵二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是惟一的。例如，图7―11（a）和（b）的前序遍历序列一定是惟一的。
7.3.4 二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。 1. 二叉树的顺序存储结构 由前面证明的性质5可知，对于完全二叉树中任意结点i的双亲结点序号、左孩子结点序号和右孩子结点序号都可由公式计算得到。因此，完全二叉树的结点可按从上至下和从左至右的次序存储在一组从0开始的连续的内存单元中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。图7―12（a）在数组中的存储结构为：
然而，对于一般的二叉树，如果仍按从上至下和从左至右的次序存储在一组从0开始的连续的内存单元中，则数组下标之间的关系就不能反映二叉树中结点之间的逻辑关系。此时，可在一般二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用二叉树的顺序存储结构存储。
图7―13（a）是一棵一般二叉树，图7-13（b）是图7―13(a）的完全二叉树形态，图7―13（c）是图7―13（b）在数组中的存储结构。
图7―13 一般二叉树的顺序存储结构 （a）一般二叉树；（b）完全二叉树形态； （c）在数组中的存储结构
2. 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域：数据域data，左子树指针域leftChild和右子树指针域rightChild。二叉链存储结构中每个结点的图示结构为： Lefe Child data rightChild 对于图7―11（b）所示的二叉树，二叉链存储 结构如图7―14所示。
图7―14 二叉树的二叉链存储结构
二叉树的二叉链存储结构是一种常用的二叉树存储结构。二叉链存储结构的优点是：结构简单，可以方便地构造任意需要的二叉树，可以方便地实现二叉树操作中的大多数操作。 二叉链存储结构的缺点是查找当前结点的双亲结点操作实现起来比较麻烦。二叉树的另一种常用的存储结构是三叉链。三叉链是在二叉链的基础上再增加一个双亲结点指针域parent。三叉链除具有二叉链的优点外，对于查找当前结点的双亲结点操作实现起来也很容易。相对于二叉链，三叉链的缺点是结构更为复杂，因而每个结点占用的内存单元也更多一些。
3. 二叉树的仿真指针存储结构 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，再增加仿真指针域仿真常规指针建立二叉树中结点之间的关系。二叉树的仿真指针存储结构有仿真二叉链存储结构和仿真三叉链存储结构。图7―15是图7―14的仿真二叉链存储结构。 仿真指针存储结构的最大优点是遍历操作实现非常容易，用for循环或while循环就可实现。仿真指针存储结构的最大缺点是可存储的结点个数受初始化定义的数组元素个数限制。
图7―15 二叉树的仿真二叉链存储结构
7.3.5 树和二叉树的转换 我们在7.2.5节讨论的孩子兄弟表示法树类的测试程序中，图7―9给出了一棵树和使用孩子兄弟表示法时该树的存储结构。实际上，树的孩子兄弟表示法结构就是一种二叉树结构，当我们认为孩子兄弟表示法结构中的第一个孩子结点指针是左孩子指针，下一个兄弟结点指针是右孩子指针时，树的孩子兄弟表示法结构就是二叉树结构。
由此，我们可方便地把树转换为二叉树结构进行计算机的存储和处理，计算机存储和处理完后再把二叉树结构的树转换为树结构表示。这里我们再归纳给出树和二叉树之间转换的图示方法。树和二叉树之间转换的图示结构可用于对照孩子兄弟表示法存储树的应用程序的调试。
1.树转换为二叉树 树转换为二叉树的方法是： （1）树中所有相同双亲结点的兄弟结点之间加一条连线； （2）对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去该结点与其他孩子结点之间的连线； （3）整理所有保留的和添加的连线，使每个结点的孩子结点连线位于左孩子指针位置，使每个结点的兄弟结点连线位于右孩子指针位置。
图7―16 树转换为二叉树的过程 （a）树;(b）相邻兄弟加连线; （c）删除双亲与其他孩子连线;（d）二叉树
2. 二叉树还原为树 二叉树还原为树的方法是： （1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来； （2）删除原二叉树中所有双亲结点与右孩子结点的连线； （3）整理所有保留的和添加的连线，使每个结点的孩子结点连线顺序位于下方孩子结点位置。
图7―17 给出了一棵二叉树还原为树的过程 和还原后的树结构
7.4 链式存储结构的二叉树设计 由于二叉树是一种递归定义（一个结点是一个二叉树；一个根结点和根结点的左子树和右子树是一个二叉树），对结点的操作也能对二叉树操作，所以第一种方法的实现比较容易，基本的二叉树操作函数的实现方法也比较简明易懂。
第一种方法的缺点是当二叉树结构复杂时，结点类不能给出二叉树结点之间关系操作的成员函数，用外部函数设计这些操作也不及第二种方法设计的规范；此外，当二叉树结构复杂时第一种方法应用程序需定义的结点类对象会很多。 本节我们首先讨论二叉树的第一种方法的设计，然后讨论在第一种方法基础上的二叉树基本操作的函数实现方法，最后讨论第二种方法的二叉树设计。
7.4.1 二叉树结点类 ＃include<iostream.h> ＃include<stdlib.h> template<class T>class BiTree Node { private: BiTreeNode<T>*leftChild; //左子树指针 BiTreeNode<T>*rightChild; //右子树指针
public: Tdata;//数据域 //构造函数和析构函数 BiTree Node():leftChild(NULL),right Child(NULL){ } BiTree Node(T item,BiTree Node<T>*left=NULL, BiTree Node<T>*right=NULL): data(item),left Child(left),right Child(right){} BiTree Node(){} //结点操作的成员函数
BiTree Node<T>*&Left(void) //注意返回值类型为指针的引用类型 {returnleft Child;} BiTreeNode<T>*&Right(void) {returnright Child;} };
访问指针域的成员函数Left()和Left()的返回值类型设计为指针的引用类型是十分必要的，这不仅可取得该指针所指结点的值，而且还可以给该结点赋值；否则，要取得私有数据成员left Child和right Child的值和修改它们的值时就一定要通过设计成二叉树结点类的友元来实现。
//定义一个由结点构造二叉树的外部函数 template<classT> BiTree Node<T>*GetTree Node(Titem,BiTree Node<T>*left=NULL, BiTree Node<T>*right=NULL) { BiTree Node<T>*p;
p=new BiTreeNode<T>(item,left,right); if(p==NULL) { cerr<<"内存分配失败!＼n"; exit(1); } returnp; }
7.4.2 二叉树的遍历 在7.3.3节我们讨论了二叉树的四种遍历算法，本节我们给出基于二叉树结点类的这四种遍历算法的C++函数。其中，visit(item)函数可在应用程序中定义为任意的操作，如7.4.4节的应用示例中定义visit(item)函数为显示结点数据域值。注意由于二叉树是递归定义的，这里的结点t表示了二叉树的根结点。 template<classT> void PreOrder(BiTree Node<T>*&t,voidvisit(Titem)) //使用visit(item)函数前序遍历二叉树t {
if(root!=NULL) { visit(t->data); PreOrder(t->Left(),visit); PreOrder(t->Right(),visit); } }
注意，上述前序遍历二叉树算法中，参数visit是函数参数。此时，函数voidvisit(Titem)中的参数item定义为模板T类型，具体遍历访问时使用的是t→data参数。 template<classT> voidIn Order(BiTree Node<T>*&t,voidvisit(Titem)) //使用visit(item)函数中序遍历二叉树t { if(t!=NULL) In Order(t->Left(),visit);
visit(t->data); InOrder(t->Right(),visit); } } template<classT> Void PostOrder(BiTree Node<T>*&t,voidvisit(Titem)) //使用visit(item)函数后序遍历二叉树t
{ if(t!=NULL) PostOrder(t->Left(),visit); PostOrder(t->Right(),visit); visit(t->data); } }
二叉树的层序遍历就是逐层访问二叉树的结点。二叉树的层序遍历算法需要使用一个队列存放后面要访问的结点，并用队列构造这些结点的访问顺序。 ＃include"LinQueue.h“ //包含模板链式队列类 template<classT> void LevelScan(BiTree Node<T>*&t,voidvisit(Titem)) //使用visit(item)函数层序遍历二叉树t { Lin Queue<BiTreeNode<T>*>q; //定义模板链式队列类对象 BiTreeNode<T>*p;
q.QInsert(t); //根结点入队列 while(!q.Queue Empty()) { p=q.QDelete();//出队列 visit(p->data);//访问根结点 if(p->Left()!=NULL)q.QInsert(p->Left()); //根结点的左子树入队列 if(p->Right()!=NULL)q.QInsert(p->Right( )); //根结点的右子树入队列 }
7.4.3 二叉树遍历的应用 计算二叉树的深度、计算二叉树的叶子结点个数、在二叉树中查找元素、分层显示二叉树结点数据域值等都要遍历二叉树，因此这些问题都是二叉树遍历的应用。二叉树的遍历分需要和不需要考虑遍历次序的两类应用问题，像计算二叉树的深度、计算二叉树的叶子结点个数和在二叉树中查找元素等问题就不需要考虑遍历的次序，而像分层显示二叉树结点数据域值等问题就需要考虑遍历的次序。
1.不需要考虑遍历次序的遍历应用问题 这里我们讨论计算二叉树的深度、计算二叉树的叶子结点个数和在二叉树中查找元素的遍历问题。 template<classT> int Depth(BiTree Node<T>*&root) //返回计算出的二叉树root的深度 { int depthleft,depthright,depthval; if(root==NULL)depthval=-1; //空树的深度为0
else { depthleft=Depth(root->Left()); depthright=Depth(root->Right()); //二叉树的深度为左子树和右子树深度的较大值加根结点的深度值1 depthval=1+(depthleft>depthright?depthleft:depthright); }
Return depthval; } template<classT> Void CountLeaf(BiTreeNode<T>*&root,int&count) //计算二叉树root的叶子结点个数存于count中 { if(root!=NULL)
{ CountLeaf(t->Left(),count); CountLeaf(t->Right(),count); if(t->Left()==NULL&&t->Right()==NULL) count++; } }
在二叉树Root中，查找数据元素item的算法是一个回溯算法，当本层递归调用未查找到数据元素，且root→Left()和root→Right()的递归调用均失败时算法返回空，从而引起算法回溯到上一层的递归调用处继续查找。关于递归的回溯算法原理我们在6.6节用迷宫问题为例曾作过较详细的讨论。 template<classT> BiTree Node<T>*Find(BiTree Node<T>*&root,Titem)//在二叉树root中回溯查找数据元素item。找到时返回该结点指针，否则返回空
{ if(root==NULL)return NULL; if(root->data==item||root->data==item) Return root; BiTree Node<T>*p; if((p=Find(root->Left(),item))!=NULL)return p; if((p=Find(root->Right(),item))!=NULL)return p; Return NULL; //失败时返回空使算法回溯 }
2. 需要考虑遍历次序的遍历应用问题 这里我们讨论二叉树结点数据域值的横向显示和竖向显示问题。首先我们讨论二叉树的横向显示算法。由于二叉树的横向显示应是二叉树竖向显示的90°旋转，又由于二叉树的横向显示算法一定是中序遍历算法，所以我们把横向显示的二叉树中序遍历算法改为先右子树再根结点再左子树的RDL结构。 template<classT> void PrintTree(BiTree Node<T>*&root,int level) //二叉树root第level层结点数据域值的横向显示
{ if(root!=NULL) //如果二叉树不空 //二叉树root->Right()第level+1层结点数据域值的横向显示 Print Tree(root->Right(),level+1); if(level!=0) { //走过6*(level-1)个空格 for(inti=0;i<6*(level-1);i++)cout<<""; Cout<<"----"; //显示横线----
} cout<<root->data<<endl;//显示结点的数据域值 //二叉树root->Left()第level+1层结点数据域值的横向显示 PrintTree(root->Left(),level+1); }
下面我们讨论二叉树的竖向显示算法。因为每次队列中需要保存当前的屏幕坐标信息，所以我们需要定义屏幕坐标信息的结构体如下： struct Info { int xIndent; //结点的x坐标 int yLevel; //结点的y坐标 };
因为二叉树的竖向显示就是二叉树结点的逐层显示，所以二叉树竖向显示算法是二叉树层序遍历算法的应用。如前所述，二叉树的层序遍历算法需要使用一个队列存放后面要访问的结点并用队列构造这些结点的访问顺序。二叉树竖向显示时每个结点的坐标信息也需要和结点信息同时用队列保存，因此我们使用队列Q存放结点的指针信息，用队列QI存放该结点的坐标信息。
＃include<math.h> //包含有pow()函数 ＃include"LinQueue.h“ //包含模板链式队列类 template<classT> Void PrintVTree(BiTree Node<T>*&t) { intscreenWidth=64; //screenWidth为屏幕的宽度 intdataWidth=2; //dataWidth为孩子结点偏移量的倍数
LinQueue<BiTree Node<T>*>Q; LinQueue<Info>QI; //QI是元素为Info类型数据的队列 BiTree Node<T>*p; Infos,s1,s2; intoffset,level=-1,len,i; Q.QInsert(t);//根结点指针入队列
s.xIndent=screen Width/data Width;//计算根结点的x坐标 s.yLevel=0;//结点的y坐标 QI.QInsert(s);//根结点的坐标信息入队列 while(!Q.Queue Empty()&&!QI.QueueEmpty()) //当队列不空时 { s2=s;
p=Q.QDelete();//结点指针出队列 s=QI.QDelete();//结点坐标出队列 //走过空格 if(s.yLevel!=level)//该层结点第一次显示 { cout<<"＼n第"<<s.yLevel<<"层"; level=s.yLevel;
for(i=0;i<s.xIndent-1;i++)cout<<""; } else//该层结点以后的显示 for(i=0;i<s.xIndent-s2.xIndent;i++)cout<<""; cout<<p->data;//显示结点信息 if(p->Left()!=NULL)//当前结点的左孩子结点非空时 {
Q.QInsert(p->Left());//左孩子结点指针入队列 s1.y Level=s.yLevel+1;//y坐标为双亲结点的y坐标加1 //计算第i层结点的偏移量 offset=screen Width/pow(dataWidth,s1.yLevel+1); //计算第i层左孩子结点的x坐标；s.xIndent为双亲结点的x坐标 s1.xIndent=s.xIndent-offset;
QI.QInsert(s1);//该结点坐标入队列 } if(p->Right()!=NULL)//当前结点的右孩子结点非空时 { Q.QInsert(p->Right());//右孩子结点指针入队列 s1.yLevel=s.yLevel+1;//y坐标为双亲结点的y坐标加1 //计算第i层结点的偏移量
offset=screen Width/pow(data Width,s1.yLevel+1); //计算第i层右孩子结点的x坐标；s.xIndent为双亲结点的x坐标 s1.xIndent=s.xIndent+offset; QI.QInsert(s1);//该结点坐标入队列 } } }
7.4.4 应用示例 例7―2 构造图7―11（a）、（b）和图7―12（a）的二叉树，然后测试文件BiTreeLib.h中的函数。 下面应用示例程序中root1为图7―11（a）的二叉树，root2为图7―11（b）的二叉树，root3为图7―12（a）的二叉树。 void MakeCharTree(BiTreeNode<char>*&root,intnum){ BiTreeNode<char>*b,*c,*d,*e,*f,*g,*h,*i; BiTreeNode<char>*j,*k,*l,*m,*n,*o,*null=NULL;
if(num==1)//构造图7―11（a）的二叉树 { g=GetTreeNode(′G′); d=GetTreeNode(′D′,g); b=GetTreeNode(′B′,d,null); e=GetTreeNode(′E′); f=GetTreeNode(′F′); c=GetTreeNode(′C′,e,f); root=GetTreeNode(′A′,b,c);
} elseif(num==2) //构造图7―11（b）的二叉树 { g=GetTreeNode(′G′); d=GetTreeNode(′D′,null,g); b=GetTreeNode(′B′,d); e=GetTreeNode(′E′); f=GetTreeNode(′F′); c=GetTreeNode(′C′,e,f); root=GetTreeNode(′A′,b,c);
} elseif(num==3) //构造图7―12（a）的二叉树 { h=GetTreeNode(′H′); i=GetTreeNode(′I′); d=GetTreeNode(′D′,h,i); j=GetTreeNode(′J′); k=GetTreeNode(′K′);
e=GetTreeNode(′E′,j,k); b=GetTreeNode(′B′,d,e); l=GetTreeNode(′L′); m=GetTreeNode(′M′); f=GetTreeNode(′F′,l,m); n=GetTreeNode(′N′); o=GetTreeNode(′O′); g=GetTreeNode(′G′,n,o); c=GetTreeNode(′C′,f,g); root=GetTreeNode(′A′,b,c); }
为测试遍历函数，我们设计简单的显示结点的数据域值函数作为调用遍历函数时的visit()函数类型实际参数。 void Printchar(char item) { cout<<item<<""; }
为使7.5节能继续使用这里建立的二叉树，我们把上述函数放在文件 "BiTreeExample.h"中。 测试主程序如下： ＃include<conio.h> ＃include"BiTreeLib.h" ＃include"BiTreeExample.h" voidmain(void) { BiTreeNode<char>*root1,*root2; MakeCharTree(root1,1);
MakeCharTree(root2,2); cout<<"root1树为："<<endl; PrintTree(root1,0); cout<<"root2树为："<<endl; PrintVTree(root2); cout<<"＼nroot2树后序遍历结点次序为:"; PostOrder(root2,Printchar); intleafCount=0; CountLeaf(root2,leafCount);
cout<<"＼nroot2树的叶子结点个数为:"<<leafCount; } 程序的运行结果如下： root1树为： ----F ----C----E A ----B ----D
----G root2树为： 第0层 A 第1层 B C 第2层 D E F 第3层 G root2树后序遍历结点次序为:GDBEFCA root2树的叶子结点个数为:3
7.4.5 二叉树类 在二叉树结点类的基础上设计出的二叉树类的数据成员是指向二叉树根结点的指针，共有成员函数除构造函数和析构函数外，一般应包括7.3.3节讨论的二叉树的操作。作为讲述基本概念和基本内容的教材，下面给出的二叉树类共有成员函数只包括了其中的一部分操作。其余操作的成员函数实现方法读者可作为练习自己设计实现。
＃include<iostream.h> ＃include<stdlib.h> ＃include"BiTreeNode.h" template<classT>classBiTree { private: BiTreeNode<T>*root;//根结点指针 //实现相应共有成员函数的算法 voidPreOrder(BiTreeNode<T>*&t,void(*visit)(Titem));
Void InOrder(BiTreeNode<T>*&t,void(*visit)(Titem)); Void PostOrder(BiTreeNode<T>*&t,void(*visit)(Titem)); public: //构造函数和析构函数 BiTree():root(NULL){};//构造函数 ~BiTree(){};//析构函数 //构造二叉树 Void MakeTree(const T &item,BiTree<T>&left,BiTree<T>&right);
//遍历访问树 Void PreOrder(void(*visit)(Titem)); //前序遍历访问树 Void InOrder(void(*visit)(Titem)); //中序遍历访问树 Void PostOrder(void(*visit)(Titem)); //后序遍历访问树 };
1.构造树和删除树的根结点 template<classT> Void BiTree<T>::Make Tree(const T &item,BiTree<T>&left,BiTree<T>&right) //构造数据域为item左子树为left右子树为right的二叉树 { root=new BiTreeNode<T>(item,left.root,right.root); }
利用此函数构造的图7―14的二叉树结构如图7―18所示。其中每个子树前的root为该子树的根结点指针。如果加上语句left 利用此函数构造的图7―14的二叉树结构如图7―18所示。其中每个子树前的root为该子树的根结点指针。如果加上语句left.root=right.root=NULL，则只有最后二叉树的根结点指针root，各个子树的根结点指针root均为空指针，其结构和图7―14的二叉树结构相同。这种结构的二叉树子树只能由双亲结点的左子树指针或右子树指针指示，不能由子树的根结点指示。从严格的二叉树的递归定义看，二叉树结构应如图7 -18所示。
图7―18 用Make Tree()构造的图7―14的二叉树结构
2. 遍历成员函数 实现二叉树类成员函数的遍历算法与前述基于二叉树结点类的遍历算法不同之处是：二叉树类成员函数中不用给出二叉树对象的根结点指针root，但要实现二叉树的递归遍历这个参数是必须的，所以需要再设计一个和二叉树结点类的遍历算法相同的私有成员函数具体实现二叉树的递归遍历。
template<classT> void BiTree<T>::PreOrder(void(*visit)(Titem)) //用visit(item)函数前序遍历访问当前对象的二叉树的共有函数 { PreOrder(root,visit); } template<classT> Void BiTree<T>::Pre Order(BiTree Node<T>*&t,void(*visit)(Titem))
//用visit(item)函数前序遍历访问二叉树t的私有函数 { if(root!=NULL) visit(t->data); Pre Order(t->Left(),visit); Pre Order(t->Right(),visit); } }
例7―3 编写一个图7―14的二叉树构造和前序遍历输出显示测试程序。图7―14的二叉树构造和前序遍历输出显示测试程序如下： ＃include"BiTree.h" template<classT> void Visit(Titem) { cout<<item<<""; } void main(void) {
BiTree<char>a,b,c,d,e,f,g,null; g.Make Tree(′G′,null,null); d.Make Tree(′D′,null,g); b.Make Tree(′B′,d,null); e.Make Tree(′E′,null,null); f.Make Tree(′F′,null,null); c.Make Tree(′C′,e,f); a.Make Tree(′A′,b,c);
Cout<<"前序遍历序列为："; a.PreOrder(Visit); } 程序运行结果为： 前序遍历序列为：A B D G C E F
7.5 二叉树遍历游标类 由于二叉树遍历的具体方法有许多种，而每种方法实现遍历的界面都一样，因此我们使用1.3.9节的纯虚函数和抽象类方法，把二叉树遍历的游标类设计为抽象类形式的基类，把二叉树中序遍历的游标类、二叉树前序遍历的游标类、二叉树后序遍历的游标类和二叉树层序遍历的游标类设计为该基类的派生类。
这样，一方面对于派生类中共同的数据成员和成员函数方法可一次完成设计；另一方面，各种不同的二叉树遍历游标类由于都是基类的派生类，所以有着相同的界面，从而方便使用和维护。 我们设计二叉树遍历的游标类基类如下： ＃include"BiTreeNode.h" template<classT>classBiTreeIterator { protected: BiTreeNode<T>*root; //二叉树根结点指针
BiTree Node<T>*current;//二叉树当前结点指针 Intite Complete;//是否到达尾部标记，由派生类维护 public: //构造函数 BiTreeIterator(BiTreeNode<T>*tree): root(tree),current(NULL),iteComplete(1){} //应用程序设计循环遍历需要的成员函数
Virtual void Next(void)=0;//纯虚函数 Virtual void Reset(void)=0;//纯虚函数 Virtual int EndOfBiTree(void)const//返回结束标记值 {returnite Complete;} //数据检索和修改成员函数 T&Data(void); };
template<classT> T& Bi TreeIterator<T>::Data(void) { if(root==NULL) cout<<"二叉树空!"<<endl; exit(1); } Return current->data; }
和二叉链表遍历的设计方法类同，类BiTree Iterator中的成员函数Reset()、Next()和End Of BiTree()构成了二叉树遍历的成员函数。二叉树的每种遍历方法都使用尾部标记ite Complete的值作为判断是否已到达尾部，所以End Of BiTree()成员函数设计成非纯虚函数的成员函数；由于二叉树有多种不同的遍历方法，所以Reset()和Next()成员函数设计成纯虚函数。
二叉树非空时Reset()成员函数使ite Complete的值为0；Next()成员函数每次查找到当前结点的下一个结点（不同的遍历找下一个结点的方法不同），当遍历结束时使ite Complete的值为1；End Of BiTree()成员函数返回ite Complete的值，即当遍历未结束时返回0，结束时返回1。这样，这三个成员函数即可让应用程序构造二叉树的循环遍历算法。
7.5.1 二叉树中序遍历游标类 对二叉树的中序遍历，由于中序递归遍历算法是由算法本身的不断自调用实现的，所以中序递归遍历算法是不可分解的。但当我们自己设计一个堆栈模仿系统的运行时，我们就有非递归的二叉树中序遍历算法。 非递归的二叉树中序遍历算法为： （1）设置一个堆栈并初始化。 （2）使临时指针等于二叉树根结点指针。如二叉树根结点不空，令结束标记为0；否则为1。
（3）当临时指针的左孩子结点指针不空时，继续执行；否则转向步骤（4）； ·把临时指针入堆栈； ·临时指针等于它的左孩子结点指针； （4）如果最后一个不为空的临时指针存在，则使临时指针等于最后一个不为空的临时指针；否则令结束标记为1。 （5）如果结束标记为1，转步骤（8）；否则继续执行。 （6）访问临时指针结点。
（7）如果临时指针的右孩子指针不空，则使临时指针等于它的右孩子结点指针，转到步骤（3）；否则如果堆栈不空，则退栈使临时指针等于栈顶结点指针，转向步骤（5）；否则令结束标记为1，转向步骤（5）。 （8）算法结束。 图7―19给出了上述算法的一个5个结点二叉树例子的图示。图中t为临时指针，堆栈为顺序堆栈，堆栈中用字符A表示指向该结点的指针。按照算法，首先，分别使A和B结点的指针入堆栈，D结点的左孩子指针为空，访问结点D；结点D的右孩子指针为空，但堆栈不空，
退栈使t等于B结点指针，访问结点B；使t等于B结点的右孩子结点指针，E结点的左孩子指针为空，访问E结点；退栈使t等于A结点指针，访问A结点；使t等于A结点的右孩子结点指针，访问结点C；最后因t的右孩子指针空并且堆栈空，所以算法结束。
图7―19 非递归的二叉树中序遍历算法图示
我们在下面的二叉树中序遍历游标类中定义Reset()成员函数为实现步骤（1）至步骤（4），定义End Of BiTree()成员函数为返回结束标记的值，定义Next()成员函数为实现步骤（7）。由于上述设计的成员函数中都包含相同的部分，我们再将这部分分离为私有成员函数GoFarLeft()。这样我们就完成了二叉树中序遍历游标类的设计分析。二叉树中序遍历游标类的具体设计如下：
＃include"LinStack.h“ //包含模板的链式堆栈 ＃include"BiTreeIterator.h" template<classT> classBiTrInIterator:publicBiTreeIterator<T>//共有方式继承 { protected: LinStack<BiTreeNode<T>*>S;//存放二叉树结点指针的堆栈 BiTreeNode<T>*GoFarLeft(BiTreeNode<T>*&t); //寻找最左孩子指针
public: BiTrInIterator(BiTreeNode<T>*&tree)://构造函数 BiTreeIterator<T>(tree){}//调用基类的构造函数 virtualvoidNext(void); virtualvoidReset(void); }; template<classT> BiTreeNode<T>*BiTrInIterator<T>::GoFarLeft(BiTreeNode<T>*&t)
//寻找最左孩子的指针由函数返回 { if(t==NULL)return NULL; while(t->Left()!=NULL)//寻找最左孩子的指针 S.Push(t);//逐层入栈 t=t->Left();//t等于左孩子指针 } returnt;//返回不为空的最左孩子的指针
} template<classT> Void Bi TrInIterator<T>::Reset(void) // { S.ClearStack();//堆栈清空 Ite Complete=(root==NULL); //赋标记值 if(root==NULL)return; current=Go FarLeft(root); //当前结点指针指向中序遍历的第一个结点
} template<classT> Void Bi TrInIterator<T>::Next(void) //使当前结点指针指向当前结点的中序遍历下的下一个结点。到尾部时标记置为1 { if(ite Complete==1) cerr<<"已到二叉树尾!"<<endl; exit(1);
} //寻找当前结点的中序遍历下的下一个结点由当前结点指针指示 if(current->Right()!=NULL) current=GoFarLeft(current->Right()); elseif(!S.StackEmpty()) current=S.Pop(); //到达尾部时标记置为1 else iteComplete=1; }
用图7―11（b）作为二叉树例子的测试程序如下： ＃include"BiTrInIterator.h" ＃include"BiTreeExample.h" voidmain(void) { BiTreeNode<char>*root2; //定义二叉树结点类指针变量 MakeCharTree(root2,2); //构造图7―11（b）的二叉树由指针root2指示
BiTrInIterator<char>biTrInIter(root2); Cout<<"中序遍历序列为："; for(biTrInIter.Reset();!biTrInIter.EndOfBiTree();biTrInIter. Next())cout<<biTrInIter.Data()<<""; } 连接root2到二叉树中序游标类的定义语句 BiTrInIterator<char>biTrInIter(root2)
将自动调用二叉树中序游标类的构造函数，使二叉树中序游标类的数据成员root等于二叉树root2，因此二叉树中序游标类对象biTrInIter具体遍历操作的是二叉树root2。 程序的运行结果为： 中序遍历序列为：D G B A E C F
7.5.2 二叉树前序遍历游标类 二叉树前序遍历游标类的设计与二叉树中序遍历游标类的设计类同，不同之处是二叉树前序遍历是先访问根结点，然后是前序遍历根结点的左子树结点，最后是前序遍历根结点的右子树结点。因此，根结点应为二叉树前序遍历的第一个结点，左子树结点前序遍历完后的下一个结点应是右子树结点前序遍历。
而要借助堆栈达到按这样的次序进行访问的方法就是在把根结点指针（第一次）或退栈取得的结点指针（非第一次）作为当前结点指针后，把当前结点指针的右子树结点指针和当前结点的左子树结点指针入栈。这样，Reset()成员函数在使当前结点指针等于根结点指针后，应再把根结点的右子树结点指针和根结点的左子树结点指针入栈；Next()成员函数当堆栈不空时把退栈得到的结点指针作为当前结点指针，然后把当前结点的右子树结点指针和当前结点的左子树结点指针入栈。
二叉树前序遍历游标类的具体设计如下： ＃include"LinStack.h" ＃include"BiTreeIterator.h" template<classT>classBiTrPreIterator:publicBiTreeIterator<T { protected: LinStack<BiTreeNode<T>*>S;//存放二叉树结点指针的堆栈public: BiTrPreIterator(BiTreeNode<T>*&tree): BiTreeIterator<T>(tree){}
virtualvoidNext(void); virtualvoidReset(void); }; template<classT> voidBiTr PreIterator<T>::Reset(void) { S.ClearStack(); iteComplete=(root==NULL); if(root==NULL)return;
current=root ; //根结点指针为当前结点指针 if(root->Right()!=NULL)S.Push(root->Right()); //右子树入栈 if(root->Left()!=NULL)S.Push(root->Left()); //左子树入栈 } template<classT> voidBiTrPreIterator<T>::Next(void) { if(iteComplete==1)
{ cerr<<"已到二叉树尾!"<<endl; exit(1); } if(!S.Stack Empty()) current=S.Pop(); //退栈取得当前结点指针
if(current->Right()!=NULL)S.Push(current->Right()); //右子树入栈 if(current->Left()!=NULL)S.Push(current->Left()); //左子树入栈 }else Ite Complete=1;//堆栈空时置结束标记为1 } 上述二叉树前序遍历游标类放在文件"BiTrPreIterator.h"中。
7.5.3 二叉树层序遍历游标类 二叉树层序遍历的次序是：根结点，根结点的左子树结点，根结点的右子树结点，根结点的左子树结点的左子树结点，根结点的左子树结点的右子树结点，如此等等一直到最下层最右边的结点为止。
在7.4.2节讨论的层序遍历算法虽然不是递归的，也需要把算法过程分解为几个函数完成。Reset()成员函数在使当前结点指针等于根结点指针后，再把根结点的左子树结点指针和根结点的右子树结点指针入队列；Next()成员函数在队列不空时把出队列得到的结点指针作为当前结点指针，然后把当前结点的左子树结点指针和当前结点的右子树结点指针入队列。
二叉树层序遍历游标类的具体设计如下： ＃include"LinQueue.h"//包含模板的链式队列 ＃include"BiTreeIterator.h" template<classT>classBiTrLeIterator:publicBiTreeIterator<T>{ protected: LinQueue<BiTreeNode<T>*>Q; //存放二叉树结点指针的队列 public:
BiTrLeIterator(BiTreeNode<T>*&tree): BiTreeIterator<T>(tree){} virtualvoidNext(void); virtualvoidReset(void); }; template<classT> voidBiTrLeIterator<T>::Reset(void) { Q.ClearQueue(); iteComplete=(root==NULL);
if(root==NULL)return; current=root;//根结点指针为当前结点指针 if(root->Left()!=NULL)Q.QInsert(root->Left()); //左子树入队列 if(root->Right()!=NULL)Q.QInsert(root->Right()); //右子树入队列 } template<classT> voidBiTrLeIterator<T>::Next(void)
{ if(iteComplete==1) cerr<<"已到二叉树尾!"<<endl; exit(1); } if(!Q.QueueEmpty()) current=Q.QDelete(); //出队列取得当前结点指针
//左子树的根结点指针入队列 if(current->Left()!=NULL)Q.QInsert(current->Left()); //右子树的根结点指针入队列 if(current->Right()!=NULL)Q.QInsert(current->Right());} else iteComplete=1;//队列空时置结束标记为1 }
由于二叉树的后序遍历次序为后序遍历二叉树根结点的左子树，后序遍历二叉树根结点的右子树，最后访问根结点，所以，借助堆栈实现时每个结点要入栈3次。第一次退栈得到该结点的左子树结点后再入栈，第二次退栈得到该结点的右子树结点后再入栈，在结点第三次从堆栈中退出时才把它标记为将要访问的当前结点。关于二叉树后序遍历游标类的设计由读者作为作业完成。
7.6 线索二叉树 7.6.1 线索二叉树的存储结构 二叉树是非线性结构，从前面的讨论我们知道，以某种规则遍历二叉树时将把二叉树中的结点按该规则排列成一个线性结构，这实质上是对一个非线性结构进行线性化操作。但是，我们每次按某种规则遍历二叉树时都没有把遍历时得到的每个结点的后继结点信息和前驱结点信息保存下来，因此，我们不能像操作双向链表一样操作二叉树。
保存这种按某种规则遍历二叉树时得到的每个结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树的存储结构。 分析二叉树结构可以发现，在有n个结点的二叉存储结构的二叉树中必定存在n+1个空链域。我们希望能利用这些空链建立起每个结点的前驱结点信息和后继结点信息。
我们作如下规定：当某结点的左指针为空时，令该指针指向按某种方式遍历二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方式遍历二叉树时得到的该结点的后继结点。仅仅这样做会使我们不能区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。我们再在二叉存储结构的结点结构上增加两个标志位来区分这两种情况。
图7―20 线索二叉树 （a）中序线索二叉树；（b）前序线索二叉树； （c）后序线索二叉树
图7―20 线索二叉树 （a）中序线索二叉树；（b）前序线索二叉树； （c）后序线索二叉树
图7―20 线索二叉树 （a）中序线索二叉树；（b）前序线索二叉树； （c）后序线索二叉树
7.6.2 线索二叉树类 线索二叉树有许多种，它们的设计方法与二叉树游标类的类同。我们先设计一个线索二叉树类。线索二叉树类既实现各种不同的线索二叉树类的相同操作，又为各种不同的线索二叉树类提供相同的界面。
线索二叉树类的成员函数First()、Next()和End Of Next()可构成应用程序的正向（从前向后）二叉树遍历的循环结构；线索二叉树类的成员函数Last()、Prior()和End Of Prior()可构成应用程序的反向（从后向前）二叉树遍历的循环结构。不同的遍历方法实现成员函数First()、Next()、Last()和Prior()的算法将不同，因此这些成员函数在基类中定义为纯虚函数，即成员函数的具体实现算法将在派生类中定义。线索二叉树类如下：
template<class T>classThreadIterator { protected: BiTrThNode<T>*root; BiTrThNode<T>*current; int nextComplete; //正序遍历结束标记，由派生类维护 int priorComplete; //反序遍历结束标记，由派生类维护
public: //构造函数 ThreadIterator(BiTrThNode<T>*&tree); //算法需要的成员函数 Virtual voidFirst(void)=0； //纯虚函数 Virtual voidNext(void)=0; //纯虚函数 Virtual voidLast(void)=0; //纯虚函数 Virtual voidPrior(void)=0; //纯虚函数 Virtual intEndOfNext(void)const
{return nextComplete;} virtualintEndOfPrior(void)const {return priorComplete;} //数据检索和修改成员函数 T&Data(void); }; template<classT> ThreadIterator<T>::ThreadIterator(BiTrThNode<T>*&tree) //构造函数
{ root=tree; current=root; if(tree==NULL) Next Complete=1; Prior Complete=1; } else Next Complete=0;
priorComplete=0; } } template<classT> T& ThreadIterator<T>::Data(void) //返回线索二叉树的数据域值 { if(root==NULL)
{ cout<<"二叉树空!"<<endl; exit(1); } Return current->data; } 上述线索二叉树类放在文件ThreadIterator.h中。
7.6.3 中序线索二叉树类 中序线索二叉树类中除要具体定义线索二叉树类中的构造正向循环和反向循环的4个纯虚函数外，还要定义中序线索化二叉树成员函数。中序线索化二叉树成员函数实现在中序遍历二叉树的过程中给每个结点建立中序下的线索。当然这个成员函数也可放在构造函数中实现。单独定义的优点是，当线索二叉树类的对象没有进行中序线索化操作时还可按一般二叉树看待。
＃include"ThreadIterator.h" template<classT> classInThreadIterator:publicThreadIterator<T> //共有方式继承 { private: voidInThread(BiTrThNode<T> *¤t,BiTrThNode<T>*&pre); public:
//构造函数 InThreadIterator(BiTrThNode<T>*&tree):ThreadIterator<T>(tree){} voidCreatInThread();//中序线索化二叉树 Virtual voidFirst(void); Virtual voidNext(void); Virtual voidLast(void); Virtual voidPrior(void); };
template<classT> voidInThreadIterator<T>::CreatInThread() //中序线索化二叉树 { BiTrThNode<T>*t=root; //保存原二叉树根结点指针 root=newBiTrThNode<T>; //建立头结点 root->leftThread=0; root->rightThread=1; if(t==NULL) //当为空树时
{ root->leftChild=root; root->rightChild=root; } else//当为非空树时 current=root->leftChild=t; //第一个结点的左指针 root->leftThread=0; //第一个结点的左线索 BiTrThNode<T>*pre=root; //定义临时指针pre InThread(current,pre); //线索化二叉树
pre->rightChild=root; //最后一个结点的右指针 pre->rightThread=1; //最后一个结点的右线索 root->rightChild=pre; //第一个结点的右指针 root->rightThread=1; //第一个结点的右线索 } } template<classT> voidInThreadIterator<T>::InThread(BiTrThNode<T> *¤t, BiTrThNode<T>*&pre)
//中序线索化二叉树。current为当前指针，pre为当前结点的中序前驱结点指针 { if(current!=NULL) InThread(current->leftChild,pre); //中序线索化左子树二叉树 if(current->leftChild==NULL) //当前结点左指针为空指针时 current->leftChild=pre;//建立左线索指针 current->leftThread=1;//建立左线索标记
} if(pre->rightChild==NULL) //前驱结点右指针为空指针 { pre->rightChild=current; //建立右线索指针 pre->rightThread=1; //建立右线索标记 pre=current; //前驱结点指针等于当前结点指针 InThread(current->rightChild,pre); //中序线索化右子树二叉树 } }
在线索二叉树中定义的root指针是固定的，定义的current指针是随着成员函数改变的。上述成员函数的参数设计成指针的引用类型，这样每次对象调用时改变的是调用对象的current指针值和pre指针值，否则调用对象的current指针不会相应改变；由于在成员函数CreatIn Thread()中调用成员函数In Thread(current,pre)时参数pre应等于root，为了不改变对象的root指针值，成员函数CreatIn Thread()中在调用In Thread(current,pre)前定义了等于root的临时指针变量。
template<classT> voidInThreadIterator<T>::First(void) //使当前结点指针current指向第一个结点 { current=root;//从根结点开始 //使current指针指向第一个结点 while(current->leftThread==0)current=current->leftChild; if(current==root)nextComplete=1;//当二叉树为空时
elsenextComplete=0;//当二叉树非空时 } 中序二叉树的第一个结点是二叉树中最左下的结点。template<classT> voidInThreadIterator<T>::Next(void) //使当前结点指针指向当前结点的下一个结点。到尾部时正序结束标记置为1 { if(nextComplete==1)
{ cerr<<"已到二叉树尾!"<<endl; exit(1); } //使当前结点指针指向当前结点的下一个结点 BiTrTh Node<T>*p=current->right Child; if(current->right Thread==0) while(p->left Thread==0)p=p->left Child; current=p; if(current==root)next Complete=1;
寻找中序二叉树中当前结点的下一个结点的算法是：若当前结点的右子树指针是线索，则当前结点的下一个结点是当前结点的右线索结点；否则，当前结点的下一个结点是当前结点的右孩子结点的最左下结点。 template<class T> void In ThreadIterator<T>::Last(void) //使当前结点指针current指向最后一个结点 { current=root->right Child; //使current指向中序下的最后一个结点
if(current==root)prior Complete=1; Elseprior Complete=0; } template<classT> voidInThreadIterator<T>::Prior(void) //使当前结点指针指向当前结点的前一个结点。到头部时反序结束标记置为1 {
if(prior Complete==1) { cerr<<"已到二叉树头!"<<endl; exit(1); } BiTrTh Node<T>*p=current->left Child; if(current->left Thread==0) while(p->right Thread==0)p=p->right Child; current=p; if(current==root)priorComplete=1; }
寻找当前结点的前驱结点的算法与寻找当前结点的后继结点算法非常类似，只是左右孩子指针和左右线索标记互换了一下。可见，中序遍历是一种对称遍历。用图7―11（b）作为二叉树例子的测试程序如下： ＃include<iostream.h> ＃include"BiTrThNode.h" ＃include"BiTreeThExample.h" ＃include"InThreadIterator.h" void main(void) {
BiTrThNode<char>*root2; MakeCharThTree(root2,2); InThreadIterator<char>threadIter(root2); threadIter.CreatInThread(); cout<<"二叉树的中序正向遍历序列为："; for(threadIter.First();!threadIter.EndOfNext();threadIter.Ne xt())cout<<threadIter.Data()<<""; cout<<endl<<"二叉树的中序反向遍历序列为："; for(threadIter.Last();!threadIter.EndOfPrior();threadIter.Pr
ior())cout<<threadIter.Data()<<""; } 程序运行结果为： 二叉树的中序正向遍历序列为：D G B A E C F 二叉树的中序反向遍历序列为：F C E A B G D
7.7 堆 7.7.1 堆的定义 设数据元素是一个有多个域的复合结构，其中有一个称为关键码的域，定义n个数据元素d0,d1,d2,…,dn-1所对应的关键码域为k0,k1,k2,…,kn-1，假设数据元素d0,d1,d2,…,dn-1按完全二叉树的顺序存放在一个一维数组中，如果当2i+1<n时有：
ki≤k2i+1（ki中的i是元素在数组中的下标,i=0,1,…,(n-1)/2）； 这样的数据元素集合称为最小堆。
与此类似，如果当2i+1<n时有： ki≥k2i+1（ki中的i是元素在数组中的下标,i=0,1,…,(n-1)/2）； 如果当2i+2<n时有： ki≥k2i+2（ki中的i是元素在数组中的下标,i=0,1,…,(n-1)/2）， 这样的数据元素集合称为最大堆。 图7―21（a）是一个最小堆；图7―21（b）是一个最大堆。为方便图示和算法设计，并不失一般性，下面均以数据元素的关键码ki表示该数据元素。
图7―21 堆 （a）最小堆；（b）最大堆
根据堆的定义可以推知堆有下面两个性质： （1）最小堆的根结点是堆中值最小的数据元素，最大堆的根结点是堆中值最大的数据元素，我们都把它们称为堆顶元素。 （2）对于最小堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是非递减有序的。对于最大堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是非递增有序的。
7.7.2 最小堆类 这里我们给出了最小堆类的定义。最大堆类的定义与最小堆类的定义类同，由读者作为练习完成。最小堆类的基本数据成员有存放数据元素的数组和当前数组元素的个数；最小堆类的基本成员函数有维持堆结构的插入元素和删除元素，以及把一个非堆的数组“堆化”成一个堆。 ＃include<iostream.h> ＃include<stdlib.h> template<class T>class MinHeap
{ private: T*heap Array; //存放数据元素的数组 Intmark Array; //标记 Int MaxHeapSize; //最大元素个数 Int heapSize; //当前元素个数 void FilterUp(inti); //插入元素后重新“堆化”时使用的方法 void FilterDown(inti); //删除元素后重新“堆化”时使用的方法
public: MinHeap(intmaxSize);//构造函数 //拷贝构造函数，用于把n个元素的数组arr“堆化” MinHeap(Tarr［］,intn); //析构函数，当标记为0（非拷贝构造）时释放数组heapArray~MinHeap(void) {if(markArray==0)deleteheapArray;} void Insert(constT&item);//插入元素item
TDelete(void); //删除堆中最小元素 TGetHeapTop()const //取堆顶数据元素 {return heapArray［0］;} intHeapSize(void)const //取当前堆中的元素个数 {return heapSize;} intHeapEmpty(void)const //堆空否 {return heapSize==0;} intHeapFull(void)cons t//堆满否 {return MaxHeapSize==heapSize;} };
1.构造函数 template<classT> MinHeap<T>::MinHeap(intmaxSize) { if(maxSize<=0) cerr<<"参数maxSize非法!"<<endl; exit(1); }
MaxHeapSize=maxSize; heapArray=new T［maxSize］; markArray=0;//置构造函数标记 }
2. 插入 插入成员函数是在原先的数据元素已经是堆的基础上，插入一个数据元素后，调整使之继续维持为一个堆。我们把要插入的数据元素放在堆尾。虽然插入前的数据元素集合构成堆，但是新的数据元素插入后可能违反堆的定义。在7―21（a）的最小堆中插入新元素8的一个例子如图7―22（a）所示，插入后显然违反了堆的定义。
图7―22 在最小堆中插入新元素的过程 （a）插入15；（b）交换15和59；（c）交换15和24
插入新元素后继续维持为一个最小堆的算法是：看新插入元素的值是否小于其双亲的值，如果不小于，则仍维持为一个最小堆，算法结束；如果小于，则交换两者的值；交换后有可能在更上一层仍然不满足堆的定义，需继续交换，直到满足堆的定义为止。 在7-21（a）的最小堆中插入新元素15后如图7―22（a）所示。由于违反了堆的定义，第一次交换15和59，交换后的状态如图7―22（b）所示。此时，本层虽然满足了堆的定义，但上一层仍然不满足堆的定义。第二次交换15和24，交换后的状态如图7―22（c）所示。
此次交换后本层和上一层都满足了堆的定义，算法结束。实际上，插入过程就是让新元素从最后一个叶结点上升到合适结点的过程，新插入结点最高可上升到根结点。 template<class T> void MinHeap<T>::FilterUp(inti) //调整插入的新元素使之上升到合适的结点位置 { int currentPos,parentPos; T target;
currentPos=i; //当前结点为i结点 target=heapArray［i］; parentPos=(i-1)/2; //计算结点i的双亲结点位置 while(currentPos!=0) //到根结点时循环结束 { if(heapArray［parentPos］<=target) break;//已经满足堆的定义循环结束 else {
heapArray［currentPos］=heapArray［parentPos］; //双亲结点下移 currentPos=parentPos;//从双亲结点位置重新开始 parentPos=(currentPos-1)/2;//计算当前结点的双亲结点位置 } heapArray［currentPos］=target;//插入新插入元素 } template<classT>
voidMinHeap<T>::Insert(constT&item) { if(heapSize==MaxHeapSize) cerr<<"堆已满!"<<endl; exit(1); } heapArray［heapSize］=item;
FilterUp(heapSize); //调整结点heapSize使之上升到合适的结点位置 heapSize++;//堆元素个数加1 } 堆是完全二叉树结构，对于完全二叉树，结点个数n和二叉树深度h的关系是h为不小于lbn的最小整数。在堆中插入一个元素的最坏情况是新插入元素要上升到根结点，所以在堆中插入一个元素最坏情况的时间复杂度为O(lbn)。
3.删除 删除成员函数是删除堆顶的最小的数据元素。删除堆顶元素后，我们用堆中最后一个元素填充堆顶位置，此时必然违反堆的定义。在7-21（a）的最小堆中删除堆顶元素后用最后一个元素填充堆顶的状态如图7―23（a）所示。
删除后继续维持为一个最小堆的算法是：令堆顶位置为当前位置，看当前位置元素的值是否小于其左右孩子中值的最小值，如果不小于，则仍维持为一个最小堆，算法结束；如果小于，则交换两者的值；交换后有可能在更下一层仍然不满足堆的定义，需继续交换，直到满足堆的定义为止。
在7-21（a）的最小堆中删除堆顶元素12后用最后一个元素80填充堆顶的状态如图7―23（a）所示；由于不满足堆的定义，第一次交换80和16，交换后的状态如图7―23（b）所示。此时，本层虽然满足了堆的定义，但下一层仍然不满足堆的定义；第二次交换80和38，交换后的状态如图7―23（c）所示，此次交换后已到达叶结点，算法结束。实际上删除过程就是让填充根结点的新元素从根结点下移到合适结点的过程填充的根结点最低可下移到叶结点。
图7―23 在最小堆中删除元素过程 （a）80填充堆顶；（b）交换80和16； （c）交换80和38
template<classT> Void MinHeap<T>::FilterDown(inti) //调整第i个结点使之下移到合适的结点位置{ intcurrentPos,childPos; Ttarget; currentPos=i; //当前结点为i结点 target=heapArray［i］; childPos=2*i+1; //计算i结点的左孩子结点位置 while(childPos<heapSize) //超出堆元素范围时循环结束 {
//childPos为当前结点的左右孩子中值较小的孩子结点位置 if((childPos+1<heapSize) &&(heapArray［childPos+1］<=heapArray［childPos］))childPos=childPos+1; if(target<=heapArray［childPos］) break;//已经满足堆的定义退出循环 else { heapArray［currentPos］=heapArray［childPos］; //孩子结点上升
currentPos=childPos; //从孩子结点位置重新开始 childPos=2*currentPos+1; //计算当前结点的左孩子结点位置 } heapArray［currentPos］=target; //把填充的堆顶元素插入 template<classT>
TMinHeap<T>::Delete(void) { if(heapSize==0) cerr<<"堆已空!"<<endl; exit(1); } Titem=heapArray［0］;//保存原堆顶元素
heapArray［0］=heapArray［heapSize-1］; //用最后一个元素填充堆顶位置 heapSize--; FilterDown(0); //调整结点0使之下移到合适的结点位置 Returnitem; //返回原堆顶元素 }
4.数组的堆化 数组的堆化是把一个有n个数据元素的非堆的数组构造成一个堆。我们把数组的堆化函数设计成拷贝构造函数，这样可方便应用程序调用。数组的堆化过程可以设计成递推过程。在完全二叉树形式的数组中，所有叶结点都满足堆的定义，令最后一个叶结点的双亲结点为当前结点，其下标为： currentPos=((n-1)-1)/2
对于结点currentPos，其左右孩子结点已满足堆的定义，使结点currentPos也满足堆的定义的过程与前面讨论过的调整第i个结点使之下移到合适结点位置的FilterDown(i)算法相同。因此，用参数currentPos调用FilterDown(currentPos)；在结点currentPos满足堆的定义后，使当前结点currentPos=currentPos-1，对于结点currentPos，其左右孩子结点已满足堆的定义，再次用参数currentPos调用FilterDown(currentPos)；这样的过程一直进行到当前结点currentPos=0，即到达根结点为止。
对数组元素集合{24,10,90,77,16,25,33,89,67}进行堆化的过程如图7―24所示。图7―24（a）是初始状态，结点旁的数字代表该结点数值在数组中的下标，下面的讨论中我们也用它们表示结点的序号。图7―24（b）是调整第一个非叶结点结点3后的状态，此时交换了77和67。图7―24（c）是调整第二个非叶结点结点2后的状态，此时交换了90和25。图7―24（d）是调整第三个非叶结点结点1后的状态，此时满足堆的定义，不需交换。图7―24（e）是调整第四个非叶结点结点0后的状态，此时交换了24和10以及24和16。当递推构造堆过程到达堆顶元素时即完成了数组的堆化。
template<classT> MinHeap<T>::MinHeap(Tarr［］,intn) { if(n<=0) cerr<<"参数n非法!"<<endl; exit(1); }MaxHeapSize=n;heapSize=n; heapArray=arr; intcurrentPos=(n-1)/2; //计算第一个非叶结点位置
while(currentPos>=0) //递推循环直到堆顶位置 { FilterDown(currentPos); //调整结点currentPos使之下移到合适的位置 currentPos--;当前结点位置减1 } markArray=1; //置拷贝构造函数标记 }
图7―24 数组的堆化 （a）初始状态；（b）调整结点3；（c）调整结点2； （d）调整结点1；（e）调整结点0
7.7.3 最小堆类的测试 为了掌握堆类对象的定义和使用方法，以及掌握在以后的应用程序中使用堆类的方法，我们在这里设计了一个堆类的简单测试程序。 ＃include"MinHeap.h" //包含最小堆类 voidPrintArray(inta［］,intn) //显示n个元素数组a的数据域值函数 { for(inti=0;i<n;i++)cout<<a［i］<<""; cout<<endl;
} voidmain(void) { inta［9］={24,10,90,77,16,25,33,89,67}; //测试数据 PrintArray(a,9); //显示测试数据 MinHeap<int>H1(a,9); //堆化9个元素数组a PrintArray(a,9); //显示堆化后的数组a while(!H1.HeapEmpty()) cout<<H1.Delete()<<""; //测试删除成员函数 cout<<endl;
MinHeap<int>H2(9);//定义有9个元素的空堆 intitem; for(inti=0;i<9;i++) { cin>>item;//键盘输入数据元素 H2.Insert(item);//测试插入成员函数 } cout<<H2.GetHeapTop()<<endl;//测试插入元素后堆顶是否是最小元素 }
程序的运行结果为： 241090771625338967 //显示的测试数据 101625672490338977 //显示的堆化后的数组元素 101624253367778990 //显示的逐个删除的堆中元素 241090771625338967 //键盘输入的依次插入堆中的9个元素 10 //显示的当前堆顶的数据元素
7.8 哈夫曼树 7.8.1 路径长度和哈夫曼树 如果二叉树中的叶结点都带有权值，我们可以把这个定义加以推广。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即：
其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。对图7―25（a）所示的二叉树，它的带权路径长度为： WPL=1×2+3×2+5×2+7×2=32 给定一组具有确定权值的叶结点，可以构造出多个具有不同带权路径长度的二叉树。例如，给定4个叶结点，设其权值分别为1,3,5,7，我们可以构造出形状不同的4棵二叉树如图7―25所示。这4棵二叉树的带权路径长度分别为：
（a）WPL=1×2+3×2+5×2+7×2=32 （b）WPL=1×2+3×3+5×3+7×1=33 （c）WPL=7×3+5×3+3×2+1×1=43 （d）WPL=1×3+3×3+5×2+7×1=29 由此可见，对于一组具有确定权值的叶结点可以构造出多个具有不同带权路径长度的二叉树，我们把其中具有最小带权路径长度的二叉树称作哈夫曼树，又称最优二叉树。可以证明，图7―25（d）的二叉树是一棵哈夫曼树。
图7―25 具有相同叶结点和不同带权路径长度的二叉树
根据哈夫曼树的定义，一棵二叉树要使其带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼提出的构造哈夫曼树的算法是： （1）由给定的n个权值{w1,w2,…,wn}构造n棵只有根结点的二叉树，从而得到一个二叉树森林F={T1,T2,…,Tn}。 （2）在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。
（3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。
图7―26 构造哈夫曼树的算法过程
7.8.2 哈夫曼编码 在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的二进制串，我们称这个过程为编码。例如，假设要传送的电文为ABACCDA，电文中只有A,B,C,D四种字符，若这四个字符采用表7-1（a）所示的编码方案，则电文的代码为00 01 00 10 10 11 00（字符编码的间空是为方便阅读所加），代码长度为14。
在这种编码方案中，四个字符的编码长度均为2，是一种等长编码。如果在编码时考虑字符在要传送的电文中出现的次数，让出现次数越高的字符采用越短的编码，构造一种不等长编码，则可使要传送的电文的代码长度最短。例如，当对上述电文中的字符A,B,C,D采用表7―1（b）所示的编码方案，则该电文的代码为0 110 0 10 10 111 0（字符编码的间空是为方便阅读所加），代码长度为13。
哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码我们称之为哈夫曼编码。
例如，图7―26所构造出的哈夫曼树的哈夫曼编码如图7―27所示。因此，权值为7的字符的编码为0，权值为1的字符的编码为100，权值为3的字符的编码为101，权值为5的字符的编码为11。 表7―1 字符的不同编码方案
图7―27 哈夫曼编码
7.8.3 哈夫曼编码问题数据结构设计 对于哈夫曼编码问题，在构造哈夫曼树时，既要求能方便地实现从双亲结点到达左右孩子结点，在由所构造的哈夫曼树进行哈夫曼编码时，又要能方便地实现从孩子结点到达双亲结点。所以，我们将哈夫曼树结点结构构造为双亲孩子结构。如前所述，双亲孩子结构既可以用常规指针实现，也可以用仿真指针实现，这里作为7.1节所讨论的仿真指针的一个复杂例子，我们采用仿真指针实现。
此外，每个结点还要有权值域。为了判断一个结点是否已加入到哈夫曼树中，每个结点要有一个标志域flag。当flag=0时，表示该结点尚未加入到哈夫曼树中；当flag=1时，表示该结点已加入到哈夫曼树中。这样，每个结点的数据结构设计为： weight parent leftChild rightChild flag
由图7―27所示的哈夫曼编码可见，从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。因此，我们需要一个数组bit［MaxBit］保存每个叶结点到根结点路径所对应的哈夫曼编码。由于是不等长编码，我们还需要一个数据域start表示每个哈夫曼编码在数组中的起始位置。这样每个叶结点的哈夫曼编码是从数组bit的起始位置start开始到数组结束位置中存放的0和1序列。存放哈夫曼编码的数组元素结构为： start Bit[0] Bit [1] … Bit[MaxBit-1]
7.8.4 哈夫曼编码问题算法设计 基于上述双亲孩子仿真指针结点结构的哈夫曼树构造算法和相应的哈夫曼编码算法如下： ＃include<iostream.h> ＃include<stdlib.h> constintMaxValue=10000; //初始设定的权值最大值 constintMaxBit=10; //初始设定的最大编码位数
constintMaxN=10; //初始设定的最大结点个数 structHaffNode //哈夫曼树的结点结构 { intweight; //权值 intflag; //标记 intparent; //双亲结点下标 intleftChild; //左孩子下标
intrightChild;//右孩子下标 }; structCode //存放哈夫曼编码的数组元素结构 { intbit［MaxN］; //数组 intstart; //编码的起始下标 intweight; //字符的权值 };
voidHaffman(intweight［］,intn,HaffNodehaffTree［］) //建立叶结点个数为n权值数组为weight的哈夫曼树haffTree { intj,m1,m2,x1,x2; //哈夫曼树haffTree［］初始化。n个叶结点共有2n-1个结点 for(inti=0;i<2*n-1;i++) if(i<n)haffTree［i］.weight=weight［i］;
else haffTree［i］.weight=0; haffTree［i］.parent=0; haffTree［i］.flag=0; haffTree［i］.leftChild=-1; haffTree［i］.rightChild=-1; } //构造哈夫曼树haffTree［］的n-1个非叶结点
for(i=0;i<n-1;i++) { m1=m2=MaxValue; x1=x2=0; for(j=0;j<n+i;j++) if(haffTree［j］.weight<m1&&haffTree［j］.flag==0) m2=m1;
x2=x1; m1=haffTree［j］.weight; x1=j; } elseif(haffTree［j］.weight<m2&&haffTree［j］.flag==0) { m2=haffTree［j］.weight; x2=j; } }
//将找出的两棵权值最小的子树合并为一棵子树 haffTree［x1］.parent=n+i; haffTree［x2］.parent=n+i; haffTree［x1］.flag=1; haffTree［x2］.flag=1; haffTree［n+i］.weight=haffTree［x1］.weight+haffTree［x2］.weight ;haffTree［n+i］.leftChild=x1; haffTree［n+i］.rightChild=x2; }
} voidHaffmanCode(HaffNodehaffTree［］,intn,CodehaffCode［］) //由n个结点的哈夫曼树haffTree［］构造哈夫曼编码haffCode［］ { Code*cd=newCode; intchild,parent; //求n个叶结点的哈夫曼编码
for(inti=0;i<n;i++) { cd->start=n-1;//不等长编码的最后一位为n-1 cd->weight=haffTree［i］.weight; //取得编码对应权值的字符 child=i; parent=haffTree［child］.parent; //由叶结点向上直到根结点
while(parent!=0) { if(haffTree［parent］.leftChild==child) cd->bit［cd->start］=0;//左孩子结点编码0 else cd->bit［cd->start］=1;//右孩子结点编码1 cd->start--; child=parent;
parent=haffTree［child］.parent; } //保存每个叶结点的编码和不等长编码的起始位 for(intj=cd->start+1;j<n;j++) haffCode［i］.bit［j］=cd->bit［j］; haffCode［i］.start=cd->start; haffCode［i］.weight=cd->weight; //记住编码对应权值的字符
} } 我们给出一个简单的图7―27所示哈夫曼编码问题的测试程序如下： voidmain(void) { inti,j,n=4; intweight［］={1,3,5,7}; HaffNode*myHaffTree=newHaffNode［2*n+1］; Code*myHaffCode=newCode［n］; if(n>MaxN)
{ cout<<"定义的n越界，修改MaxN!"<<endl; exit(1); } Haffman(weight,n,myHaffTree); HaffmanCode(myHaffTree,n,myHaffCode); //输出每个叶结点的哈夫曼编码
for(i=0;i<n;i++) { cout<<"Weight="<<myHaffCode［i］.weight<<"Code="; for(j=〖WB〗myHaffCode［i］.start+1;j<n;j++) cout<<myHaffCode［i］.bit［j］; cout<<endl; } }
程序运行结果如下： Weight=1 Code=100 Weight=3 Code=101 Weight=5 Code=11 Weight=7 Code=0