岁堤春晓

这次的作业是输入二叉树的前序和中序然后构建出该二叉树并输出其后序。在做作业的时候首先自己得搞清楚二叉树的一些概念

二叉树基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？到了后面才明白，这是不同的应用需要的。例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性，这些遍历方法能很清晰的表达。

下面提供主要的代码（老师给的哈！语言为C）

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 27

struct tree

{

char data;

struct tree *left;

struct tree *right;

};

typedef struct tree treenode;

typedef treenode *btree;

btree creat(char a)

{

btree p;

p=(btree)malloc(sizeof(treenode));

p->data=a;

p->left=NULL;

p->right=NULL;

return p;

}

void LRNandFREE(btree p)

{

if ( p != NULL )

{

LRNandFREE(p->left);

LRNandFREE(p->right);

printf(“%c”,p->data);

free(p);

}

}

int onleft(char a, char b, char *p)

{

while(*p)

{

if(*p==a)

return 1;

if(*p==b)

return 0;

p++;

}

printf(“Cannot found %c and %c in InorderTraversal!\n”,a,b);

system(“pause”);

exit(0);

}

btree search(char a, btree root)

{

btree p;

if(root==NULL)

return NULL;

if(root->data==a)

return root;

else

{

p=search(a,root->left);

if(p==NULL)

p=search(a,root->right);

return p;

}

}

btree prev(char a, char b, char *s, btree root)

{

btree p;

int i, j;

for(i=0;;i++)

if(a==s[i]) break;

for(j=i+1;;j++)

if(b==s[j]) break;

for(j–;j>i;j–)

if((p=search(s[j],root))!=NULL)

return p;

return NULL;

}

void main()

{

char a[N],b[N];

int i,j;

btree root=NULL, p, q, t;

printf(“Input PreorderTraversal:\n”); /*输入前序遍历*/

scanf(“%s”,a);

printf(“Input InorderTraversal:\n”); /*输入中序遍历*/

scanf(“%s”,b);

if(strlen(a)>=N || strlen(a)!=strlen(b))

{

printf(“Input ERROR!\n”);

system(“pause”);

exit(0);

}

if(a[0]!=’\0′)

{

root=creat(a[0]);

p=root;

for(i=1;a[i]!=’\0′;i++)

{

q=creat(a[i]);

if(onleft(a[i],a[i-1],b))

{p->left=q; p=q;}

else

if(onleft(a[i-1],a[i],b))

{

t=prev(a[i-1],a[i],b,root);

if(t==NULL)

{p->right=q; p=q;}

else

{t->right=q; p=q;}

}

else

{

printf(“The two travelsal you have entered is not legal!\n”);

system(“pause”);

exit(0);

}

}

}

printf(“PostorderTraversal:\n”);

LRNandFREE(root);

printf(“\n”);

system(“pause”);

}

我是经过测试后分享上来的 如果有问题请大家多多交流  祝大家好运！O(∩_∩)O~