| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1309 人关注过本帖
标题:几个数据结构知识点的实现(6)
取消只看楼主 加入收藏
Achaocmt
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2006-2-3
收藏
 问题点数:0 回复次数:2 
几个数据结构知识点的实现(6)

几个数据结构的知识点的实现,希望大家多提意见.
只写了几个,不全
:)


(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;
}

搜索更多相关主题的帖子: 数据结构 知识点 
2006-02-10 00:54
Achaocmt
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2006-2-3
收藏
得分:0 
请教一下了,
使用template<class T>和使用template< typename T>有什么区别吗?

我相信,我会找到属于自己的方向
2006-02-10 14:05
Achaocmt
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2006-2-3
收藏
得分:0 

谢谢了啊.
看来我还有很多东西要学啊.


我相信,我会找到属于自己的方向
2006-02-12 20:18
快速回复:几个数据结构知识点的实现(6)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039126 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved