实验6 树

1、编写算法函数void levelorder(tree t)实现树的层次遍历。

#include "tree.h"void levelorder(tree t) /* t为指向树根结点的指针*/{tree queue[MAXLEN];/*用队列存放待处理的结点*/int head=0,end=1;int i;queue[head] = t;/*先将根节点入队*/while( head < end ){for(i=0;i<m;i++)/*将队列中结点的下一层结点入队，逐层入队*/{if( queue[head]->child[i] ){queue[end++] = queue[head]->child[i];}}printf("%c",queue[head++]->data);/*逐层出队*/}}int main(){tree t;printf("please input the preorder sequence of the tree:\n");t=createtree();printf("\nthe levelorder is:");levelorder(t);return 0;}

2、假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PreOrder1(tree root)，实现树的前序遍历算法。

#include "tree.h"void PreOrder1(tree root){tree stack[100];int i;int top=-1;while (root || top!=-1){if (root){printf("%c",root->data); //输出根结点for (i=m-1;i>0;i--) //所有非空孩子结点进栈if (root->child[i]!=NULL){top++;stack[top]=root->child[i];}root=root->child[0]; //转第1棵子树}else{root=stack[top--]; //栈顶树出栈}}}int main (){tree root;printf("please input the preorder sequence of the tree:\n");root =createtree();printf("前序序列是：\n");PreOrder1(root);return 0;}

3、 假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PostOrder1(tree t)，实现树的后序遍历算法。

#include "tree.h"int PostOrder1(tree root){tree treeStack[MAXLEN];/*储存待处理的结点*/int top = -1;tree printStack[MAXLEN];/*储存已经处理完子树的、待输出的结点*/int topp = -1;int i;if( root ) treeStack[++top] = root;/*根结点进栈*/while( top != -1 ){root = treeStack[top--];/*取一个待处理结点root*/for(i=0;i<m;i++)/*将root的所有子结点进栈*/{if( root->child[i] ) treeStack[++top] = root->child[i];}printStack[++topp] = root;/*处理完root、将root进printStack*/}while( topp != -1 ) printf("%c",printStack[topp--]->data);/*输出后序序列*/}int PostOrder2(tree root){tree treeStack[MAXLEN];/*未处理完的结点*/int subStack[MAXLEN];/*正在处理的孩子的下标*/int top = -1;tree p;int i;treeStack[++top] = root;subStack[top] = 0;/*首先处理child[0]这个分支*/while( top != -1 ){p = treeStack[top];while( subStack[top] < m )/*处理所有分支*/{i = subStack[top];if( p->child[i] ){p = p->child[i];treeStack[++top] = p;/*有孩子则入栈*/subStack[top] = 0;/*并处理刚入栈结点的child[0]*/}else {subStack[top]++;/*该分支没有孩子，处理下一分支*/}}printf("%c",p->data);/*出栈前再输出*/top--;/*该结点处理完毕，返回处理父结点的child[i+1]*/subStack[top]++;}}int main (){//AB###CE###FH###I####G###D### ,测试三度树tree root;printf("please input the preorder sequence of the tree:\n");root =createtree();printf("后序序列是：\n");PostOrder1(root);putchar('\n');PostOrder2(root);return 0;}

4、假设树采用指针方式的孩子表示法表示，试编写一个函数int equal(tree t1, tree t2)，判断两棵给定的树是否等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。

#include "tree.h"#define TRUE 1#define FALSE 0int equal(tree t1,tree t2){int flag=TRUE,i;if (t1==NULL && t2==NULL)return TRUE;elseif (t1==NULL && t2!=NULL || t2==NULL && t1!=NULL)return FALSE;elseif (t1->data!=t2->data) return FALSE;else{for (i=0;i<m;i++)flag=flag&&equal(t1->child[i],t2->child[i]);return flag;}}int main (){tree t1,t2;printf("please input the preorder sequence of the tree:\n");t1=createtree();getchar();printf("please input the preorder sequence of the tree:\n");t2=createtree();if ( equal(t1,t2) == TRUE){printf ("两树相等\n");}else{printf ("两树不相等\n");}return 0;}

5、假设树采用指针方式的孩子表示法存储结构，试编写一个函数tree Ct(char s[])，根据输入的树的括号表示字符串s，生成树的存储结构。例如，若要建立教材图6.4所示的树，应输入A（B（E，F）,C,D（G（I，J，K）,H））。（说明，tree.h中定义的常量m表示树的最大度，请根据建树的需要自行修改m的值）

#include "tree.h"/*请将本函数补充完整，并进行测试*/tree Ct(char s[MAXLEN]){int length;int i,j,top;tree stack[100],root=NULL,temp = NULL,n;int childSeq[m];// 其第几个孩子top = -1;length = strlen (s);for (i = 0;i < length;i++){if (s[i] == ','){continue;}else if (s[i] == '('){stack[++top] = temp;childSeq[top] = 0;}else if (s[i] == ')'){top--;}else if (top != -1){n = (tree)malloc (sizeof (node));n->data= s[i];for (j = 0;j < m;j++){n->child[j] = NULL;}temp = n;stack[top]->child[childSeq[top]++] = temp;}else{root = (tree)malloc (sizeof (node));root->data = s[i];for (j = 0;j < m;j++){root->child[j] = NULL;}temp = root;}}return root;}int main (){char s[MAXLEN];tree root = NULL;printf ("请用树的括号表示法输入一棵树:\n");scanf ("%s",s);root = Ct(s);preorder(root); /*前序遍历树*/return 0;}