tree1.h

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

#include <iostream.h>
#include "TreeNode1.h"                 //二叉树的结点类

class Tree1                            //二叉树类
{
  public:
    TreeNode1 *root;                   //指向根结点的指针

    Tree1(char *str="");               //构造函数
    ~Tree1();
 
    TreeNode1* create(char *str);      //以标明空子树的先序遍历序列构建二叉树
    void destroy(TreeNode1 *p);        //撤销二叉树

    void preorder();                   //先序遍历二叉树
    void inorder();                    //中序遍历二叉树
    void postorder();                  //后序遍历二叉树
};

Tree1::Tree1(char *str)                //构造函数
{
    cout<<"创建二叉树: "<<endl;
    root=create(str);
    cout<<endl;
}

TreeNode1* Tree1::create(char *str)    //以标明空子树的先序遍历序列构建二叉树
{                                      //返回指向根结点的指针
    TreeNode1 *p=NULL;
    static int i=0;                    //静态变量i指出str中的当前位置
    cout<<"调用"<<str[i]<<endl;        //显示中间结果
    if(str[i]!='.')
    {
        p=new TreeNode1(str[i]);       //非"."时，建立结点
        i++;                           //应该在递归调用之前 
        p->left=create(str);           //建立左子树，递归调用
        p->right=create(str);          //建立右子树，递归调用
    }
    else 
        i++;
    if(p==NULL)                        //ch="."时，p为NULL 
       cout<<"返回NULL"<<endl;
    else
       cout<<"返回"<<p->data<<endl;
    return p;
}

Tree1::~Tree1()                        //析构函数
{
    cout<<"撤销二叉树: ";
    destroy(root);
    root=NULL;
    cout<<endl;
}

void Tree1::destroy(TreeNode1 *p)      //撤销以p为根的子二叉树，后序遍历算法
{
    if(p!=NULL)
    {
        destroy(p->left);
        destroy(p->right);
        cout<<p->data<<" ";            //显示撤销结点的次序
        delete p;
    }
}

void Tree1::preorder()                 //先序遍历二叉树
{
    cout<<"先序遍历二叉树:  ";   
    root->preorderChild(root);         //调用TreeNode1类先序遍历二叉树的递归函数
    cout<<endl;   
}

void Tree1::inorder()                  //中序遍历二叉树
{
    cout<<"中序遍历二叉树:  ";   
    root->inorderChild(root);          //调用TreeNode1类中序遍历二叉树的递归函数
    cout<<endl;   
}

void Tree1::postorder()                //后序遍历二叉树
{
    cout<<"后序遍历二叉树:  ";   
    root->postorderChild(root);        //调用TreeNode1类后序遍历二叉树的递归函数
    cout<<endl;   
}