几个数据结构的知识点的实现,希望大家多提意见.
只写了几个,不全
:)
(7)线索二叉树（下）
template <class T>
class ThreadTree
{
friend class ThreadI<T>;
private:
ThreadNode<T> * root;
public:
ThreadTree(ThreadNode<T> * item) { root=item;}
void PreOrder(ThreadNode<T> * t) const;
void InOrder(ThreadNode<T> * t) const;
void PostOrder(ThreadNode<T> * t) const;
void LevelOrder_Queue();
void PreOrder_Stack();
void InOrder_Stack();
void PostOrder_Stack();
virtual int IsEmpty() { return(root==NULL?1:0);}
ThreadNode<T> * Father(ThreadNode<T> * begin,ThreadNode<T> * current);
virtual ThreadNode<T> * Left(ThreadNode<T> * current)
{
return ((current!=NULL)?current->left:NULL);
}
virtual ThreadNode<T> * Right(ThreadNode<T> * current)
{
return ((current!=NULL)?current->right:NULL);
}
ThreadNode<T> * GetRoot() const
{
return root;
}
int Find(ThreadNode<T> * & current,T item);
void DelSubtree(ThreadNode<T> * current);
ThreadNode<T> * Brother(ThreadNode<T> * temp);
};
template <class T>
void ThreadTree<T>::PreOrder(ThreadNode<T> * t) const
{
if(t!=NULL)
{
cout<<t->data;
if(t->LeftThread==0)
PreOrder(t->left);
if(t->RightThread==0)
PreOrder(t->right);
}
}
template <class T>
void ThreadTree<T>::InOrder(ThreadNode<T> * t) const
{
if(t!=NULL)
{
if(t->LeftThread==0)
InOrder(t->left);
cout<<t->data;
if(t->RightThread==0)
InOrder(t->right);
}
}
template <class T>
void ThreadTree<T>::PostOrder(ThreadNode<T> * t) const
{
if(t!=NULL)
{
if(t->LeftThread==0)
PostOrder(t->left);
if(t->RightThread==0)
PostOrder(t->right);
cout<<t->data;
}
}
template<class T>
void ThreadTree<T>::LevelOrder_Queue()
{
Queue<ThreadNode<T> * > q;
if(root!=NULL)
{
ThreadNode<T> * temp=root;
q.QInsert(temp);
while(!q.QEmpty())
{
temp=q.QDelete();
if(temp!=NULL)
cout<<temp->data;
if((temp->left!=NULL)&&(temp->LeftThread==0))
q.QInsert(temp->left);
if((temp->right!=NULL)&&(temp->RightThread==0))
q.QInsert(temp->right);
}
return;
}
}
template<class T>
void ThreadTree<T>::PreOrder_Stack()
{
if(root==NULL)
return;
Stack<ThreadNode<T> * > s;
ThreadNode<T> * p=root;
while(p!=NULL)
{
cout<<p->data;
s.Push(p);
if((p->left!=NULL)&&(p->LeftThread==0))
p=p->left;
else
if((p->right!=NULL)&&(p->RightThread==0))
p=p->right;
else
p=NULL;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
p=Brother(p);
}
while(!s.StackEmpty())
{
while(p!=NULL)
{
cout<<p->data;
s.Push(p);
if((p->left!=NULL)&&(p->LeftThread==0))
p=p->left;
else
if((p->right!=NULL)&&(p->RightThread==0))
p=p->right;
else
p=NULL;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
p=Brother(p);
}
}
}
template<class T>
void ThreadTree<T>::InOrder_Stack()
{
if(root==NULL)
return;
if((root->LeftThread==1)&&(root->RightThread==1))
{
cout<<root->data;
return;
}
Stack<ThreadNode<T> * > s;
ThreadNode<T> * p=root;
ThreadNode<T> * jl[100];
for(int i=0;i<100;i++)
jl[i]=NULL;
int num=0;
while(p!=NULL)
{
s.Push(p);
if((p->left!=NULL)&&(p->LeftThread==0))
p=p->left;
else
if((p->right!=NULL)&&(p->RightThread==0))
p=p->right;
else
p=NULL;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
int p_pos=0;
int r_pos=0;
for(int i=0;i<100;i++)
{
if(jl[i]==p)
p_pos=1;
if(jl[i]==Father(root,p))
r_pos=1;
}
if(p_pos==0)
{
cout<<p->data;
jl[num]=p;
num++;
}
if(r_pos==0)
{
cout<<Father(root,p)->data;
jl[num]=Father(root,p);
num++;
}
p=Brother(p);
}
while(!s.StackEmpty())
{
while(p!=NULL)
{
s.Push(p);
if((p->left!=NULL)&&(p->LeftThread==0))
p=p->left;
else
if((p->right!=NULL)&&(p->RightThread==0))
p=p->right;
else
p=NULL;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
return;
int p_pos=0;
int r_pos=0;
for(int i=0;i<100;i++)
{
if(jl[i]==p)
p_pos=1;
if(jl[i]==Father(root,p))
r_pos=1;
}
if(p_pos==0)
{
cout<<p->data;
jl[num]=p;
num++;
}
if(r_pos==0)
{
cout<<Father(root,p)->data;
jl[num]=Father(root,p);
num++;
}
p=Brother(p);
}
}
}
template<class T>
void ThreadTree<T>::PostOrder_Stack()
{
if(root==NULL)
return;
Stack<ThreadNode<T> * > s;
ThreadNode<T> * p=root;
while(p!=NULL)
{
s.Push(p);
if((p->left!=NULL)&&(p->LeftThread==0))
p=p->left;
else
if((p->right!=NULL)&&(p->RightThread==0))
p=p->right;
else
p=NULL;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
{
if(p==root)
cout<<p->data;
return;
}
cout<<p->data;
p=Brother(p);
}
while(!s.StackEmpty())
{
while(p!=NULL)
{
s.Push(p);
if((p->left!=NULL)&&(p->LeftThread==0))
p=p->left;
else
if((p->right!=NULL)&&(p->RightThread==0))
p=p->right;
else
p=NULL;
}
while((p==NULL)&&(!s.StackEmpty()))
{
p=s.Pop();
if(s.StackEmpty())
{
if(p==root)
cout<<p->data;
return;
}
cout<<p->data;
p=Brother(p);
}
}
}
template <class T>
ThreadNode<T> * ThreadTree<T>::Father(ThreadNode<T> * begin,ThreadNode<T> * current)
{
ThreadNode<T> * temp;
if(begin==NULL)
return NULL;
if( ((begin->LeftThread==0)&&(begin->left==current)) || ((begin->RightThread==0)&&(begin->right==current)) )
return begin;
if( (begin->RightThread==0)&&( ( temp=Father(begin->right,current) )!=NULL ) )
return temp;
if( (begin->LeftThread==0)&&((temp=Father(begin->left,current))!=NULL) )
return temp;
return NULL;
}
template <class T>
int ThreadTree<T>::Find(ThreadNode<T> * & current,T item)
{
int i=0;
if(current==NULL)
return 0;
if(current->data==item)
return 1;
if((current->LeftThread==0)&&(i=Find(current->left,item))!=0)
return 1;
if((current->RightThread==0)&&(i=Find(current->right,item))!=0)
return 1;
return 0;
}
template <class T>
void ThreadTree<T>::DelSubtree(ThreadNode<T> * current)
{
if(current!=NULL)
{
if(current->LeftThread==0)
DelSubtree(current->left);
if(current->RightThread==0)
DelSubtree(current->right);
cout<<current->data;
delete current;
}
}
template <class T>
ThreadNode<T> * ThreadTree<T>::Brother(ThreadNode<T> * temp)
{
if((temp==NULL)||(root==NULL))
return NULL;
ThreadNode<T> * item=Father(root,temp);
if(item->RightThread==1)
return NULL;
if(item->right==temp)
return NULL;
return item->right;
}
template <class T>
class ThreadI
{
private:
ThreadNode<T> * current;
ThreadTree<T> * TE;
void Reset();
public:
ThreadI(ThreadTree<T> * Tree) { TE=Tree;current=Tree->root;}
ThreadNode<T> * FirstOf(ThreadNode<T> * q=current);
ThreadNode<T> * LastOf(ThreadNode<T> * q=current);
ThreadNode<T> * First();
ThreadNode<T> * Last();
ThreadNode<T> * Next();
ThreadNode<T> * Prior();
};
template <class T>
ThreadNode<T> * ThreadI<T>::FirstOf(ThreadNode<T> * q)
{
while(q->LeftThread==0)
q=q->left;
return q;
}
template <class T>
ThreadNode<T> * ThreadI<T>::LastOf(ThreadNode<T> * q)
{
while(q->RightThread==0)
q=q->right;
return q;
}
template <class T>
ThreadNode<T> * ThreadI<T>::First()
{
return (current=FirstOf(current));
}
template <class T>
ThreadNode<T> * ThreadI<T>::Last()
{
return (current=LastOf(current));
}
template <class T>
ThreadNode<T> * ThreadI<T>::Next()
{
if(current==LastOf(TE->root))
return NULL;
ThreadNode<T> * p=current->right;
if(current->RightThread==1)
{
current=current->right;
return current;
}
else
current=FirstOf(p);
return current;
}
template <class T>
ThreadNode<T> * ThreadI<T>::Prior()
{
if(current==FirstOf(TE->root))
{
Reset();
return NULL;
}
ThreadNode<T> * p=current->left;
if(current->LeftThread==1)
return (current=p);
else
current=LastOf(p);
return current;
}
int main()
{
ThreadNode<int> * tni1=new ThreadNode<int>(1);
ThreadNode<int> * tni2=new ThreadNode<int>(2);
ThreadNode<int> * tni3=new ThreadNode<int>(3);
ThreadNode<int> * tni4=new ThreadNode<int>(4);
ThreadNode<int> * tni5=new ThreadNode<int>(5);
ThreadNode<int> * tni6=new ThreadNode<int>(6);
ThreadNode<int> * tni7=new ThreadNode<int>(7);
ThreadNode<int> * tni8=new ThreadNode<int>(8);
ThreadNode<int> * tni9=new ThreadNode<int>(9);
tni1->InsertRight(tni2);
tni1->InsertLeft(tni3);
tni2->InsertRight(tni4);
tni2->InsertLeft(tni5);
tni4->InsertRight(tni6);
tni4->InsertLeft(tni7);
tni3->InsertLeft(tni8);
tni3->InsertRight(tni9);
ThreadTree<int> * ttree=new ThreadTree<int>(tni1);
ThreadNode<int> * tni10=ttree->Father(tni1,tni8);
ttree->LevelOrder_Queue();
cout<<tni10->data<<":)"<<endl;
ttree->InOrder(tni1);
cout<<endl;
cout<<"~~~~~~~~~~~~~~~";
ttree->PreOrder_Stack();
int i=ttree->Find(tni1,2);
cout<<endl;
cout<<i<<endl;
ThreadI<int> * Thi=new ThreadI<int>(ttree);
ThreadNode<int> * tni11=Thi->First();
tni10=Thi->Next();
tni10=Thi->Next();
tni10=Thi->Next();
tni10=Thi->Next();
tni10=Thi->Next();
tni10=Thi->Next();
tni10=Thi->Next();
cout<<tni10->data<<endl;
return 1;
}
