【实验目的】

1. 掌握树的孩子兄弟链存储表示。

2. 掌握树的创建、遍历等算法。

【问题描述】

树的创建及其操作。

【基本要求】

1. 创建树的孩子兄弟链式存储表示。假设以二元组(F,C)的形式输入一颗树的诸边，其中F表示双亲结点标识，C表示孩子结点标识，且在输入的二元组序列中，C是按层次序列顺序出现的。F=’^’时C为根结点标识，若C也为’^’，则表示输入结束。例如，如下所示树的输入序列为；

2. 按树状打印树。例如：假设树上每个结点所含数据元素为单个字母，左下图树印为右下形状。

3. 统计树的叶子结点个数；

4. 计算树的高度；

5. 给出树的先根遍历序列、后根遍历序列和层次遍历序列；

6. 输出树中从根结点到所有叶子结点的路径。

【测试数据】

       自行设定

• 需求分析：包含题目要求，程序功能，运行方式，测试数据等

题目要求用孩子兄弟链表结构表示树，并按照特定的输入方法去创建树，并将树打印。需要创建结构体CSNode，将数据类型定义为char，在主函数中设置输入，在运行时输入相应的字符，创建孩子兄弟树。

typedef struct CSNode{char data;struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

 同时先预设队列和相关实现队列操作的函数与结构体，用于实现统计树的叶子结点个数和输出树中从根结点到所有叶子结点的路径。

typedef struct {CSTree  *base;  // 动态分配存储空间int  front;    // 头指针，若队列不空，指向队列头元素int  rear;     // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue; 

按特定形状打印树：即是按先根遍历去打印树，同时运用递归的方法来打印孩子兄弟，打印孩子时深度加一，打印兄弟时深度不变，所以用一个数字n表示深度，用for循环结合n打印制表符来表示树的深度。

if(T){for(int i = 0;idata;//打印数据cout<firstchild,n+1);//递归打印孩子，深度加1printTree(T->nextsibling,n);//递归打印兄弟}

二、概要设计：包含抽象数据类型定义，程序模块等

第一个模块定义CSNode结构体，创建孩子兄弟链表，相应的指针。

    char data;

通过struct CSNode *firstchild,*nextsibling;可知CSNode是一个递归的结构体。

定义创建孩子兄弟树，和孩子兄弟树结点的函数。

CSTree GetTreeNode(char ch){//创建结点CSTree CST = new CSNode;CST->data = ch;CST->firstchild = NULL;CST->nextsibling = NULL;return CST;
}

创建树，P = GetTreeNode(ch)创建结点，指针入队，fa == ^表示没有父结点，即创建结点为根结点，取队列头元素(指针值)，查询双亲结点，不存在孩子结点时链接第一个孩子结点，否则链接兄弟结点。

定义顺序队列SqQueue相应的内容，数据，左右孩子指针，头尾指针，创建需要用到的函数，InitQueue构造一个空队列Q；EmptyQueue判断队列是否空；GetHead返回队列Q的队头元素，不修改队头指针；EnQueue插入元素e为Q的新的队尾元素；DeQueue若队列不空，则删除Q的队头元素，否则退出程序报错。相应的需要用到的基本算法，再用这些算法去实现题目所要求的遍历算法和统计结点，路径。

bool EmptyQueue(SqQueue Q){//判断队列是否空return Q.front == Q.rear;
}int  QueueLength (SqQueue Q) {//返回Q的元素个数，即队列的长度return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}CSTree GetHead(SqQueue Q) {//返回队列Q的队头元素，不修改队头指针if ( Q.front != Q.rear )return Q.base[Q.front];elsereturn 0;
}void EnQueue(SqQueue&Q,CSTree e) {// 插入元素e为Q的新的队尾元素if((Q.rear+1) %MAXQSIZE ==Q.front){cout<<"队列满";exit(0); //队列满}Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MAXQSIZE;
}void DeQueue (SqQueue&Q) {//若队列不空，则删除Q的队头元素，//否则退出程序报错if (Q.front==Q.rear)  exit(0);Q.front = (Q.front+1) % MAXQSIZE;
}

第二个模块用来定义相应的算法, CountLeaf(CSTree T)用于统计树的叶子结点个数，TreeDepth(CSTree T)用于计算树的高度，PreOrderTraverse(CSTree T)先根遍历树，InOrderTraverse(CSTree T)后根遍历树，LevelOrderTraverse(CSTree T)层次遍历树，AllPath(CSTree T,SqQueue Q)用于输出根结点到叶子结点的路径。

       第三个模块是主函数模块，用来实现进入算法和输出函数返回值，输出正确的题目和所要求的结果。同时用于初始化孩子兄弟树与队列，按顺序调用的算法函数和endl，让最后运行程序时简洁美观。

int main()
{CSTree CST;SqQueue Q;CreatTree(CST);InitQueue(Q);printTree(CST,0);cout<<"树的叶子个数为:"<firstchild)//没有孩子即为叶子结点，计数+1num++;CountLeaf(T->firstchild);//遍历孩子CountLeaf(T->nextsibling);//遍历兄弟}return num;
}
计算树的高度：空树时返回0，树高度为0。定义h1，h2分别表示孩子、兄弟的高度，并递归计算，返回两者中较大值，即为树的高度。
int TreeDepth(CSTree T){//计算树的高度if(T == NULL) return 0;//空树时返回0else{int h1 = TreeDepth(T->firstchild);//孩子高度int h2 = TreeDepth(T->nextsibling);//兄弟高度return (h1+1>h2)?(h1+1):h2;//返回大的值}
}
给出树的先根遍历序列、后根遍历序列：先根遍历与后根遍历较为简单，只需要根据遍历的定义按顺序输出孩子兄弟，即输出了相应的序列。
void PreOrderTraverse(CSTree T) {//先根遍历if(T) {cout<data<<" ";PreOrderTraverse(T->firstchild);PreOrderTraverse(T->nextsibling);}
}void InOrderTraverse(CSTree T) {//后根遍历if(T) {InOrderTraverse(T->firstchild);cout<data<<" ";InOrderTraverse(T->nextsibling);}
}
输出树的层次序列：需要用到队列辅助输出层次序列，队列创建并初始化后，先让根结点入队，队列非空时，根据队列长度输出结点并出队，指向下一个孩子结点，在p非空时继续遍历入队，让p指向兄弟结点，循环上述方法直到树遍历完成。
void LevelOrderTraverse(CSTree T){//层次遍历SqQueue Q;InitQueue(Q);//队列初始化if(T==NULL) return;CSTree p = T;EnQueue(Q,p);//根结点入队while (!EmptyQueue(Q)) {int width = QueueLength(Q);//队列长度for(int i = 0;idata<<" ";//输出结点DeQueue(Q);//出队p = p->firstchild;//指向下一个孩子结点while (p) {//p非空时继续遍历EnQueue(Q,p);//入队p = p->nextsibling;//指向兄弟结点}}}
}

输出树中从根结点到所有叶子结点的路径：同样是要用队列辅助输出，但队列要定义在主函数中，因为要用到递归，队列定义在主函数中保证路径输出正确。根结点入队，当没有孩子时输出路径，否则指向孩子，递归孩子，循环入队直到该路径输出。一条路径输出之后指向根结点兄弟，重复上面的方法，直到所有路径输出完成。

void AllPath(CSTree T,SqQueue Q){//输出根结点到叶子结点的路径if(T){EnQueue(Q,T);//根结点入队if(!T->firstchild){//没有孩子时输出路径for(;QueueLength(Q)>1;DeQueue(Q)){cout<data<<" ";}cout<data<firstchild;//否则指向孩子while (T) {AllPath(T,Q);//递归孩子，即递归该路径T = T->nextsibling;//指向兄弟}}}
}

四、调试分析：包括算法的时间复杂度和空间复杂度分析等

       树的先根遍历序列、后根遍历用到了递归，时间复杂度均为O（n），辅助空间即树的深度，所以空间复杂度也为O（n）。

按树状打印孩子兄弟树同理，但因为需要按深度打印制表符，所以时间复杂度为O（n2），空间复杂度为O（n）。

       树的层次遍历，因为需要用到队列，出队和入队，同时需要递归遍历孩子兄弟，辅助空间较多，同时用到队列空间和树CSNode空间，空间复杂度为O（n2），时间复杂度为O（n）。

       统计叶子结点个数的算法较为简单，只使用了递归遍历，对含n个结点的二叉树，时间复杂度均为O（n），辅助空间即树的深度，所以空间复杂度也为O（n）。

输出根结点到所有叶子结点的路径中，要用到队列，输出队列中的内容，加上需要递归子树，所以时间复杂度为O（n2），空间复杂度也为空间复杂度为O（n2）。

在层次遍历孩子兄弟树时，没有正确的递归孩子兄弟，递归了传入算法的树，让其入队，相当于重复入队其首结点并输出，导致层次序列一直输出首结点直到队列满，后来发现是需要在递归函数的参数中传入队头的子树，才能正确递归孩子兄弟，这样才正确入队和出队，完成输出层次遍历树的目的。

统计叶子结点时定义n为全局变量，封装性不够好，在递归时最好定义静态static的数据，这样保证了数据的封装性也保证了输出能够正确，同时不破坏程序的模块化。

输出根结点到所有叶子结点的路径时，错误的对形参采用了取地址的符号&，导致递归的封装性被破坏，取到队列的未知地址，整个函数的输出完全错误，后来经过仔细检查后发现不能取地址，而是直接对队列进行调整入队，这样才能输出正确的路径。

五、测试结果：提供试验结果和数据，测试所有操作结果的正确性

测试数据1:

可见所有数据正确

测试数据2：

可见所有数据正确：

头文件及源程序

#include 
#include using namespace std;#define MAXQSIZE  100  //最大队列长度typedef struct CSNode{char data;struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;typedef struct {CSTree  *base;  // 动态分配存储空间int  front;    // 头指针，若队列不空，指向队列头元素int  rear;     // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;void InitQueue (SqQueue &Q) {// 构造一个空队列QQ.base = new CSTree[MAXQSIZE];if(!Q.base) exit(0);             // 存储分配失败Q.front = Q.rear = 0;
}bool EmptyQueue(SqQueue Q){//判断队列是否空return Q.front == Q.rear;
}int  QueueLength (SqQueue Q) {//返回Q的元素个数，即队列的长度return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}CSTree GetHead(SqQueue Q) {//返回队列Q的队头元素，不修改队头指针if ( Q.front != Q.rear )return Q.base[Q.front];elsereturn 0;
}void EnQueue(SqQueue&Q,CSTree e) {// 插入元素e为Q的新的队尾元素if((Q.rear+1) %MAXQSIZE ==Q.front){cout<<"队列满";exit(0); //队列满}Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MAXQSIZE;
}void DeQueue (SqQueue&Q) {//若队列不空，则删除Q的队头元素，//否则退出程序报错if (Q.front==Q.rear)  exit(0);Q.front = (Q.front+1) % MAXQSIZE;
}CSTree GetTreeNode(char ch){//创建结点CSTree CST = new CSNode;CST->data = ch;CST->firstchild = NULL;CST->nextsibling = NULL;return CST;
}void CreatTree(CSTree &T){//创建树CSTree P,s,r;T = NULL;SqQueue Q;InitQueue(Q);//队列创建及初始化char fa,ch;for(cin>>fa,cin>>ch;ch!='^';cin>>fa,cin>>ch){P = GetTreeNode(ch);//创建结点EnQueue(Q,P);//指针入队if(fa == '^') T=P;//fa == ^表示没有父结点，即创建结点为根结点else{//不为根结点时s = GetHead(Q);//取队列头元素(指针值)while (s->data != fa){//查询双亲结点DeQueue(Q);s = GetHead(Q);}if(!(s->firstchild)){s->firstchild = P;//链接第一个孩子结点r = P;//r指向尾端}else{r->nextsibling = P;//链接兄弟结点r = P;//r指向尾端}}}
}void printTree(CSTree T,int n){//打印树，n表示深度if(T){for(int i = 0;idata;//打印数据cout<firstchild,n+1);//递归打印孩子，深度加1printTree(T->nextsibling,n);//递归打印兄弟}
}int CountLeaf(CSTree T){//统计树的叶子结点个数int static num=0;if(T){if(!T->firstchild)//没有孩子即为叶子结点，计数+1num++;CountLeaf(T->firstchild);//遍历孩子CountLeaf(T->nextsibling);//遍历兄弟}return num;
}int TreeDepth(CSTree T){//计算树的高度if(T == NULL) return 0;//空树时返回0else{int h1 = TreeDepth(T->firstchild);//孩子高度int h2 = TreeDepth(T->nextsibling);//兄弟高度return (h1+1>h2)?(h1+1):h2;//返回大的值}
}void PreOrderTraverse(CSTree T) {//先根遍历if(T) {cout<data<<" ";PreOrderTraverse(T->firstchild);PreOrderTraverse(T->nextsibling);}
}void InOrderTraverse(CSTree T) {//后根遍历if(T) {InOrderTraverse(T->firstchild);cout<data<<" ";InOrderTraverse(T->nextsibling);}
}void LevelOrderTraverse(CSTree T){//层次遍历SqQueue Q;InitQueue(Q);//队列初始化if(T==NULL) return;CSTree p = T;EnQueue(Q,p);//根结点入队while (!EmptyQueue(Q)) {int width = QueueLength(Q);//队列长度for(int i = 0;idata<<" ";//输出结点DeQueue(Q);//出队p = p->firstchild;//指向下一个孩子结点while (p) {//p非空时继续遍历EnQueue(Q,p);//入队p = p->nextsibling;//指向兄弟结点}}}
}void AllPath(CSTree T,SqQueue Q){//输出根结点到叶子结点的路径if(T){EnQueue(Q,T);//根结点入队if(!T->firstchild){//没有孩子时输出路径for(;QueueLength(Q)>1;DeQueue(Q)){cout<data<<" ";}cout<data<firstchild;//否则指向孩子while (T) {AllPath(T,Q);//递归孩子，即递归该路径T = T->nextsibling;//指向兄弟}}}
}int main()
{CSTree CST;SqQueue Q;CreatTree(CST);InitQueue(Q);printTree(CST,0);cout<<"树的叶子个数为:"<