作业帮 > 综合 > 作业

二叉树的后续序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,试建立这颗二叉树,画出该二叉树的先序线索二叉

来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/03/29 09:11:10
二叉树的后续序列为DCEGBFHKJIA,中序序列为DCBGEAHFIJK,试建立这颗二叉树,画出该二叉树的先序线索二叉数
//第二个多了个I,我写了个程序,并假设第二个序列没有I
#include <windows.h>
#include <iostream.h>
struct node{
char c;
node *left;
node *right;
};
int depth=0;
int lengthFunc(char *string);
int lengthLeftFunc(char *string,char ref);
node *makeTree(char *string1,char *string2);
void printTree(node *newNode);
void destroyTree(node* newNode);
void main()
{
node *top=0;
char string1[]="DCBGEAHFJK";
char string2[]="DCEGBFHKJA";
top=makeTree(string1,string2);
printTree(top);
destroyTree(top);
}
int lengthFunc(char *string)
{
for(int i=0;string[i]!='\0';i++);
return i;
}
int lengthLeftFunc(char *string,char ref)
{
for(int i=0;string[i]!=ref;i++);
return i;
}
node *makeTree(char *string1,char *string2)
{
int length=lengthFunc(string1);
if(length==0)
return (node*)0;
node *newNode=(node*)malloc(sizeof(node));
newNode->c=string2[length-1];
int lengthLeft=lengthLeftFunc(string1,newNode->c);
int lengthRight=length-lengthLeft-1;
char *stringLeft1=(char*)malloc(sizeof(char)*(lengthLeft+1));
char *stringLeft2=(char*)malloc(sizeof(char)*(lengthLeft+1));
char *stringRight1=(char*)malloc(sizeof(char)*(lengthRight+1));
char *stringRight2=(char*)malloc(sizeof(char)*(lengthRight+1));
if(lengthLeft!=0){
for(int i=0;i<lengthLeft;i++){
stringLeft1[i]=string1[i];
stringLeft2[i]=string2[i];
}
stringLeft1[i]=stringLeft2[i]=(char)0;
newNode->left=makeTree(stringLeft1,stringLeft2);
}
else
newNode->left=0;
if(lengthRight!=0){
for(int i=0;i<lengthRight;i++){
stringRight1[i]=string1[lengthLeft+1+i];
stringRight2[i]=string2[lengthLeft+i];
}
stringRight1[i]=stringRight2[i]=(char)0;
newNode->right=makeTree(stringRight1,stringRight2);
}
else
newNode->right=0;
free(stringLeft1);free(stringLeft2);free(stringRight1);free(stringRight2);
return newNode;
}
void printTree(node *newNode)
{
if(newNode==0)
return;
depth++;
printTree(newNode->left);
depth--;
for(int i=0;i<depth;i++)
cout<<'\t';
cout<<newNode->c<<endl;
depth++;
printTree(newNode->right);
depth--;
}
void destroyTree(node* newNode)
{
if(newNode==0)
return;
if(newNode->left!=0)
destroyTree(newNode->left);
if(newNode->right!=0)
destroyTree(newNode->right);
free(newNode);
newNode=0;
}
//按照假设,如果输入序列无I,则输出结果如图.
如果还没解决你的问题,可以加我百度HI账号.