Question

二叉树的问题

(2) 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是
A) acbed
B) decab
C) deabc
D) cedba

求详细解析，一定要详细

Answer 1

后序遍历最后一个结点肯定是根结点，于是数根为c；据此由中序遍历知左子树含deba结点，右子树为空；然后同理分析左子树：根为e，它的左子树含d，右子树含ba；继续分析其右子树：根据后序知根为b，由中序知其右子树为a。分析完毕，得到原树为：
c
/
e
/ \
d b
\
a
前序遍历得：cedba
选D。

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct tree
{
char info;
struct tree *left;
struct tree *right;
};
struct tree *root; /*树的第一个结点*/
struct tree *construct(struct tree *root, struct tree *r, char info);
void print(struct tree *r, int l);

int main(void)
{
char s[80];
root = NULL;
do
{
printf("Please input a character:");
gets(s);
root = construct(root,root,*s);
}while(*s);
print(root,0);
getch();
return 0;
}

struct tree *construct(
struct tree *root,
struct tree *r,
char info)
{
if(!r)
{
r = (struct tree *)malloc(sizeof(struct tree));
if(!r)
{
printf("内存分配失败！");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root)
return r;
if(info < root->info)
root->left = r;
else
root->right = r;
return r; /*是return r;还是return root;*/
}
if(info < r->info)
construct(r,r->left,info);
else
construct(r,r->right,info);
return root;
}

void print(struct tree *r, int l)
{
int i;
if(!r)
return;
print(r->left,l+1);
for(i = 0;i < l;++i)
printf(" ");
printf("%c\n",r->info);
print(r->right,l+1);
}

上面的是采用中序遍历，采用前序遍历和后序遍历的函数如下：
void scan(struct tree root)(前序遍历)
{
if(!root)return;
if(root->info);
执行相应操作;
scan(root->left);
scan(root->right);
}

void scan(struct tree root)(后序遍历)
{
if(!root)return;
scan(root->left);
scan(root->right);
if(root->info);
执行相应操作;
}