/*
编写算法函数void levelorder(tree t)实现树的层次遍历。
*/
#include "tree.h"
void levelorder(tree t) /* t为指向树根结点的指针*/
{
tree queue[100];
int f,r,i; //f,r分别为队头和队尾指针
tree p;
f=0; r=1; queue[0]=t;
while(f<r)
{
p=queue[f] ;f++;printf("%c",p->data); //访问队头元素
for(i=0;i<m;i++) //将刚被访问的元素的所有子女结点依次进队
{
if(p->child[i])
{
queue[r]=p->child[i];
r++;
}
}
}
}
int main()
{
tree t;
printf("please input the preorder sequence of the tree:
");
t=createtree();
printf("
the levelorder is:");
levelorder(t);
return 0;
}
/*
假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PreOrder1(tree root)，实现树的前序遍历算法。
*/
#include "tree.h"
void PreOrder1(tree root)
{
tree stack[MAXLEN];
int top=-1,i;
while(top!=-1||root)
{
if(root) //子树不为空
{
printf("%c",root->data);
for(i=m-1;i>0;i--)
{
if(root->child[i]!=NULL) //将不为空的子结点进栈
stack[++top]=root->child[i];
}
root=root->child[0]; //从第一个子结点开始遍历
}
else //子树为空，出栈
{
root=stack[top--];
}
}
}
int main ()
{
tree root;
printf("please input the preorder sequence of the tree:
");
root =createtree();
printf("前序序列是：
");
PreOrder1(root);
return 0;
}
/*
假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void PostOrder1(tree t)，实现树的后序遍历算法。
*/
#include "tree.h"
int PostOrder1(tree root)
{
tree treeStack[MAXLEN]; //待处理结点
tree overStack[MAXLEN]; //已处理完的结点
int top=-1,top1=-1,i;
if(root)
treeStack[++top]=root; //根结点进栈
while(top!=-1)
{
root=treeStack[top--]; //取一个待处理结点
for(i=0;i<m;i++) //将root的所有子结点进栈
{
if(root->child[i])
treeStack[++top]=root->child[i];
}
overStack[++top1]=root; //处理完root，将root入overStack
}
while(top1!=-1) //输出
printf("%c",overStack[top1--]->data);
}
int main ()
{
tree root;
printf("please input the preorder sequence of the tree:
");
root =createtree();
printf("后序序列是：
");
PostOrder1(root);
return 0;
}
/*
假设树采用指针方式的孩子表示法表示，试编写一个函数int equal(tree t1, tree t2)，
判断两棵给定的树是否等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。
*/
#include "tree.h"
#define TRUE 1
#define FALSE 0
int equal(tree t1,tree t2)
{
int flag=TRUE,i;
if(!t1&&!t2) //若两树为空，则相等
return TRUE;
else if(!t1&&t2||t1&&!t2) //若有一树为空，则不相等
return FALSE;
else if(t1->data!=t2->data)
return FALSE;
else
{
for(i=0;i<m;i++)
{
if(t1->child[i]==t2->child[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:
");
t1=createtree();
getchar();
printf("please input the preorder sequence of the tree:
");
t2=createtree();
if ( equal(t1,t2) == TRUE)
{
printf ("两树相等
");
}
else
{
printf ("两树不相等
");
}
return 0;
}
/*
假设树采用指针方式的孩子表示法存储结构，试编写一个函数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])
{
tree stack[MAXLEN],parent=NULL,child=NULL;
int n=0,top=0,done=0,i;
while(done==0&&s[n]!='
