bintree.h

遍历线索二叉树 遍历线索二叉树

#ifndef _BINTREE_H
#define _BINTREE_H

template<typename Type> class BinaryTree;
template<typename Type> class ThreadBinTree;
template<typename Type> class ThreadPreOrderTree;

template<typename Type> class BinTreeNode
{
friend class BinaryTree<Type>;
private:
        Type data;
        BinTreeNode<Type> *lchild , *rchild , *parent;
public:
       BinTreeNode():lchild(NULL),rchild(NULL) , parent(NULL){}
       BinTreeNode(Type d):data(d) , 
       lchild(NULL) , rchild(NULL) , parent(NULL){}
       Type const& GetData() {return data;}
       BinTreeNode<Type> *GetLeftChild() const{return lchild;}
       BinTreeNode<Type> *GetRightChild() const{return rchild;}
       BinTreeNode<Type> *GetParent() const{return parent;}
       void SetData(const Type& d){data = d;} 
       void SetLeftChild(BinTreeNode<Type> *p){lchild=p;}
       void SetRightChild(BinTreeNode<Type> *p){rchild=p;}  
       void SetParent(BinTreeNode<Type> *p){parent=p;}  
};

template<typename Type> class BinaryTree
{

private:
        BinTreeNode<Type> *root;
        BinTreeNode<Type> *Parent(BinTreeNode<Type> *,
                          BinTreeNode<Type> *);
        void destroy(BinTreeNode<Type> *);
        void CreateTree(BinTreeNode<Type> * , Type);       
public:
       BinaryTree():root(NULL){}
       BinaryTree(Type d){root = new BinTreeNode<Type>(d);}
       virtual ~BinaryTree(){destroy(root);}
       virtual int isEmpty(){return root==NULL?1:0;}
       BinTreeNode<Type>* Root(){return root;}
       virtual BinTreeNode<Type> *Parent(BinTreeNode<Type> *p)
               {return Parent(root , p);}
       virtual BinTreeNode<Type> *LeftChild(BinTreeNode<Type> *p)
               {return p==NULL?NULL:p->GetLeftChild();}
       virtual BinTreeNode<Type> *RightChild(BinTreeNode<Type> *p)
               {return p==NULL?NULL:p->GetRightChild();}
       virtual BinTreeNode<Type> *MyParent(BinTreeNode<Type> *p)
               {return p==NULL?NULL:p->GetParent();}
       BinTreeNode<Type>* LeftSibling(BinTreeNode<Type> *);
       BinTreeNode<Type>* RightSibling(BinTreeNode<Type> *);
       Type Retrieve(BinTreeNode<Type> *p)
            {return p->GetData();}
       void Assign(BinTreeNode<Type> *p , Type d)
            {p->SetData(d);}     
       void InsertLeftChild(BinTreeNode<Type> *, Type);
       void InsertRightChild(BinTreeNode<Type> *, Type);
       void DeleteLeftChild(BinTreeNode<Type> *p){destroy(p->GetLeftChild());}
       void DeleteRightChild(BinTreeNode<Type> *p){destroy(p->GetRightChild());}
       void BuildSortTree(Type);
       Type Find(Type);
       BinTreeNode<Type>* SearchPreOrder(BinTreeNode<Type> * , Type);
       BinTreeNode<Type>* SearchInOrder(BinTreeNode<Type> * , Type);
};

template<typename Type> 
BinTreeNode<Type>* BinaryTree<Type>::Parent(BinTreeNode<Type> *r , BinTreeNode<Type> *p)
{
    BinTreeNode<Type> *q;
    if(r == NULL) return NULL;
    if(r->GetLeftChild()==p || r->GetRightChild()==p) return r;
    if((q=Parent(r->GetLeftChild() , p)) != NULL) return q;
        else return Parent(r->GetRightChild() , p);
}

template<typename Type>
void BinaryTree<Type>::destroy(BinTreeNode<Type> *p)
{
     if(p != NULL)
     {
          destroy(p->GetLeftChild());
          destroy(p->GetRightChild());
          delete p;
     }          
}

template<typename Type>
void BinaryTree<Type>::InsertLeftChild(BinTreeNode<Type> *p , Type d)
{
     BinTreeNode<Type> *q = new BinTreeNode<Type>(d);     
     if(p->GetLeftChild() != NULL)
         q->SetLeftChild(p->GetLeftChild());         
     q->SetParent(p);
     p->SetLeftChild(q);
}

template<typename Type>
void BinaryTree<Type>::InsertRightChild(BinTreeNode<Type> *p, Type d)
{
     BinTreeNode<Type> *q = new BinTreeNode<Type>(d);
     if(p->GetRightChild() != NULL)
          q->SetRightChild(p->GetRightChild());
     q->SetParent(p);
     p->SetRightChild(q);
}

template<typename Type>
BinTreeNode<Type>* BinaryTree<Type>::LeftSibling(BinTreeNode<Type> *p)
{
     if((p->GetParent()==NULL) || (p==p->GetParent()->GetLeftChild())) return NULL;
     else return p->GetParent()->GetLeftChild();
}

template<typename Type>
BinTreeNode<Type>* BinaryTree<Type>::RightSibling(BinTreeNode<Type> *p)
{
     if(p->GetParent()==NULL || (p=p->GetParent()->GetRightChild())) return NULL;
     else return p->GetParent()->GetLeftChild();
}

template<typename Type>
void BinaryTree<Type>::CreateTree(BinTreeNode<Type> *r , Type d)
{
     if(r == NULL) return;
     if(d < r->GetData())
     {
          if(r->GetLeftChild() == NULL)
              InsertLeftChild(r , d);
              else
                  CreateTree(r->GetLeftChild() , d);
     }
     else
     {
          if(r->GetRightChild() == NULL)
              InsertRightChild(r , d);
              else
                  CreateTree(r->GetRightChild() , d);
     }        
}

template<typename Type>
void BinaryTree<Type>::BuildSortTree(Type d)
{     
    CreateTree(root , d);
}

template<typename Type>
BinTreeNode<Type>* BinaryTree<Type>::SearchPreOrder(BinTreeNode<Type> *r , Type d)
{
    BinTreeNode<Type> *q;
    if(r==NULL) return NULL;    
    if(d == r->GetData()) return r;
    if((q=SearchPreOrder(r->GetLeftChild() , d)) != NULL) return q;
        else return SearchPreOrder(r->GetRightChild() ,d);
}

template<typename Type>
Type BinaryTree<Type>::Find(Type d)
{
     BinTreeNode<Type> *q;
     q=SearchInOrder(root , d);
     return q->GetData();
}

template<typename Type>
BinTreeNode<Type>* BinaryTree<Type>::SearchInOrder(BinTreeNode<Type> *r , Type d)
{
     BinTreeNode<Type> *q;
     if(r == NULL) return NULL;
     if((q=SearchInOrder(r->GetLeftChild() , d)) != NULL) return q;
     if(d == r->GetData()) return r;
          else return SearchInOrder(r->GetRightChild() , d);
}

template<typename Type> class ThreadBinTreeNode:public BinTreeNode<Type>
{
friend class ThreadBinTree<Type>;
friend class ThreadPreOrderTree<Type>;
private:
        int lTag , rTag;
public:
        ThreadBinTreeNode():lTag(0) , rTag(0){}
        ThreadBinTreeNode(Type d):lTag(0) , rTag(0) , BinTreeNode<Type>(d){}
        int const& GetlTag(){return lTag;}
        int const& GetrTag(){return rTag;}
        void SetlTag(const int& d){lTag = d;}
        void SetrTag(const int& d){rTag = d;}
        
};

template<typename Type> class ThreadBinTree:public BinaryTree<Type>
{
friend class ThreadPreOrderTree<Type>;
private:
        ThreadBinTreeNode<Type> *root;
        void destroy(ThreadBinTreeNode<Type> *);
        int CreateTree(ThreadBinTreeNode<Type> * , Type);
public:
        ThreadBinTree():root(NULL){}
        ThreadBinTree(Type d){root = new ThreadBinTreeNode<Type>(d);}
        virtual ~ThreadBinTree(){destroy(root);}
        ThreadBinTreeNode<Type>* Root(){return root;}
        Type Retrieve(ThreadBinTreeNode<Type> *p)
           {return p->GetData();}   
        virtual int isEmpty(){return root==NULL?1:0;}
        virtual ThreadBinTreeNode<Type> *Parent(BinTreeNode<Type> *p)
                {return p==NULL?NULL:(ThreadBinTreeNode<Type> *)p->GetParent();}
        virtual ThreadBinTreeNode<Type> *LeftChild(BinTreeNode<Type> *p)
                {return p==NULL?NULL:(ThreadBinTreeNode<Type> *)p->GetLeftChild();}
        virtual ThreadBinTreeNode<Type> *RightChild(BinTreeNode<Type> *p)
                {return p==NULL?NULL:(ThreadBinTreeNode<Type> *)p->GetRightChild();}
        void InsertLeftChild(ThreadBinTreeNode<Type> *, Type);
        void InsertRightChild(ThreadBinTreeNode<Type> *, Type);
        void DeleteLeftChild(ThreadBinTreeNode<Type> *p){destroy(p->GetLeftChild());}
        void DeleteRightChild(ThreadBinTreeNode<Type> *p){destroy(p->GetRightChild());}
        int BuildSortTree(Type);
        Type Find(Type);
        ThreadBinTreeNode<Type>* SearchPreOrder(ThreadBinTreeNode<Type> * , Type);
  
};

template<typename Type>
void ThreadBinTree<Type>::destroy(ThreadBinTreeNode<Type> *p)
{
     if(p == NULL)
          return;
          
     destroy((ThreadBinTreeNode<Type> *)p->GetLeftChild());
     destroy((ThreadBinTreeNode<Type> *)p->GetRightChild());
     delete p;
}

template<typename Type>
int ThreadBinTree<Type>::CreateTree(ThreadBinTreeNode<Type> *r , Type d)
{     
     if(r == NULL) return -1;
     if(d < r->GetData())
     {
          if(r->GetLeftChild() == NULL)
		  {InsertLeftChild(r , d); return 0;}
              else
                  CreateTree((ThreadBinTreeNode<Type> *)(r->GetLeftChild()) , d);
     }
     else
     {
          if(r->GetRightChild() == NULL)
		  {InsertRightChild(r , d); return 0;}
              else
                  CreateTree((ThreadBinTreeNode<Type> *)(r->GetRightChild()) , d);
     }    
}

template<typename Type>
void ThreadBinTree<Type>::InsertLeftChild(ThreadBinTreeNode<Type> *p, Type d)
{
     ThreadBinTreeNode<Type> *q = new ThreadBinTreeNode<Type>(d);     
     if(p->GetLeftChild() != NULL)
         q->SetLeftChild(p->GetLeftChild());         
     q->SetParent(p);
     p->SetLeftChild(q);     
}

template<typename Type>
void ThreadBinTree<Type>::InsertRightChild(ThreadBinTreeNode<Type> *p, Type d)
{
     ThreadBinTreeNode<Type> *q = new ThreadBinTreeNode<Type>(d);
     if(p->GetRightChild() != NULL)
          q->SetRightChild(p->GetRightChild());
     q->SetParent(p);
     p->SetRightChild(q);     
} 

template<typename Type>
int ThreadBinTree<Type>::BuildSortTree(Type d)
{
    return CreateTree(root , d);
}

template<typename Type>
Type ThreadBinTree<Type>::Find(Type d)
{
     ThreadBinTreeNode<Type> *q;
     q=SearchPreOrder(root , d);
     return q->GetData();
}

template<typename Type>
ThreadBinTreeNode<Type>* ThreadBinTree<Type>::SearchPreOrder(ThreadBinTreeNode<Type> *r , Type d)
{
    ThreadBinTreeNode<Type> *q;
    if(r==NULL) return NULL;    
    if(d == r->GetData()) return r;
    if((q=SearchPreOrder((ThreadBinTreeNode<Type> *)r->GetLeftChild() , d)) != NULL) return q;
        else return SearchPreOrder((ThreadBinTreeNode<Type> *)r->GetRightChild() ,d);


}
     
template<typename Type> class ThreadPreOrderTree
{
private:
        ThreadBinTree<Type>*& T;
        ThreadBinTreeNode<Type> *cur;
        void PreThread(ThreadBinTreeNode<Type> *, ThreadBinTreeNode<Type> * &);
public:
        ThreadPreOrderTree(ThreadBinTree<Type>*& Tree):T(Tree){ cur = T->root;}
        int CreatePreThread();
};

template<typename Type>
void ThreadPreOrderTree<Type>::PreThread(ThreadBinTreeNode<Type> *r, ThreadBinTreeNode<Type> * &pre)
{
     if(r == NULL)
          return;
         
     if(r->GetLeftChild() == NULL)
     {r->SetLeftChild(pre); r->SetlTag(1);}
     if(pre->GetRightChild() == NULL)
     {pre->SetRightChild(r); pre->SetrTag(1);}
     pre = r;
     
     PreThread((ThreadBinTreeNode<Type> *)r->GetLeftChild() , pre);
     PreThread((ThreadBinTreeNode<Type> *)r->GetRightChild() , pre);
}

template<typename Type>
int ThreadPreOrderTree<Type>::CreatePreThread()
{
    ThreadBinTreeNode<Type> *pre , *root;
    root = new ThreadBinTreeNode<Type>;
    root->SetlTag(1); root->SetrTag(1);

    if(cur == NULL)
    {root->SetLeftChild(root) ; root->SetRightChild(root); return -1;}
    else
    {
        root->SetLeftChild(cur);
        root->SetlTag(0);
        pre = root;
        PreThread(cur , pre);
        pre->SetRightChild(root);
        pre->SetrTag(1);
    } 
    
    return 0;  
}


#endif