树图及其应_r_n 用（唯一地确定一棵二叉树）.c.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > algorithm > 数据结构上机实习-树图及其应_r_n 用（唯一地确定一棵二叉树）.c


/************************************************************************* 
-------问题描述-------- 
唯一地确定一棵二叉树 
　　如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵 
二叉树。试编写实现上述功能的程序。 

-------基本要求-------- 
已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法： 
1.构造一棵二叉树。 
2.证明构造正确。(即分别以前序和中序遍历该树，将得到的结果与给出的序列 
进行进行比较) 

-------测试数据-------- 
前序序列为ABDEGCFHIJ 
中序序列为DBGEAHFIJC 

-------实现提示------- 
1.用两个一维数组A和B分别存放前序和中序序列。 
2.根据定义，前序序列中第一个元素一定是树根，在中序序列中该元素之前的 
所有元素一定在左子树中，其余元素一定则在右子树中。所以，首先从数组A 
中取出第一个元素A[0]作为根结点，然后在数组B中找到A[0]，以它为界，在 
其前面的是左子树中序序列，在它后面的是右子树中序序列。 
3.若左子树不为空，沿前序序列向后移动，找到左子树根结点，转2。 
4.左子树构造完毕后，若右子树不为空，沿前序序列向后移到，找到右子树根结点， 
　转2 
5.前序序列中各元素取完则二叉树构造完毕。 
6.对二叉树进行前序和中序遍历，并将结果分别与数组A和B进行比较。若相同，则 
　证明二叉树构造正确。 

**************************************************************************/ 
#include <stdio.h> 
#define MAXLONG 20 
#define NULL 0 

typedef char elemtype; 

char A[MAXLONG], B[MAXLONG]; 

typedef struct node { 
elemtype Data; 
struct node * LChild; 
struct node * RChild; 
} treenode; 

/* 初始化某结点 */ 
void Initiate(treenode * t) { 
t->Data=0; 
t->LChild = NULL; 
t->RChild = NULL; 
} 

void pre(treenode * head) { 
if(head==NULL) 
return; 

printf(">c",head->Data); 
pre(head->LChild); 
pre(head->RChild); 
} 

void zhong(treenode * head) { 
if(head==NULL) 
return; 

zhong(head->LChild); 
printf(">c",head->Data); 
zhong(head->RChild); 
} 

treenode * bintree(int i, int j, int u, int v){ 
int k; 
treenode * head, * s; 

printf(" >d, >d, >d, >d\n",i,j,u,v); 
head= NULL; 
if(i<=j) { 
head=(treenode * )malloc(sizeof(treenode)); 
head->Data = A[i]; 
k = u; 
while(B[k]!=A[i]) k++; 
if(k==u) head->LChild = NULL; 
else { 
printf("left "); 
s=bintree(i+1, i+k-u, u, k-1); 
head->LChild = s; 
} 

if(k==v) head->RChild = NULL; 
else { 
printf("right "); 
s = bintree(i+k+1-u, j, k+1, v); 
head->RChild = s; 
} 
} 
return head; 
} 

main() { 
int i, j; 
int strlength=0; 
treenode * head; 

clrscr(); 
printf("Input Qianxu (less than 20) :"); 
scanf(">s",A); 
printf("Input Zhongxu(less than 20) :"); 
scanf(">s",B); 
printf("\nQianxu is : >s\nZhongxu is : >s\n",A, B); 

while(A[strlength]!='\0') { 
strlength++; 
printf(">d ",strlength); 
} 
strlength--; 

printf("\n\nhead "); 
head=bintree(0, strlength, 0, strlength); 

printf("\n"); 
pre(head); 
printf("\n"); 
zhong(head); 
}