tree1_list.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include "Tree1.h"                     //二叉树类

TreeNode1* listCreate(char *str)       //str为二叉树的广义表表示
{                                      //返回指向所建立二叉树根结点的指针
    TreeNode1 *p=NULL;
    static int i=0;
    if(str[i]>='A' && str[i]<='Z')     //大写字母
    {
        p=new TreeNode1(str[i]);       //建立结点，数据元素为当前的大写字母
        i++;                           //跳过大写字母
        if(str[i]=='(')
        {
            i++;                       //跳过(
            p->left=listCreate(str);   //建立左子树
            i++;                       //跳过,
            p->right=listCreate(str);  //建立右子树
            i++;                       //跳过)
        }
    }
    if(str[i]=='#')
        i++;                           //跳过#
    return p;                          //str[i]非大写字母时，返回NULL
}

void main()
{
    char *str="A(B(D(#,G),#),C(E,F(H,#)))";  //二叉树的广义表表示
    cout<<"The Tree: "<<str<<endl;
    Tree1 t1;                          //构造空树
    t1.root=listCreate(str);           //创建二叉树
    t1.preorder();
    t1.inorder();
    t1.postorder();
}
/*
程序运行结果如下：
The Tree: A(B(D(#,G),#),C(E,F(H,#)))
先序遍历二叉树:  A B D G C E F H 
中序遍历二叉树:  D G B A E C H F 
后序遍历二叉树:  G D B E H F C A 
撤销二叉树: G D B E H F C A 
*/