#include<iostream>
using namespace std;
class ThreadNode            //节点类
{
private:
    int LThread,RThread;                //线索域
    ThreadNode * left;                    //若有左子节点，指向它，否则，中根前驱节点
    ThreadNode * right;                   //若有右节点，指向它，否则，中根后驱节点
    int data;
public:
    ThreadNode (const int item):data(item),left(NULL),right(NULL),LThread(0),RThread(0) {}
    ThreadNode *GetLeft(void) const  {return left;}
    ThreadNode *GetRight(void) const  {return right;}
    void SetLeft(ThreadNode *t) {left=t;}
    void SetRight(ThreadNode *t) {right=t;}
    void SetData(const  int item) {data=item;}
    int & GetData (){return data;}
    void SetLThread(const int d){LThread=d;}
    void SetRThread(const int d){RThread=d;}
    int GetLThread(){return LThread;}
    int GetRThread(){return RThread;}
};
class ThreadInTree                         //中序线索二叉树类声明
{
private:
    ThreadNode *root;                          //表头节点
    int stop;
    ThreadNode *pre;                            //中序二叉树的线索化。
public:
    ThreadInTree(ThreadNode * t){root=t;}
    ThreadNode *FIO(ThreadNode *t)    //返回中根序列第一个节点
    {
        if(t==NULL)
            return NULL;
        ThreadNode *q=t;
        while((q->GetLThread())==0)
            q=q->GetLeft();
        return q;
    }

    ThreadNode *LIO(ThreadNode *t)    //返回最后一个节点
    {
        if(t==NULL)
            return NULL;
        ThreadNode *q=t;
        while((q->GetRThread())==0)
            q=q->GetRight();
        return q;
    }
    ThreadNode *PIO(ThreadNode *t,ThreadNode *p)      //t为根节点的二叉树搜索p中根前驱节点。
    {
        if(t==NULL||p==NULL)
            return NULL;
        ThreadNode *q;
        if(p==FIO(t))
            return NULL;    //首节点，无前驱。
        ThreadNode *lp=p->GetLeft();     //取p左指针、
        if((p->GetLThread())==1)
            return lp;
        q=LIO(lp);
        return q;
    }
    ThreadNode *NIO(ThreadNode *t,ThreadNode *p)       //                           后驱节点。
    {
        if(t==NULL||p==NULL)
            return NULL;
        ThreadNode *q;
        if(p==LIO(t))
            return NULL;
        ThreadNode *rp=p->GetRight();
        if((p->GetRThread())==1)
            return rp;
        q=FIO(rp);
        return q;
    }

    void InOrderOf(ThreadNode *t)        //中根遍历t的二叉树,输出
    {
        if(t==NULL)
            return ;
        ThreadNode *q;
        for(q=FIO(t);q!=NULL;q=NIO(t,q))
            cout<<q->GetData()<<endl;
    }


    void InsrtRight(ThreadNode *p,ThreadNode * s)  //插入节点p，作为s右子节点。
    {
        if(s==NULL||p==NULL)
            return ;
        p->SetRight(s->GetRight());
        p->SetRThread(s->GetRThread());
        p->SetLeft(s);
        p->SetLThread(1);
        s->SetRight(p);
        s->SetRThread(0);
        if((s->GetRThread())==0)
        {
            ThreadNode * q=p->GetRight();
            q=FIO(q);
            q->SetLeft(p);
        }
    }



    ThreadNode * GetRoot(){return root;}
    void SetRoot(ThreadNode *t){root=t;}
    int GetStop(){return stop;}
    void SetStop(int tostop)  {stop=tostop;}



    void CreateThreadingTree(int tostop)        //建立root的中序线索二叉树
    {
        SetStop(tostop);
        root=Create();
    }


    ThreadNode * Create()
    {
        ThreadNode *t,*t1,*t2;
        int item;
        cout<<"请输入值:"<<endl;
        cin>>item;
        if(item==stop)
        {
            t=NULL;
            return t;
        }
        else
        {
            if(!(t=new ThreadNode(item)))
                return NULL;
            t1=Create();
            t->SetLeft(t1);
            t2=Create();
            t->SetRight(t2);
            return t;
        }
    }


    void ThreadingTree() ;            //线索化以root为根节点的中序线索二叉树。


    void InThreading(ThreadNode *t)
    {
        ThreadNode  * x;
        if(t==NULL)
            return ;
        InThreading(t->GetLeft());
        if((t->GetLeft())==NULL)
            t->SetLThread(1);
        if((t->GetRight())==NULL)
            t->SetRThread(1);
        if(x!=NULL&&(t->GetLThread())==1)
            t->SetLeft(x);
        if(x!=NULL&&(x->GetRThread())==1)
            x->SetRight(t);
        x=t;
        if((t->GetRThread())==0)
            InThreading(t->GetRight());
    }

    ThreadNode * First(){return FIO(root);};
    ThreadNode * Last(){return LIO(root);};
    void InOrder () {InOrderOf(root);};
    ThreadNode * search(ThreadNode *t,int item);   //搜索item
    void InsertLeft(ThreadNode * p,ThreadNode *s);
    void DeleteRight(ThreadNode *p,ThreadNode *s);
    void DeleteLeft(ThreadNode *p,ThreadNode *s);
    ThreadNode *Getroot(void)
    {
        ThreadNode *t;
        t=root;
        return t;
    }

};
int main(void)
{
    ThreadInTree tree1;
    tree1.CreateThreadingTree(1000);     //创建线索二叉树
    tree1.InThreading(tree1.GetRoot());          //线索化二叉树
    cout<<"中序输出二叉树为:"<<endl;
    tree1.InOrderOf(tree1.GetRoot());
    return 0;
}



 错误：
--------------------Configuration: Cpp1 - Win32 Debug--------------------
Compiling...
Cpp1.cpp
D:\C++编程练习\Cpp1.cpp(184) : error C2512: 'ThreadInTree' : no appropriate default constructor available
Error executing cl.exe.

Cpp1.obj - 1 error(s), 0 warning(s)


[ 本帖最后由 做个好人 于 2010-6-15 17:11 编辑 ]