WRlw5zlq.rar//brinarytree.h
#include<iostream>
#include<math.h>
#include<assert.h>
#include"stack.h"
#include"queue.h"
using namespace std;
struct Level{
int yLevel;
int xIndent;
};
template<typename T>class BinaryTree;
template<typename T>class BinaryTreeNode{
public:
BinaryTreeNode(T data){element=data; LeftChild=NULL; RightChild=NULL; lTag=0;rTag=0;}
friend class BinaryTree<T>;
private:
BinaryTreeNode<T> *LeftChild,*RightChild;
T element;
int lTag,rTag;
};
template<typename T>class BinaryTree
{
public:
BinaryTree(){root=NULL;}
~BinaryTree();
void MakeEmpty(){ MakeEmpty(root);} //清除二叉树
int Research(T data); //寻找结点
void CreatTree(T data); //建立二叉树
void PrintVTree(){ PrintVTree(root);} //打印图形二叉树
void PrinTree(){ PrinTree(root,0);} //用凹凸法打印图型二叉树
void PreOrder(){ PreOrder(root);} //非递归前序遍历
void InOrder(){InOrder(root);} //非递归中序遍历
void PostOrder(){PostOrder(root);} //非递归后序遍历
void COrder(){ COrder(root);} //层次遍历
void Countleaf(int &c){ Countleaf(root,c);} //计算叶结点个数
int Depth_queue(){ return Depth_queue(root);} //用队列求二叉树深度
int Depth_stack(){ return Depth_stack(root);} //用栈求二叉树深度
void PackOrder(){PackOrder(root);} //用括号遍历二叉树
void creatpackettree(char *str); //用括号建立二叉树
void m_creatbrinarytree(T *str,int n); //建立满二叉树
BinaryTreeNode<T>* pre_and_in_creatbinary(char *ppos,char * ipos,int n);//用中序周游跟前序周游建立二叉树
void InThread(){ InThread(root);} //中序线索二叉树
void In_thread_Order(){ In_thread_Order(root);} //中序线索周游二叉树
void FindNextinInorderTree(T data){ //中序线索中找指定结点在前序下的后续
BinaryTreeNode<T> *p;
p=FindNextinInorderTree(root,data);
if(p==NULL)
cout<<"\n该结点在前序下没有后续!"<<endl<<endl;
else{
cout<<endl;
cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<p->element<<endl<<endl;
}
}
void FindBeforeinInorderTree(T data){ //中序线索中找指定结点在后序下的前驱
BinaryTreeNode<T> *p;
p=FindBeforeinInorderTree(root,data);
if(p==NULL)
cout<<"\n该结点在后序下没有前驱!"<<endl<<endl;
else{
cout<<endl;
cout<<"在中序线索中找指定结点在后序下的前驱:"<<p->element<<endl<<endl;
}
}
void Post_Thread_Order(){ Post_Thread_Order(root);} //后序周游中序线索二叉树
void Del_BinaryTreeNode(T data){ Del_BinaryTreeNode(root,data);}//排序二叉树删除结点
void Del_BinaryTreeNode_EX(T data){ Del_BinaryTreeNode_EX(root,data);}//改进的二叉树删除结点
void InsertNode_in_Inthread(T find_data,T insert_data){ InsertNode_in_Inthread(root,find_data,insert_data);}//在中序线索二叉树插入结点
void Ancestor(T data){ Ancestor(root,data);}//打印指定结点的祖先
void Closed_Ancestor(T data1,T data2){ Closed_Ancestor(root,data1,data2);}//打印指定两个结点的最近祖先
void PreOrder_Ex(){ PreOrder_Ex(root);}//改进的非递归前序遍历，这个遍历少了一个子循环，高效很多
private:
BinaryTreeNode<T> *root,*p;
void MakeEmpty(BinaryTreeNode<T> *t);
void PrintVTree(BinaryTreeNode<T> *t);
void PrinTree(BinaryTreeNode<T> *b,int level);
void PreOrder(BinaryTreeNode<T> *t);
void InOrder(BinaryTreeNode<T> *t);
void PostOrder(BinaryTreeNode<T> *t);
void COrder(BinaryTreeNode<T> *t);
void Countleaf(BinaryTreeNode<T> *t,int &c);
int Depth_queue(BinaryTreeNode<T> *t);
int Depth_stack(BinaryTreeNode<T> *t);
void PackOrder(BinaryTreeNode<T> *t);
void InThread(BinaryTreeNode<T> *t);
void In_thread_Order(BinaryTreeNode<T> *t);
BinaryTreeNode<T> *FindNextinInorderTree(BinaryTreeNode<T> *t,T data);
BinaryTreeNode<T> *FindBeforeinInorderTree(BinaryTreeNode<T> *t,T data);
void Post_Thread_Order(BinaryTreeNode<T> *t);
BinaryTreeNode<T>* Is_PostOrder_first_Node(BinaryTreeNode<T> *t);//判断是否后序周游中序线索二叉树的第一个结点
void Del_BinaryTreeNode(BinaryTreeNode<T> *t,T data);
void Del_BinaryTreeNode_EX(BinaryTreeNode<T> *t,T data);
void InsertNode_in_Inthread(BinaryTreeNode<T> *t,T find_data, T insert_data);
void Ancestor(BinaryTreeNode<T> *t,T data);
void Closed_Ancestor(BinaryTreeNode<T> *t,T data1,T data2);
void PreOrder_Ex(BinaryTreeNode<T> *t);
};
template<typename T>BinaryTree<T>::~BinaryTree()
{
MakeEmpty(root);
}
template<typename T>void BinaryTree<T>::MakeEmpty(BinaryTreeNode<T> *t)
{
if(t!=NULL)
{
if(t->lTag==0)
MakeEmpty(t->LeftChild);
if(t->rTag==0)
MakeEmpty(t->RightChild);
delete t;
}
}
template<typename T>int BinaryTree<T>::Research(T data)
{
BinaryTreeNode<T> *ptr=root;
p=NULL;
while(ptr)
{
if(ptr->element==data) {p=ptr; return 1;}
if(ptr->element>data)
{
p=ptr;
ptr=ptr->LeftChild;
}
else{
p=ptr;
ptr=ptr->RightChild;
}
}
return 0;
}
template<typename T> void BinaryTree<T>::CreatTree(T data)
{
BinaryTreeNode<T> *current;
if(Research(data)==0)
{
current=new BinaryTreeNode<T>(data);
if(p==NULL) root=current;
else if(p->element>data)
p->LeftChild=current;
else p->RightChild=current;
}
}
template<typename T>void BinaryTree<T>::PrintVTree(BinaryTreeNode<T> *t){
int screenWidth=64;
int dataWidth=2;
queue<BinaryTreeNode<T> *> Q;
queue<Level> QI;
BinaryTreeNode<T> *p;
Level s,s1,s2;
double offset,level=-1,i;
Q.EnQue(t);
s.xIndent=screenWidth/dataWidth;
s.yLevel=0;
QI.EnQue(s);
while(!Q.IsEmpty()&&!QI.IsEmpty())
{
s2=s;
p=Q.DeQue();
s=QI.DeQue();
if(s.yLevel!=level){
cout<<"\n\n第"<<s.yLevel<<"层";
level=s.yLevel;
for(i=0;i<s.xIndent-1;i++) cout<<" ";
}
else
for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" ";
cout<<p->element;
if(p->LeftChild!=NULL)
{
Q.EnQue(p->LeftChild);
s1.yLevel=s.yLevel+1;
offset=screenWidth/pow(dataWidth,s1.yLevel+1);
s1.xIndent=s.xIndent-offset;
QI.EnQue(s1);
}
if(p->RightChild!=NULL)
{
Q.EnQue(p->RightChild);
s1.yLevel=s.yLevel+1;
offset=screenWidth/pow(dataWidth,s1.yLevel+1);
s1.xIndent=s.xIndent+offset;
QI.EnQue(s1);
}
}
}
template<typename T>void BinaryTree<T>::PrinTree(BinaryTreeNode<T> *b,int level){
if(b!=NULL)
{
PrinTree(b->RightChild,level+1);
if(level!=0){
for(int i=0;i<6*(level-1);i++)cout<<" ";
cout<<"-----";
}
cout<<b->element<<endl;
PrinTree(b->LeftChild,level+1);
}
}
template<typename T>void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T> *p=t;
while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);
cout<<p->element<<'\t';
p=p->LeftChild;
}
p=s.Pop();
p=p->RightChild;
}
}
template<typename T>void BinaryTree<T>::InOrder(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T> *p=t;
while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);
p=p->LeftChild;
}
p=s.Pop();
cout<<p->element<<'\t';
p=p->RightChild;
}
}
template<typename T>void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T> *p=t;
int tag[255],top=-1;
while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);
tag[++top]=0;
p=p->LeftChild;
}
if(top>-1)
if(tag[top]==1)
{
cout<<s.GetTop()->element<<'\t';
s.Pop();
top--;
}
else{
p=s.GetTop();
tag[top]=1;
p=p->RightChild;
}
}
}
template<typename T>void BinaryTree<T>::COrder(BinaryTreeNode<T> *t)
{
BinaryTreeNode<T> *p;
p=t;
queue<BinaryTreeNode<T> *> Q;
Q.EnQue(p);
while(!Q.IsEmpty())
{
p=Q.DeQue();
cout<<p->element<<"\t";
if(p->LeftChild!=NULL)
Q.EnQue(p->LeftChild);
if(p->RightChild!=NULL)
Q.EnQue(p->RightChild);
}
}
template<typename T>void BinaryTree<T>::Countleaf(BinaryTreeNode<T> *t,int &c)
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T> *p=t;
int tag[255],top=-1;
while(!s.IsEmpty()||p!=NULL)
{
while(p)
{
s.Push(p);
tag[++top]=0;
p=p->LeftChild;
}
if(top>-1)
if(tag[top]==1)
{
if(s.GetTop()->LeftChild==NULL && s.GetTop()->RightChild==NULL)
c++;
s.Pop();
top--;
}
else{
p=s.GetTop();
tag[top]=1;
p=p->RightChild;
}
}
}
template<typename T>int BinaryTree<T>::Depth_queue(BinaryTreeNode<T> *t)
{
queue<BinaryTreeNode<T> *> Q;
queue<Level> QI;
int depth;
Level y,y1;
BinaryTreeNode<T> *p=t;
y.yLevel=1;
Q.EnQue(p);
QI.EnQue(y);
while(!Q.IsEmpty())
{
p=Q.DeQue();
y=QI.DeQue();
if(p->LeftChild!=NULL)
{
Q.EnQue(p->LeftChild);
y1.yLevel=y.yLevel+1;
QI.EnQue(y1);
}
if(p->RightChild!=NULL)
{
Q.EnQue(p->RightChild);
y1.yLevel=y.yLevel+1;
QI.EnQue(y1);
}
}
depth=y.yLevel;
return depth;
}
template<typename T>int BinaryTree<T>::Depth_stack(BinaryTreeNode<T> *t)
{
stack<BinaryTreeNode<T>*> S;
BinaryTreeNode<T> *p;
int tag[100],top=-1;
p=t;
stack<Level> s,s1; //s1是用来记录当前有左右孩子的结点的高读
Level y,y1,temp;
temp.yLevel=0;
y.yLevel;
while(p!=NULL||!S.IsEmpty()){
while(p!=NULL){
S.Push(p);
y.yLevel=0;
s.Push(y);
tag[++top]=0;
p=p->LeftChild;
}
if(top>-1)
if(tag[top]==1)
{
y=s.Pop();
if(S.GetTop()->LeftChild!=NULL&&S.GetTop()->RightChild!=NULL)
{
temp=s1.Pop();
if(temp.yLevel>y.yLevel)
s.Push(temp);
else{
y1.yLevel=y.yLevel+1;
s.Push(y1);
}
}
else{
y1.yLevel=y.yLevel+1;
s.Push(y1);
}
S.Pop();
top--;
}
else {
p=S.GetTop();
if(p->LeftChild!=NULL&&p->RightChild!=NULL)//当这个结点是它左孩子的后续并且这个结点有右孩子
{
y=s.Pop();
y1.yLevel=y.yLevel+1;
s1.Push(y1);
temp=y1;
}
tag[top]=1;
p=p->RightChild;
}
}
y=s.Pop();
return y.yLevel;
}
template<typename T>void BinaryTree<T>::creatpackettree(char *str)
{
BinaryTreeNode<T> *p;
stack<BinaryTreeNode<T> *> s;
int k,i=0;
char ch=str[i];
while(ch!='\0')
{
switch(ch)
{
case '(': s.Push(p); k=1; break;
case ')': s.Pop(); break;
case ',': k=2; break;
default:
p=new BinaryTreeNode<T>(ch);
if(root==NULL)
root=p;
else{
switch(k)
{
case 1: s.GetTop()->LeftChild=p; break;
case 2: s.GetTop()->RightChild=p; break;
}
}
}
i++;
ch=str[i];
}
}
[此贴子已经被作者于2006-7-13 21:32:25编辑过]
