xiansuohua.txt

线索化二叉树的源程序

附源程序:
#include<iostream.h>
template<class Type> class bintree;
template<class Type> class bintreenode{
       friend class bintree<Type>;
       public:
       bintreenode():leftchild(NULL),rightchild(NULL),leftthread(0),rightthread(0){}
              bintreenode(Type d):data(d),leftchild(NULL),rightchild(NULL),leftthread(0),rightthread(0){}
              bintreenode<Type> *leftchild,*rightchild;
              Type data;
              int leftthread,rightthread;
};
template<class Type> class bintree{
       public:
              bintree():root(NULL){}
              bintree(Type value):refvalue(value),root(NULL){}
              void CreateBinTree (bintreenode<Type> * &current);
              int IsEmpty(){return root==NULL?1:0;}
              void destroy(bintreenode<Type> *current);bintreenode<Type> *root;              
       private:
                     Type refvalue;
};
template<class Type> void bintree<Type>::CreateBinTree(bintreenode<Type> * &current){
           Type item;
              cout<<"Please input a number:";
              cin>>item;  
        if (item!=refvalue)      {
            current=new bintreenode<Type>(item);         
            CreateBinTree(current->leftchild);
            CreateBinTree(current->rightchild);
        }
        else current=NULL;    
}
template<class Type>void bintree<Type>::destroy(bintreenode<Type> *current){

if(current!=NULL){
              destroy(current->leftchild);
              destroy(current->rightchild);
           delete current;
       }
}
template<class Type> class threadtree{
       public:
              threadtree(bintree<Type> &tree):t(tree),pre(NULL){current=t.root;}
              bintreenode<Type>* first();
              bintreenode<Type> *next();
              void inorder();
              void inthread(bintreenode<Type> *p,bintreenode<Type> * &pre);
              bintree<Type> &t;
              bintreenode<Type> *current;
              bintreenode<Type> *pre;
};
template<class Type>bintreenode<Type> *threadtree<Type>::first(){

current=t.root;
       while(current->leftthread==0)
         current=current->leftchild;
    return current;
}
template<class Type>bintreenode<Type> *threadtree<Type>::next(){
       bintreenode<Type> *p=current->rightchild;
       if(current->rightthread==0) {
              while(p!=NULL&&p->leftthread==0)
                     p=p->leftchild;
       }
       current=p;
       return current;              
}
template<class Type>void threadtree<Type>::inorder(){
       bintreenode<Type> * p;
       for(p=first();p!=NULL;p=next())
              cout<<p->data<<"  ";
       cout<<endl;
}

template<class Type>void hreadtree<Type>::inthread(bintreenode<Type> *current,bintreenode<Type> * &pre){
       if(current!=NULL)       {
              inthread(current->leftchild,pre);
              if(current->leftchild==NULL){
                     current->leftchild=pre;
                     current->leftthread=1;
              }
              if(pre!=NULL)            {
                     if(pre->rightchild==NULL){
                     pre->rightchild=current;
                     pre->rightthread=1;     
                     }
              }
              pre=current;         
              inthread(current->rightchild,pre);
              }
}