数据结构第4章

第4章树

本章学习最常用的非线性数据结构之一—树，特别是二叉树的基本表示和操作方法。

1JYP4.1树和森林的概念及其表示

层次关系：家谱中的双亲子女关系组织中的上下级关系计算机文件系统中的目录与子目录关系表达式中的括号嵌套关系，等等对这些关系及相关对象进行抽象，就形成了计算机科学中最重要的数据结构之一树。2JYP定义：一棵树是由一个或多个结点组成的有限集合，且其中（1）存在一个称为根的特定结点；（2）剩余结点被划分为n≥0个不相交集合T1,…,Tn，且Ti（1≤i≤n）也是一棵树。T1,…,Tn称为根结点的子树。这里使用了递归定义。一棵树中的每一个结点都是整个树的某一子树的根。根结点同其子树的关系可以通过这些子树的根描述。3JYP如果允许树的结点个数为零个，并将具有零个结点的树定义为空树，那么树的子树可以有无限个，这显然是不合理的。一个结点包含数据项和指向其它结点的分枝信息。通常将树根画在顶层，再逐层画出子树，这与自然界生长的树正好相反。下一页给出了一棵具有13个结点的树，为了简单起见，每个数据项用一个字母表示并用该字母标识结点，树根是A。4JYP5JYP一个结点的子树个数称为该结点的度。结点A的度是3，C的是1，G的是零。度为零的结点称为叶结点或终端结点。K，L，F，G，M，I，J是叶结点。其它结点为非终端结点。结点X的子树的根是X的子女。X是其子女的双亲。D的子女是H，I和J；D的双亲是A。同一个双亲的子女是兄弟。H，I和J是兄弟。一个结点的祖先是从根到该结点所经过的所有结点。M的祖先是A，D和H。一棵树的度是树中结点的度的最大值。图4.1的树的度为3。6JYP结点的层次递归定义为：根结点的层次为1，任何其它结点的层次为其双亲结点的层次加1。图4.1给出了树中各结点的层次。一棵树的高度或深度定义为树中结点的层次的最大值。图4.1的树的高度为4。

定义：一个森林是由n≥0个不相交的树T1,…,Tn构成的集合。森林和树的概念密切相关，因为删除一棵树的根就得到森林，而一棵树是一个森林中的一分子。7JYP可以用和广义表类似的方法表示树。例如，图4.1的树可写为A(B(E(K,L),F),C(G),D(H(M),I,J))即，根结点后面是与其子女对应的森林。该树的链表表示下图所示：8JYP度为k的树称为k叉树。可以直接用含k个子女字段的结点结构表示k叉树的结点，每个子女字段指向相应的子女结点，但这会造成存储资源的很大浪费。

引理4.1：如果用含k个子女字段的结点表示一棵具有n（n≥1）个结点的k叉树，则n(k–1)+1个子女字段的值是0。

证明：由于每个非0子女字段指向一个结点，且除了根结点以外，每个结点正好与一个指针对应，所以具有n个结点的树中非0子女字段数是n–1。具有n个结点的k叉树共有nk个子女字段，因此，0子女字段数为nk–(n–1)=n(k–1)+1。9JYP将k限定为2，则得到二叉树。这时，结点的空间代价较小，且有利于深入研究其特性和设计有效算法。二叉树结点的两个子女字段：

LeftChild

RightChild

由于k叉树的每个结点最多只有一个最左子女，且该结点最多只有一个紧邻右兄弟，因此，可以用LeftChild指向结点的最左子女，用RightChild指向该结点的紧邻右兄弟，从而可以用二叉树结点表示一般的k叉树。10JYP例如，图4.1的树可用二叉树结点表示为右边的形式：我们将重点研究二叉树。

11JYP4.2二叉树

4.2.1二叉树定义由于二叉树最多只有两个分枝，因此可扩展一般树的概念，允许二叉树为空，同时区分左、右子树，从而简化二叉树的递归定义。

定义：一棵二叉树是结点的有限集合，该集合或者为空，或者由一个根结点和两个互不相交的子二叉树组成，这两个子树分别称为左、右子树。注意，由于二叉树只有左、右两个子树，允许二叉树为空不会导致根结点有无限个子树。12JYP二叉树的抽象数据类型ADT4.1为：template<classType>

classBinaryTree{//对象：结点的有限集合，或为空，或 //由根结点和左、右子BinaryTree构成public:

BinaryTree(); //创建一个空二叉树

BooleanIsEmpty();//判断二叉树是否为空BinaryTree(BinaryTreebt1,Element<Type>item,BinaryTreebt2);//创建一个二叉树，其//左子树为bt1,右子树为bt2,根结点的数据项为item

BinaryTreeLchild();//若IsEmpty()为TRUE返回出错信 //息，否则返回*this的左子树13JYP

Element<Type>Data();//若IsEmpty()为TRUE返回出错信//息，否则返回*this的根结点的数据项

BinaryTreeRchild();//若IsEmpty()为TRUE返回出错信//息，否则返回*this的右子树};14JYP按定义，非空二叉树才属于一般树。此外，二叉树区分子女的顺序，而树却不区分。因此，下面的两棵二叉树是不同的，第一棵的右子树为空，而第二棵的左子树为空。但作为一般树，两者是相同的。关于树的术语也适用于二叉树。15JYP4.2.2二叉树性质

引理4.2[最大结点数]：（1）二叉树第i层的最大结点数是2i-1，i≥1。（2）深度为k的二叉树的最大结点数是2k–1，k≥1。证明：设Mi是第i层的最大结点数。（1）通过对层次i应用归纳法证明。当i=1，只有根结点，所以，Mi=2i-1=20=1。设i>1，并假设Mi-1=2i-2。二叉树的每个结点最多有2个子女，因此Mi=2Mi-1，根据归纳假设，Mi=2*2i-2=2i-1。（2）深度为k的二叉树的最大结点数是16JYP（2）深度为k的二叉树的最大结点数是17JYP引理4.3[叶结点数与度为2的结点数之间的关系]：

对于任何非空二叉树，若n0为叶结点数，n2为度为2的结点数，则n0=n2+1。证明：设n1为度为1的结点数，n为总结点数。由于二叉树的结点度数最多为2，所以 n=n0+n1+n2 (4.1)设B为分枝数，由于除了根结点以外，每个结点正好由一个分枝引出，所以n=B+1。所有分枝出自度为1或2的结点，所以B=n1+2n2，从而有 n=n1+2n2+1 (4.2)(4.1)–(4.2)并整理可得n0=n2+118JYP

定义：深度为k（k≥0）的满二叉树是具有2k–1个结点的二叉树。下图是一棵深度k=4的满二叉树。19JYP其中，结点从1到2k–1编号，从第1层开始，后接第2层，直至第k层。每层从左到右。通过这种编号方式，可定义完全二叉树。

定义：深度为k（k≥0）且结点个数为n的二叉树是完全二叉树当且仅当其结点与深度为k的满二叉树的1到n号结点一一对应。根据引理4.2，具有n个结点的完全二叉树的高度为log2(n+1)。此外，完全二叉树的的叶结点都在相邻的层次上。

20JYP另一种特殊的二叉树是偏斜树，包括左、右两种。下面分别是左偏斜树和完全二叉树的例子：21JYP4.2.3二叉树表示1数组表示按照完全二叉树的编号规则，可以用一维数组存储二叉树的结点。引理4.4：如果顺序表示具有n个结点的完全二叉树，那么对于任何下标为i（1≤i≤n）的结点，有（1）若i1，则结点i的双亲位于i/2；若i=1，则结点i是根，无双亲。（2）若2i≤n，则结点i的左子女位于2i，否则i没有左子女。（3）若2i+1≤n，则i的右子女位于2i+1，否则i没有右子女。22JYP证明：只需证明（2）。由（2）和在同一层从左到右编号的规则即可推出（3）。（1）是（2）和（3）的自然结论。下面仍然通过对i应用归纳法证明（2）。当i=1，显然结点i的左子女位于2，除非2>n，而这时结点i没有左子女。假设对所有j（1≤j≤i），结点j的左子女位于2j。由于紧排在结点i+1的左子女前面的是结点i的右、左子女，根据归纳假设，结点i的左子女位于2i，因此，结点i+1的左子女位于2i+2=2(i+1)，除非2(i+1)>n，而这时结点i+1没有左子女。23JYP这种表示方法可用于所有二叉树，但大多数情况下空间利用率较低。显然，数组表示对完全树是最理想的，对于偏斜树，空间利用率最低。最坏情况下，深度为k的右偏斜树需要2k–1个空间单元，但其中只有k个用于存放数据。24JYP2链接表示数组表示法对于很多二叉树空间浪费过大，而且还存在顺序表示的固有缺点，即在树的中间插入和删除结点需要移动大量其它结点。在链接表示中，每个结点有三个字段：

LeftChilddata

RightChild。25JYPclassTree; //向前声明classTreeNode{friendclassTree;private:

TreeNode*LeftChild;chardata;TreeNode*RightChild;};classTree{public:

//二叉树操作…private:TreeNode*root; //树的根结点指针};26JYP上一小节的左偏斜树和完全二叉树的链表表示如下所示：

27JYP4.3二叉树遍历与树游标

二叉树遍历是最基本的操作。一次完整的遍历可产生树中结点的一个线性序列。设L，V和R分别表示在位于一个结点时移到左子女、访问结点数据和移到右子女，并规定从左到右遍历。存在三种遍历：LVR，VLR和LRV，分别称为中序、前序和后序遍历。例如，在前序中，先访问结点再遍历其左、右子树，而在后序中，先遍历结点的左、右子树再访问结点。28JYP考虑下面的二叉树，该树表示表达式A/B*C+D。29JYP其中，每个含操作符的结点的左、右子树分别表示该操作符的左、右操作数。下面将以此树为例，说明各种遍历产生的结果。30JYP4.3.1中序遍历

设T为一棵二叉树，T的中序遍历可递归定义为：（1）若T为空，返回；（2）中序遍历T的左子树；（3）访问T的根结点；（4）中序遍历T的右子树。由此可得中序遍历的递归算法，如下一页所示。31JYPvoidTree::inorder(){//驱动器，作为Tree的公有成员函数

inorder(root);}voidTree::inorder(TreeNode*CurrentNode){//递归核心， //作为Tree的私有成员函数if(CurrentNode){

inorder(CurrentNodeLeftChild);cout<<CurrentNodedata;

inorder(CurrentNodeRightChild);}}32JYP对图4.10的二叉树调用inorder(TreeNode*)的执行过程如下，输出是：A/B*C+D，这正好是表达式的中缀。33JYP4.3.2前序遍历

设T为一棵二叉树，T的前序遍历可递归定义为：（1）若T为空，返回；（2）访问T的根结点；（3）前序遍历T的左子树；（4）前序遍历T的右子树。由此可得前序遍历的递归算法，如下一页所示。对图4.10的二叉树，其输出是：+*/ABCD，这正好是表达式的前缀。34JYPvoidTree::preorder(){//驱动器，作为Tree的公有成员函数

preorder(root);}voidTree::preorder(TreeNode*CurrentNode){//递归核心， //作为Tree的私有成员函数if(CurrentNode){cout<<CurrentNodedata;

preorder(CurrentNodeLeftChild);

preorder(CurrentNodeRightChild);}}35JYP4.3.3后序遍历

设T为一棵二叉树，T的后序遍历可递归定义为：（1）若T为空，返回；（2）后序遍历T的左子树；（3）后序遍历T的右子树；（4）访问T的根结点。由此可得后序遍历的递归算法，如下一页所示。对图4.10的二叉树，其输出是：AB/C*D+，这正好是表达式的后缀。36JYPvoidTree::postorder(){//驱动器，作为Tree的公有成员函数postorder(root);}voidTree::postorder(TreeNode*CurrentNode){//递归核心， //作为Tree的私有成员函数if(CurrentNode){

postorder(CurrentNodeLeftChild);

postorder(CurrentNodeRightChild);cout<<CurrentNodedata;}}37JYP4.3.4中序游标

树作为一种容器类也可以通过游标遍历。为此，首先需要将遍历算法转变为非递归型的。观察中序遍历的过程，CurrentNode从树根一直沿着左子女下移，直到CurrentNode为空为止。接着回溯到双亲结点，“访问”结点，然后转移到右子女，再继续上述过程。因此，可以在沿着左子女下移过程中用栈保存所经历的结点，实现递归到非递归的转换，所得非递归中序遍历算法如下一页所示。

38JYP1voidTree::NonrecInorder(){//利用栈实现非递归中序遍 //历，设模板类Stack已定义并实现Stack<TreeNode*>s;//声明并初始化栈3TreeNode*CurrentNode=root;4while(1){ 5while(CurrentNode){ //沿着左子女下移6

s.Add(CurrentNode); //加入栈中7

CurrentNode=CurrentNodeLeftChild;8}9If(!s.IsEmpty()){ //栈不空10

CurrentNode=*s.Delete(CurrentNode);//从栈中删除11

cout

<<CurrentNodedata<<endl;//访问结点12

CurrentNode=CurrentNodeRightChild;//转到右子女13}39JYP14elsebreak;15}16}分析：设树中结点个数为n。每个结点进栈一次，所以第6到7行和第10到12行共执行n次。对于每个0指针，CurrentNode将成为0一次，共2n0+n1=n0+n1+n2+1=n+1次。因此，算法的时间复杂性是O(n)。所需要的栈空间与树的深度成线性关系。40JYP函数Tree::NonrecInorder第4到15行的while循环的每次迭代都产生中序遍历的下一个元素，由此很容易实现中序遍历二叉树的游标。中序游标类InorderIterator的定义如下：classInorderIterator{public:char*next();

InorderIterator(Treetree):t(tree){CurrentNode=t.root;};private:

Treet;

Stack<TreeNode*>s;

TreeNode*CurrentNode;};41JYP其中，假设InorderIterator是类TreeNode和Tree的友元。数据成员变量s和CurrentNode记载游标的内部状态。构造函数使游标和需遍历的二叉树相关联，并完成必要的初始化。42JYPNext()的实现基本与函数Tree::NonrecInorder()第4到15行的while循环的一次迭代对应：char*InorderIterator::Next(){while(CurrentNode){

s.Add(CurrentNode);

CurrentNode=CurrentNodeLeftChild;}if(!s.IsEmpty()){

CurrentNode=*s.Delete(CurrentNode);char&temp=CurrentNodedata;

CurrentNode=CurrentNodeRightChild;return&temp;}elsereturn0; //树已遍历完，没有更多元素了}43JYP4.3.5后序游标

后序游标可在中序游标的基础上实现。但后序遍历与中序遍历不同，从左子女回溯时还不能访问结点元素，只有从右子女回溯时才能访问结点元素。因此，需要标识栈内结点的右子女是否被遍历。为此，可将栈模板实例化为如下类型：structStackItem{

TreeNode*p;

BooleanRCVisited; //RCVisited==TRUE表示回溯到结点p //时，其右子女已遍历};44JYP后序游标类PostorderIterator的定义如下，其中同样假设PostorderIterator是类TreeNode和Tree的友元。

classPostorderIterator{public:

char*next();

PostorderIterator(Treetree):t(tree){CurrentNode=t.root;};private:Treet;Stack<StackItem>s;TreeNode*CurrentNode;};45JYP实现Next()需注意标识栈内结点的右子女是否被遍历，且只返回右子女已被遍历的结点的元素，如下所示：char*PostorderIterator::Next(){

StackItemitem;while(1){while(CurrentNode){ //沿着左子女下移

item.p=CurrentNode;

item.RCVisited=FALSE;

s.Add(item); //首次进栈

CurrentNode=CurrentNodeLeftChild;}if(!s.IsEmpty()){ //栈不空

item=*s.Delete(item); //从栈中删除46JYP

CurrentNode=item.p;if(item.RCVisited=FLASE){ //从左子女回溯

item.RCVisited=TRUE;//下次回溯时，右子女已遍历

s.Add(item); //再次进栈CurrentNode=CurrentNodeRightChild;//转向右子女}else{ //从右子女回溯

char&temp=CurrentNodedata;CurrentNode=0;//下次执行时将再从栈中删取结点return&temp;}}elsereturn0; //树已遍历完，没有更多元素了}47JYP4.3.6按层次遍历

按层次遍历按照完全二叉树编号顺序访问结点，即，先访问根，接着访问根的左、右子女，如此继续，在每一层，都从最左结点到最右结点进行访问。从树根开始，将所访问结点的左、右子女存入队列，再逐个取出处理，即可实现按层次遍历。48JYPvoidTree::LevelOrder(){ //按层次遍历二叉树，设模板类 //Queue已定义并实现

Queue<TreeNode*>q; //声明并初始化队列

TreeNode*CurrentNode=root;while(CurrentNode){cout<<CurrentNodedata<<endl;if(CurrentNodeLeftChild)q.Add(CurrentNodeLeftChild);if(CurrentNodeRightChild)q.Add(CurrentNodeRightChild);

CurrentNode=*q.Delete(CurrentNode);}}49JYP

由于一个结点的子女处于下一层，且左子女先于右子女存入队列，所以结点元素以按层次遍历的顺序输出。对于图4.10的二叉树，该算法输出的结点数据序列是：+*D/CAB。50JYP4.4满足性问题

给定一个由布尔变量x0,x1,…,xn-1（n≥1）构成的命题演算的公式f(x0,x1,…,xn-1)，满足性问题要求判断是否存在x0,x1,…,xn-1的一个赋值，使得f为TRUE。假设公式已表示为二叉树，例如，(x0

x1)(x0

x2)

x2可表示为下一页的二叉树。51JYP52JYP求解满足性问题的最直接方法是对x0,x1,…,xn-1的每一个取值组合，计算公式的值。如果用布尔数组x存放x0,x1,…,xn-1，则借助例1.11中BinaryAddOne的思想，可生成n个变量的2n种取值组合。计算公式的值可通过后序遍历相应的二叉树实现。为便于得到变量当前取值，树的叶结点改为存放变量的下标。如下一页所示。

53JYP54JYP为了简化设计，分别用–3，–2和–1表示，和，于是树结点和树可定义如下：enumBoolean{FALSE,TRUE};classSatTree; //向前声明classSatNode{friendclassSatTree;private:SatNode*LeftChild;

intdata;SatNode*RightChild;};

55JYPclassSatTree{public:BooleanSatisfiability();//公式可满足则返回TRUE，并打 //印变量的取值组合，否则返回FALSEprivate:SatNode*root;Boolean*x;

intn; //变量个数BooleanPostOrderEval(SatNode*);BooleanNextCombination();};56JYP函数NextCombination生成变量的下一个取值组合，当变量取值已全部为TRUE时，返回FALSE，否则返回TRUE。BooleanSatTree::NextCombination(){inti=n-1;

while(x[i]==TRUE&&i>=0){x[i]=FALSE;i--;

}

if(i>=0){x[i]=TRUE;

returnTRUE;}

elsereturnFALSE; //变量取值已经全部为TRUE}

57JYP函数Satisfiability对x=(FALSE,FALSE,…,FALSE)，计算公式的值，若为TRUE则成功返回。否则继续生成下一个取值组合，直到计算完取值组合(TRUE,TRUE,…,TRUE)为止。BooleanSatTree::Satisfiability(){ inti;

x=newBoolean[n];

for(i=0;i<n;i++)x[i]=FALSE;do{ //由于n≥1，所以此循环至少迭代2次

if(PostOrderEval(root)==TRUE){for(i=0;i<n;i++)cout<<x[i]; //输出取值组合

delete[]x;x=0;returnTRUE; //满足}}while(NextCombination());58JYPdelete[]x;

x=0;returnFALSE; //不可满足}59JYP函数PostOrderEval后序遍历计算公式的值。BooleanSatTree::PostOrderEval(SatNode*s){BooleanleftValue,rightValue;if(s){leftValue=PostOrderEval(sLeftChild);rightValue=PostOrderEval(sRightChild);switch(sdata){case-3:return!rightValue; //操作符case-2:returnleftValue&&rightValue;//操作符

case-1:returnleftValue||rightValue; //操作符

default:returnx[sdata]; //变量下标

}}returnFALSE; //空树的值为FALSE}60JYP由于有2n种取值组合，每次计算公式的时间为O(n)，生成下一个取值组合的平均时间为O(1)，所以最坏情况下，算法的时间复杂性是O(n2n)。61JYP4.5线索二叉树

4.5.1线索在二叉树的链接表示中，0指针的个数为2n0+n1=n+1，占总指针数2n的一半还多。可用一种称为线索的指向树中其它结点的指针取代0指针。这些线索的构造规则为：（1）若结点p的RightChild字段值为0，则令其指向p的中序后继；（2）若结点p的LeftChild字段值为0，则令其指向p的中序前趋。将二叉树中的0指针替换为线索（用虚线表示）后得到线索二叉树。62JYP下面是一个线索二叉树的例子，其中结点E的左线索和右线索分别指向其中序前趋B和中序后继A。图4.1463JYP为了区分线索和普通指针，在结点中增加两个Boolean字段：

LeftThread

RightThread对于结点t，若tLeftThread==TRUE，则tLeftChild存放线索，否则存放左子女指针。右子女情况也类似。64JYP线索二叉树及其结点和中序游标的类定义：classThreadedTree;classThreadedInorderIterator;classThreadedNode{friendclassThreadedTree;friendclassThreadedInorderIterator;private:BooleanLeftThread;ThreadedNode*LeftChild;chardata;ThreadedNode*RightChild;BooleanRightThread;};65JYPclassThreadedTree{friendclassThreadedInorderIterator;public://树操作…private:ThreadedNode*root;};66JYPclassThreadedInorderIterator{public:char*Next();voidInorder();ThreadedInorderIterator(ThreadedTreetree):t(tree)

{CurrentNode=t.root;};private:ThreadedTreet;ThreadedNode*CurrentNode;};67JYP由于中序第一结点没有前趋，最后一个结点没有后继，致使这两个结点的左、右线索无定义，如图4.14中结点H和G所示。为此，引入一个头结点，使原树作为其左子树，并使头结点的RightChild作为普通指针指向其本身。图4.15表示带头结点的空树。68JYP图4.14的线索二叉树加头结点后如图4.16:69JYP不难看出，原树的中序第一个结点是头结点的后继，最后一个结点是头结点的前趋。70JYP4.5.2中序遍历线索二叉树

通过线索，可以不用栈或递归实现中序遍历。对于二叉树的任何结点x，若xRightThread==TRUE，则x的中序后继是xRightChild。否则，x的中序后继可沿x的右子女的LeftChild链寻找，找到字段LeftThread==TRUE的结点即可。函数Next（程序4.14）返回线索二叉树中结点CurrentNode的中序后继。

71JYP函数Next返回线索二叉树中结点CurrentNode的中序后继：char*ThreadedInorderIterator::Next(){

ThreadedNode*temp=CurrentNodeRightChild;

if(!CurrentNodeRightThread)

while(!tempLeftThread)temp=tempLeftChild;CurrentNode=temp;if(CurrentNode==t.root)return0; //头结点

elsereturn&CurrentNodedata;}

72JYP利用Next函数，并注意到原树的中序第一个结点是头结点的后继，很容易得到线索二叉树的中序遍历函数Inorder：voidThreadedInorderIterator::Inorder(){CurrentNode=t.root;for(char*ch=Next();ch;ch=Next())//注意，当 //CurrentNode==t.root,Next()返回中序第一元素

cout<<*ch<<endl;}

由于每个结点最多被访问两次，所以对于n个结点的线索二叉树，中序遍历的计算时间是O(n)。73JYP4.5.3后序遍历线索二叉树

不用栈或递归后序遍历线索二叉树比其它遍历更复杂一些。在后序遍历中，当首次到达一个结点时，先遍历其左子树；接着返回该结点再遍历其右子树；只有在第三次到达该结点的时候，才真正访问结点的数据。为此，使用enumAction{GOLEFT,GORIGHT,VISITNODE};

表示结点处理的不同阶段。74JYP访问完结点p后，必须定位p的双亲q，并确定q所处的处理阶段。定位p的双亲q如下图所示：75JYP

由上图可得函数Parent：ThreadedNode*ThreadedTree::Parent(ThreadedNode*p, Action*nextaction){ //假设p0 //返回p的双亲q；若p是q的左子女，*nextaction= //GORIGHT；否则*nextaction=VISITNODEThreadeNode*q=p;doq=qRightChild;while(!qRightThread); //定位p子树 //最右结点的中序后继

if(q==root)*nextaction=VISITNODE;//无后继，p不可 //能是左子女

elseif(qLeftChild==p)*nextaction=GORIGHT;//p是q //的左子女

else*nextaction=VISITNODE;//p是其双亲的右子女76JYP

if(*nextaction==VISITNODE&&q!=root){ //p不是q的 //左子女，寻找以p为根的子树最左结点 //的中序前趋，该前趋即p的双亲q=p;doq=qLeftChild;while(!qLeftThread);}returnq;}77JYP利用函数Parent，可得到后序遍历线索二叉树的算法：voidThreadedTree::PostOrder(){Actionnextaction=GOLEFT;ThreadedNode*p=rootLeftChild; //头结点的左子女 //是原树的根

while(p!=root)

switch(nextaction){caseGOLEFT: //遍历非空左子树

if(!pLeftThread)p=pLeftChild;

elsenextaction=GORIGHT;break;78JYP

caseGORIGHT: //遍历非空右子树

if(!pRightThread){p=pRightChild;nextaction=GOLEFT;}elsenextaction=VISITNODE;break;caseVISITNODE:

cout<<pdata;p=Parent(p,&nextaction);break;}}79JYP在线索二叉树的后序遍历基础上，也可以定义后序遍历游标：classThreadedPostorderIterator{public:char*First();char*Next(Boolean);voidPostorder();

ThreadedPostorderIterator(ThreadedTreetree):t(tree)

{CurrentNode=t.rootLeftChild;};private:

ThreadedTreet;

ThreadedNode*CurrentNode;

ThreadedNode*Parent(ThreadedNode*,Action*);//同前};80JYP其中，假设ThreadedPostorderIterator是类ThreadedNode和ThreadedTree的友元。函数Next的设计：为了利用后序遍历的控制结构寻找CurrentNode的后序后继，需将CurrentNode的处理阶段设置为VISITNODE。当首次到达switch控制的VISITNODE分枝时，需通过Parent和循环迭代寻找CurrentNode的后序后继。再次到达VISITNODE分枝时，CurrentNode的后序后继已确定。81JYP实现函数First可利用函数Next，但从First调用Next时的处理与一般处理不同，因此在函数Next中用参数fromfirst表示是否由First调用。函数Next的实现如下：char*ThreadedPostorderIterator::Next(Boolean

fromFirst){

//fromFirst==TRUE表示由First()调用BooleanfirstVisit=TRUE;//用于Next(FALSE)，首次到达 //VISITNODE分枝后置为FALSEActionnextAction=VISITNODE; //通过VISITNODE分枝寻 //找CurrentNode的后序后继

if(fromFirst==TRUE){ //由First()调用，特殊处理

nextAction=GOLEFT;

firstVisit=FALSE;}

82JYPwhile(CurrentNode!=t.root)

switch(nextaction){caseGOLEFT:

if(!CurrentNodeLeftThread)CurrentNode=CurrentNodeLeftChild;

elsenextAction=GORIGHT;break;

caseGORIGHT:

if(!CurrentNodeRightThread){

CurrentNode=CurrentNodeRightChild;

nextAction=GOLEFT;}elsenextAction=VISITNODE;break;83JYP

caseVISITNODE:

if(firstVisit==TRUE){CurrentNode=Parent(CurrentNode,&nextaction);firstVisit=FALSE;

}elsereturn&CurrentNodedata;break;}}return0; //无后继}

84JYP通过调用函数Next，很容易实现函数First和Postorder，如下所示：char*ThreadedPostorderIterator::First(){ //若原树为空，返 //回0，否则将CurrentNode设置为后序第一结点

CurrentNode=t.rootLeftChild;returnNext(TRUE);}voidThreadedPostorderIterator::Postorder(){for(char*ch=First();ch;ch=Next(FALSE))cout<<*ch<<endl;}85JYP4.5.4将结点插入线索二叉树

插入结点是构造线索二叉树的主要途径。此处将只研究将结点r作为结点s的右子女插入的情况。这又分两种情况：（1）s的右子树为空，插入比较简单，如下图：86JYP（2）s的右子树不空，插入后该右子树成为r的右子树。s原来的中序后继变为r的中序后继，如下图：87JYP假设函数InorderSucc(r)返回r的中序后继，函数InsertRight实现了上述插入过程：voidThreadedTree::InsertRight(ThreadedNode*s, ThreadedNode*r){//r作为s的右子女插入rRightChild=sRightChild;//见前图(1)，注意s!=t.root

rRightThread=sRightThread;

rLeftChild=s;rLeftThread=TRUE; //见前图(2)

sRightChild=r;sRightThread=FALSE;//见前图(3)if(!rRightThread){

ThreadedNode*temp=InorderSucc(r); //见前图(4)

tempLeftChild=r;}}88JYP4.6选择树

归并段是记录的有限序列，且这些记录按关键字的非递减顺序排列。假设需要将k个归并段归并为一个，这可通过反复输出关键字最小的记录完成。最小关键字可能在k个归并段的前端记录的任何一个之中，因此需要从k种可能中选出最小。最直接的方法是作k–1次比较。但对于k>2，如果利用上一次比较获得的知识，就可以使本次及以后比较的次数减少。选择树就是一种能够记载上一次比较获得的知识的数据结构。选择树是一棵完全二叉树，有胜者树和败者树两种。

89JYP4.6.1胜者树

胜者树的构造与锦标赛类似，胜者是关键字较小的记录。每个非叶结点表示比赛的胜者，根结点表示总胜者，即树中关键字最小的结点。

作为完全树，胜者树可用顺序方法表示。每个叶结点表示相应归并段的第一个记录。由于记录一般较大，每个结点实际存放的是其所表示记录的缓冲区下标。设buf[i]存放归并段i（0≤i<k）的第一个记录，则buf[i]对应的叶结点编号是k+i，这意味着叶结点存放的下标可推算得到，不必用空间存储。90JYP下图是一棵k=8的胜者树：91JYP其中，每个结点旁的数字是该结点的顺序编号。虽然每个非叶结点实际存放胜者记录下标，但为便于直观比较，图中也给出了胜者的关键字。叶结点直接用buf[i]代替。由根结点指向的记录（buf[3]）的关键字最小，可输出。归并段3的下一个记录进入buf[3]，其关键字为15。为了重构胜者树，需要沿buf[3]对应的叶结点到根结点进行一系列比赛。结点10和11比赛的胜者又是结点11（15<20），结点4和5比赛的胜者是结点4（9<15），结点2和3比赛的胜者是结点3（8<9）。92JYP新的胜者树如下图：93JYP其中，粗体字结点是发生了变化的结点。可见，比赛是在兄弟结点之间进行，结果存放在它们的双亲结点中。新一轮比赛在下一个更靠近根的层次进行。分析：除去叶结点层，树的层数为log2(k+1)，所以重构树的时间为O(log2k)。对于每一个归并到输出文件的记录都需要重构树，归并n个记录的时间是O(nlog2k)。建立初始胜者树的时间是O(k)。因此，归并k个归并段的总时间是O(nlog2k)。94JYP4.6.2败者树

胜者树重构的比赛是沿上次输出的记录缓冲区对应的叶结点到根的路径，与兄弟结点进行的。可以令非叶结点指向比赛的败者记录而不是胜者记录，从而简化重构过程。非叶结点存放败者记录下标的选择树称为败者树。实际上，结点p中的败者是与结点p的两个子女对应的比赛的胜者比赛的败者。下一页是与前面第一棵胜者树对应的败者树。其中增加了结点0，用于表示整个比赛的胜者。95JYP与前面第一棵胜者树对应的败者树96JYP输出总胜者之后，重构可通过从结点11到结点1进行比赛实现。而且，双亲结点直接指明了需要比赛的对手。可通过先建立胜者树构造初始败者树。假设记录类型的定义为：structRec{intkey;其它数据部分;};97JYP败者树的类定义如下：classLoserTree{public:LoserTree(intk); //构造函数

voidBuild(); //建立初始败者树… //其它操作private:

intk;int*l; //非叶结点Rec*buf; //记录缓冲区

intgetKey(inti);//返回结点i指向的记录缓冲区中的关键字

intgetIndex(inti); //返回结点i存放的记录缓冲区指针};98JYP构造函数的实现如下：LoserTree::LoserTree(intk){

l=newint[k]; //非叶结点空间buf=newRec[k]; //记录缓冲区空间}

99JYP建立初始败者树的算法及相应辅助函数的实现如下：voidLoserTree::Build(){ //假设记录缓冲区已输入数据

inti;for(i=k–1;i>0;i--)

if(getKey(2*i)>getKey(2*i+1)l[i]=getIndex(2*i+1);

elsel[i]=getIndex(2*i); //自下而上建立胜者树l[0]=l[1]; //总胜者

for(i=1;i<k;i++)

if(l[i]==getIndex(2*i)l[i]=getIndex(2*i+1);

elsel[i]=getIndex(2*i); //自上而下建立败者树}100JYPintLoserTree::getKey(inti){

if(i<k)returnbuf[l[i]].key;

elsereturnbuf[i-k].key;}intLoserTree::getIndex(inti){

if(i<k)returnl[i];

elsereturn(i–k);}显然，建立初始败者树的计算时间是O(k)。

101JYP4.7森林的二叉树表示及遍历

下面是一个由三棵树构成的森林：如果用二叉树表示森林中的每一棵树，再用根结点的RightChild字段将这些二叉树链接起来，则可将整个森林表示为一棵二叉树。102JYP例如，前面的森林可表示为下面的二叉树。103JYP此转换可形式化定义为：

定义：如果T1,…,Tn是一个森林，则与该森林对应的二叉树（记为B(T1,…,Tn)）（1）若n=0则为空二叉树。（2）具有与root(T1)等同的根，其左子树为B(T11,T12,…,T1m)，其中T11,T12,…,T1m是root(T1)的子树；其右子树为B(T2,…,Tn)。

104JYP设T是与森林F对应的二叉树。前序遍历二叉树T与前序遍历森林F存在自然对应，森林F的前序遍历定义为：（1）若F为空则返回；（2）访问F的第一棵树的根；（3）前序遍历由第一棵树的子树构成的森林；（4）前序遍历由其余树构成的森林。105JYP中序遍历二叉树T与中序遍历森林F存在自然对应，森林F的中序遍历定义为：（1）若F为空则返回；（2）中序遍历由F的第一棵树的子树构成的森林；（3）访问第一棵树的根；（4）中序遍历由其余树构成的森林。106JYP后序遍历二叉树T与后序遍历森林F不存在自然对应，但我们可人为地将森林F的后序遍历定义为：（1）若F为空则返回；（2）后序遍历由F的第一棵树的子树构成的森林；（3）后序遍历由其余树构成的森林；（4）访问第一棵树的根。107JYP

森林的按层次遍历从森林的所有树的根所在层开始，逐层访问，在每一层内按照从左到右的顺序访问。这里森林作为一个整体看待，而不是遍历完一棵树再遍历另一棵。显然，按层次遍历二叉树T与按层次遍历森林F一般不存在对应关系。108JYP4.8集合表示

4.8.1并查集假设集合元素为0,1,2,3,…,n–1。还假设所表示的集合之间互不相交，即，若Si和Sj（ij）是集合，则Si

Sj=。例如，当n=10，元素可划分为三个不相交的集合：S1={0,6,7,8}，S2={1,4,9}和S3={2,3,5}。需要在这些集合上进行的操作是：（1）union(Si,Sj)：求Si和Sj的并（）。Si和Sj不再独立存在，将被SiSj所取代。（2）find(i)：查找含元素i的集合。109JYP为了高效率实现以上操作，用树表示集合。S1，S2和S3的表示如下：其中，每个集合用一棵树表示，且分枝由子女指向双亲。110JYP实现并操作可直接使两棵树之一成为另一棵树的子树，这样S1

S2可表示为下列两种形式之一：111JYP如果每个集合名对应一个指针，使之指向表示该集合的树的根，则上述操作很容易完成。此外，每个根也存放一个指向集合名的指针，这样，当需要判断一个元素属于哪个集合时，可沿着子女到双亲的链接，定位于根，并确定集合名。112JYP集合S1，S2和S3的数据表示如下：以后将直接用树根表示集合。于是，操作find(i)变为：确定含元素i的树的根；操作union(i,j)需要连接以i为根和以j为根的两棵树。113JYP由于集合元素为0,1,2,3,…,n–1，可以用数组parent[MaxElements]表示树结点。数组的第i个位置表示元素i对应的树结点。数组元素存放相应树结点的双亲指针。下面是S1，S2和S3的数组表示，注意根结点的parent为–1。114JYP基于上述表示的集合的类定义和构造函数：classSets{public:

//集合操作…private:int*parent;intn; //集合元素个数};Sets::Sets(intsz=DefaultSize){

n=sz;

parent=newint[sz];for(inti=0;i<n;i++)parent[i]=-1;}115JYP实现find(i)只需简单地沿着结点i的parent向上移动，直至到达parent值为–1的结点：intSets::SimpleFind(inti){ //找到含元素i的树的根while(parent[i]>=0)i=parent[i];returni;}union(i,j)也很简单，这里假设采用令第一棵树为第二棵的子树的策略：voidSets::SimpleUnion(inti,intj){//用以i为根和以j //（i!=j）为根的两个不相交集合的并取代它们

parent[i]=j;}

116JYP对SimpleUnion和SimpleFind的分析：

这两个算法虽然简单，但性能却不够好。例如，假设一开始各集合只含一个元素，即Si={i}，0≤i<n。执行以下操作序列：union(0,1),union(1,2),union(2,3),…,union(n–2,n–1),find(0),find(1),…,find(n–1)将生成下一页所示的退化树。117JYP该序列中的n–1个union共需O(n)时间。然而，每个find都需要从相应元素所在结点出发，沿parent指针找到根。从位于第i层的结点找到根结点需要O(i)时间，完成n个find共需O()O(n2)时间。118JYP可以通过避免生成退化树来改善union和find操作的性能。为此，可以对union(i,j)操作应用以下权重规则：若以i为根的树中结点数小于以j为根的树中结点数，则令j成为i的双亲，否则令i成为j的双亲。当应用权重规则时，执行前述union操作序列生成的树如下一页所示。其中，对union操作的参数作了适当修改，使其与树根对应。119JYP120JYP为了实现权重规则，可利用根结点的parent字段以负数的形式存储计数数据。由此可得基于权重规则的union算法：voidSets::WeightedUnion(inti,intj){//基于权重规则构造以i //和j为根的集合的并inttemp=parent[i]+parent[j];if(parent[j]<parent[i]){ //树i的结点少

parent[i]=j;parent[j]=temp;}else{ //树j的结点少或与树i的同样多

parent[j]=i;parent[i]=temp;}}121JYP对WeightedUnion和SimpleFind的分析：一次union操作的时间仍然是O(1)。find操作未变，其一次执行所需要的最长时间可由以下引理4.5确定。引理4.5：假设开始时森林是由一组只含单个结点的树构成的，并令T为一棵具有m个结点，且通过执行一系列WeightedUnion函数构成的树，则T的高度不高于log2m+1。证明：当m=1，引理显然正确。假设对于所有具有i（i≤m–1）个结点的树引理正确。下面需要证明对于i=m引理也正确。122JYP设T是由函数WeightedUnion构建的，有m个结点的树。考虑最后一次并操作union(k,j)。设a为树j的结点数，那么树k的结点数为m–a。不失一般性，设1≤a≤m/2，则T的根为k。因此，T的高度或者与原树kkjam-a的相同或者比原树j的多一级。若是前一种情况，T的高度≤log2(m–a)+1≤log2m+1；若是后一种情况，T的高度≤log2a+2≤log2m+1。

123JYP由引理4.5可知，如果一棵树有m个结点，则一次find操作的时间最多为O(logm)。执行u–1次union操作和f次find操作组成的混合序列的时间是O(u+flogu)，因为每棵树的结点数不超过u。当然，初始化n棵树的森林需要O(n)时间。问题的解决方法还可以作进一