回 帖 发 新 帖 刷新版面

主题:请教一个建立二叉树的问题

给定了 前序遍历序列 和 中序遍历序列,然后这就确定了一个唯一的二叉树型,然后想建立一个树.代码我不会些,.希望大家帮我写一下,谢谢.
   有两个类,一个是class BinaryTreeNode  和  class BinaryTree
   例如 前序:ABCDEF
        中序:BCAEDF
[em18]

回复列表 (共1个回复)

沙发

你的例子中的二叉树为:(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);
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册