?? binarytree.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];
}
}
template<typename T>void BinaryTree<T>::PackOrder(BinaryTreeNode<T> *t)
{
if(t!=NULL)
{
cout<<t->element;
if(t->LeftChild!=NULL||t->RightChild!=NULL)
{
cout<<"(";
PackOrder(t->LeftChild);
if(t->RightChild!=NULL)
cout<<",";
PackOrder(t->RightChild);
cout<<")";
}
}
}
template<typename T>void BinaryTree<T>::m_creatbrinarytree(T *str,int n)//根據滿二叉樹的性質，2i為左孩子，2i+1為右孩子
{
queue<BinaryTreeNode<T>*> q;
BinaryTreeNode<T> *p,*p1;
int i=1;
p=new BinaryTreeNode<T>(str[i-1]);
root=p;
q.EnQue(root);
while(i<n)
{
p1=q.DeQue();
if(2*i-1<n)
{
p=new BinaryTreeNode<T>(str[2*i-1]);
p1->LeftChild=p;
q.EnQue(p1->LeftChild);
}
if(2*i<n)
{
p=new BinaryTreeNode<T>(str[2*i]);
p1->RightChild=p;
q.EnQue(p1->RightChild);
}
i++;
}
}
template<typename T>BinaryTreeNode<T> * BinaryTree<T>::pre_and_in_creatbinary(char *ppos,char *ipos,int n)
{
char *rpos;
int k;
BinaryTreeNode<T> *p;
if(n<=0)
return NULL;
p=new BinaryTreeNode<T>(*ppos);
for(rpos=ipos;rpos<ipos+n;rpos++)
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -