实现提示

定义树的孩子兄弟表示法的结点结构以及树类Tree，包括题目要求建立树（即构造函数）、前序遍历和后序遍历二叉树等基本操作。简单起见,本实验假定树的数据元素为char型,树的孩子兄弟表示法的结点结构请参见主教材5.2.4节，树的遍历操作的定义请参见主教材5.1.3节。

首先需建立一棵树，这里采用按层次序来建立树的孩子兄弟表示法存储结构。先建立树的根节点，然后建立第一层的结点，同时建立根和其孩子结点之间的链接关系。为此需要队列作为辅助数据结构。其基本思想为：输入有序对(F C)，生成一个新结点p，其数据域为C，并将指针p入队。然后查询队头元素是否等于F，若不等，则说明该元素不会再有孩子输入，将它从队列中删去。当找到C的双亲结点q之后，首先检查结点q的firstchild域是否为空，若为空，则说明当前输入的C是结点q的第一个孩子，链入q的firstchild域，否则找到结点q的最后一个孩子结点，将C链入它的firstchild域。算法的伪代码描述如下：

1.队列Q初始化；

2.输入根结点，并将根结点入队列Q；

3.依次输入有序对(F C)，执行下述操作：

3.1P=申请一个新结点; p->data=C; p->firstchild=p->rightsib=NULL;

3.2当队列Q非空，执行下述操作：

3.2.1q=队列Q的队头元素；

3.2.2若q->data不等于F，则将队列Q的队头元素删除；

3.2.3否则，若F->firstchild为NULL，则令F->firstchild=p；否则，查找结点F的最后一个孩子q，令q->rightsib=p；

四、实验程序

在VC++编程环境下新建一个工程“树的实现验证”，在该工程中新建一个头文件Tree.h，该头文件包括树的孩子兄弟表示法的结点结构和树类Tree的定义，范例程序如下：

#ifndef Tree_H

#define Tree_H

const int Max = 20;

struct TNode

{

char data;

TNode *firstchild, *rightsib;

};

class Tree

{

public:

Tree( );

~Tree( ){Release(root);} //析构函数，释放各结点的存储空间

void PreOrder( ){PreOrder(root);}

void PostOrder( ){PostOrder(root);}

private:

TNode *root;

void PreOrder(TNode *bt);

void PostOrder(TNode *bt);

void Release(TNode *bt);

};

#endif

在工程“树的实现验证”中新建一个源程序文件Tree.cpp，该文件包括类Tree的成员函数的定义，范例程序如下：

#include <iostream>

using namespace std;

#include "Tree.h"

Tree::Tree( )

{

TNode *Q[Max] = {NULL};

char ch1 = '#', ch2 = '#';

int front = -1, rear = -1;

TNode *p = NULL, *q = NULL;

cout<<"请输入根结点：";

cin>>ch1;

p = new TNode; p->data = ch1;

p->firstchild = p->rightsib = NULL;

root = p;

Q[++rear] = p;

cout<<"请输入结点对，以空格分隔：";

fflush(stdin);

ch1 = getchar(); getchar(); ch2 = getchar();

while (ch1 != '#' || ch2 != '#')

{

p = new TNode; p->data = ch2;

p->firstchild = p->rightsib = NULL;

Q[++rear] = p;

while (front < rear)

{

q = Q[front + 1];

if (q->data != ch1)

front++;

else

{

if (q->firstchild == NULL)

q->firstchild = p;

else

{

while (q->rightsib != NULL)

q = q->rightsib;

q->rightsib = p;

}

break;

}

}

cout<<"请输入结点对，以空格分隔：";

fflush(stdin);

ch1 = getchar(); getchar(); ch2 = getchar();

}

}

void Tree::Release(TNode *bt)

{

if (bt == NULL) return; //递归调用的结束条件

else

{

Release(bt->firstchild); //后序递归释放bt的第一棵子树

Release(bt->rightsib); //后序递归释放bt的右兄弟子树

delete bt; //释放根结点

}

}

void Tree::PreOrder(TNode *bt)

{

if (bt == NULL) return; //递归调用的结束条件

else

{

cout<<bt->data; //访问根结点的数据域

PreOrder(bt->firstchild); //前序递归遍历root的第一棵子树

PreOrder(bt->rightsib); //前序递归遍历root的右兄弟子树

}

}

void Tree::PostOrder(TNode *bt)

{

if (bt == NULL) return; //递归调用的结束条件

else

{

PostOrder(bt->firstchild); //后序递归遍历root的第一棵子树

PostOrder(bt->rightsib); //后序递归遍历root的右兄弟子树

cout<<bt->data; //访问根结点的数据域

}

}

在工程“树的实现验证”中新建一个源程序文件Tree_main.cpp，该文件包括主函数，范例程序如下：

#include <iostream>

using namespace std;

#include "Tree.h"

int main( )

{

Tree t1;

t1.PreOrder();

cout<<endl;

t1.PostOrder();

cout<<endl;

return 0;

}