主题:请教一个建立二叉树的问题
要干仗啊
[专家分:10] 发布于 2007-05-05 22:23:00
给定了 前序遍历序列 和 中序遍历序列,然后这就确定了一个唯一的二叉树型,然后想建立一个树.代码我不会些,.希望大家帮我写一下,谢谢.
有两个类,一个是class BinaryTreeNode 和 class BinaryTree
例如 前序:ABCDEF
中序:BCAEDF
[em18]
回复列表 (共1个回复)
沙发
oney139 [专家分:0] 发布于 2007-05-07 23:10:00
你的例子中的二叉树为:(A(B(,C),D(E,F)))建立过程如下:
//包括了建立和输出过程和测试,自已看吧,再找找其它课本.
#include<iostream.h>
#include<malloc.h>
#define MaxSize 40
typedef char Elemtype;
typedef struct node
{
Elemtype data;//数据
struct node *left,*right;//左右指针
} BTree;
void creatree(BTree *&b,char *str)//由广义表样式创建二叉树
{
BTree *stack[MaxSize],*p;
int top=-1,j=0;//栈空
int k;//左右指标志
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(': top++;stack[top]=p;k=1;break;
case ')': top--;break;
case ',': k=2;break;
default: p=(BTree*)malloc(sizeof(BTree));
p->data=ch;p->left=p->right=NULL;
if(b==NULL)
b=p;//根结点
else
{
if(k==1) stack[top]->left=p;
if(k==2) stack[top]->right=p;
}
}
j++;ch=str[j];
}
}
void printree(BTree *b)//由广义表形式输出二叉树
{
if(b!=NULL)
{
cout<<b->data;
if(b->left!=NULL||b->right!=NULL)
{
cout<<"(";
printree(b->left);
if(b->right!=NULL)
cout<<",";
printree(b->right);
cout<<")";
}
}
}
void main()
{
BTree *b;
creatree(b,"(A(B(,C),D(E,F)))");
cout<<"广义表表示法为:"<<endl;
printree(b);
}
我来回复