threadtree1.h

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

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

class ThreadTree1                      //线索二叉树类
{
  public:
    ThreadTreeNode1 *root;             //指向根结点的指针

    ThreadTree1(char *str="");         //构造函数，创建二叉树
    ThreadTreeNode1* create(char *str);//以标明空子树的先序遍历序列构建二叉树

    void inThreadTree();                           //中序线索化二叉树
    void inThreadTree(ThreadTreeNode1 *p);         //中序线索化以p结点为根的子树

    ThreadTreeNode1* innext(ThreadTreeNode1 *p);   //返回中根次序下的后继结点
    void inorder();                                //中根次序遍历中序线索二叉树

    ThreadTreeNode1* inlast(ThreadTreeNode1 *p);   //返回中根次序下的前趋结点
    void inorder_last();                           //中根次序遍历中序线索二叉树

    ThreadTreeNode1* prenext(ThreadTreeNode1 *p);  //返回先根次序下的后继结点
    void preorder();                               //先根次序遍历中序线索二叉树

    ThreadTreeNode1* postlast(ThreadTreeNode1 *p); //返回后根次序下的前驱结点
    void postorder();                              //后根次序遍历中序线索二叉树
};

ThreadTree1::ThreadTree1(char *str)    //构造函数，创建二叉树
{                                      //与Tree1.h中函数相同
    root=NULL;
    if(str!="")
    {
        root=create(str);
        cout<<endl;
    }
}

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


void ThreadTree1::inThreadTree()       //中序线索化二叉树
{
    cout<<"中序线索化："<<endl;
    inThreadTree(root);
}

void ThreadTree1::inThreadTree(ThreadTreeNode1 *p)  //中序线索化以p结点为根的子树
{                                      
    static ThreadTreeNode1 *front=NULL;//front指向p的前驱结点
    if(p!=NULL)
    {
        inThreadTree(p->left);         //中序线索化p的左子树

        if(p->left==NULL)              //p的左子树为空时
        {                              //设置p的left为指向front的线索
            p->ltag=1;
            p->left=front;
        }

        if(p->right==NULL)             //p的右子树为空时
            p->rtag=1;                 //设置p的right为线索的标志
        if(front!=NULL && front->rtag==1) 
            front->right=p;            //设置front的right为指向p的线索
               
        if(front!=NULL)                //显示中间结果
            cout<<"front="<<front->data<<"\t\t";
        else
            cout<<"front=NULL\t";
        cout<<"  p="<<p->data<<"  ";
        cout<<"  ltag="<<p->ltag<<"  ";
        cout<<"  rtag="<<p->rtag<<"\n";

        front=p;
        inThreadTree(p->right);        //中序线索化p的右子树
    }
}

ThreadTreeNode1* ThreadTree1::innext(ThreadTreeNode1 *p)
{                                      //返回中根次序下的后继结点
    if(p->rtag==1)                     //右子树为空时
        p=p->right;                    //right就是指向后继结点的线索
    else                               //右子树非空时
    {
        p=p->right;                    //进入右子树
        while(p->ltag==0)              //找到最左边的子孙结点
            p=p->left;
    }
    return p;
}

void ThreadTree1::inorder()            //中根次序遍历中序线索二叉树
{
    ThreadTreeNode1 *p=root;
    if(p!=NULL)
    {
        cout<<"中根次序遍历中序线索二叉树:  ";   
        while(p->ltag==0)
            p=p->left;                 //找到根的最左边子孙结点
        do
        {
            cout<<p->data<<" ";
            p=innext(p);               //返回p的后继结点
        }while(p!=NULL);
        cout<<endl;
    }
}    

ThreadTreeNode1* ThreadTree1::inlast(ThreadTreeNode1 *p)
{                                      //返回中根次序下的前趋结点
    if(p->ltag==1)                     //左子树为空时
        p=p->left;                     //left就是指向前驱结点的线索
    else                               //左子树非空时
    {
        p=p->left;                     //进入左子树
        while(p->rtag==0)              //找到最右边的子孙结点
            p=p->right;
    }
    return p;
}

void ThreadTree1::inorder_last()       //中根次序遍历中序线索二叉树
{
    ThreadTreeNode1 *p=root;
    if(p!=NULL)
    {
        cout<<"中根次序遍历中序线索二叉树:  ";   
        while(p->rtag==0)
            p=p->right;                //找到根的最右边子孙结点
        do
        {
            cout<<p->data<<" ";
            p=inlast(p);               //返回p的前驱结点
        }while(p!=NULL);
        cout<<endl;
    }
}    

ThreadTreeNode1* ThreadTree1::prenext(ThreadTreeNode1 *p)
{                                      //返回先根次序下的后继结点
    if(p->ltag==0)                     //左子树非空时
        p=p->left;                     //左孩子就是p的后继结点
    else
    {
        if(p->rtag==0)                 //左子树为空而右子树非空时，此if语句可不要，包含在下面的循环条件中
            p=p->right;                //右孩子是p的后继结点
        else                           //叶子，后继是其某个中序祖先的右孩子
        {
            while(p->rtag==1 && p->right!=NULL)
                p=p->right;            //寻找其某个中序祖先
            p=p->right;                //右孩子是p的后继结点
        }
    }
    return p;
}

void ThreadTree1::preorder()           //先根次序遍历中序线索二叉树
{
    ThreadTreeNode1 *p=root;
    if(p!=NULL)
    {
        cout<<"先根次序遍历中序线索二叉树:  ";   
        do
        {
            cout<<p->data<<" ";
            p=prenext(p);              //返回先根次序下的后继结点
        }while(p!=NULL);
        cout<<endl;
    }
}    

ThreadTreeNode1* ThreadTree1::postlast(ThreadTreeNode1 *p)
{                                      //返回后根次序下的前驱结点
    if(p->rtag==0)                     //右子树非空时
        p=p->right;                    //右孩子是p的前驱结点
    else                               //否则，前驱是自己（或其某个中序祖先）的左孩子
    {
        while(p->ltag==1 && p->left!=NULL)
            p=p->left;                 //寻找其某个中序祖先
        p=p->left;                     //左孩子是p的前驱结点
    }
    return p;
}

void ThreadTree1::postorder()          //后根次序遍历中序线索二叉树
{
    ThreadTreeNode1 *p=root;
    if(p!=NULL)
    {
        cout<<"后根次序遍历中序线索二叉树:  ";   
        do
        {
            cout<<p->data<<" ";
            p=postlast(p);             //返回后根次序下的前驱结点
        }while(p!=NULL);
        cout<<endl;
    }
}    

/*
ThreadTreeNode1* ThreadTree1::prelast(ThreadTreeNode1 *p)???
{                                      //返回先根次序下的前驱结点
    if(p->ltag==0)                     //左子树非空时
        p=p->left;                     //左孩子就是p的后继结点
    else
    {
        if(p->rtag==0)                 //左子树为空而右子树非空时
            p=p->right;                //右孩子是p的后继
        else
        {
            while(p->rtag==1 && p->right!=NULL)  //叶子结点
                p=p->right;            //后继是其某个中序祖先的右孩子
            p=p->right;
        }
    }
    return p;
}

void ThreadTree1::preorder_last()           //先根次序遍历中序线索二叉树
{
    ThreadTreeNode1 *p=root;
    if(p!=NULL)
    {
        cout<<"先根次序遍历中序线索二叉树:  ";   
        do
        {
            cout<<p->data<<" ";
            p=prelast(p);              //返回先根次序下的前驱结点
        }while(p!=NULL);
        cout<<endl;
    }
}    



  
	//与Tree1.h中函数相同
ThreadTree1::~ThreadTree1()            //析构函数
{
    cout<<"撤销二叉树: ";
    destroy(root);
    root=NULL;
    cout<<endl;
}

void ThreadTree1::destroy(ThreadTreeNode1 *p)  //撤销以p为根的子二叉树，后序遍历算法
{//必须改成循环算法？？必须沿后根的后继方向走，或先根的前驱方向走？？
    if(p!=NULL)
    {
        destroy(p->left);            //??Stack overflow 因空子树的链非空了
        destroy(p->right);
        cout<<p->data<<" ";            //显示撤销结点的次序
        delete p;
    }
}
*/