以下是对二叉树的基本操作的实现，如创建无序二叉树，二叉排序树，三种递归遍历和非递归遍历，查找，插入，删除,以及树叶的计算和树的深度的计算等。
#include "iostream.h"
#include "stdlib.h"
#include "stack.h"
#pragma once
template<class T>
class CBiTree
{
public:
CBiTree(void)
{
}
~CBiTree(void)
{
}
static struct _tagBiTNode
{
T data;
struct _tagBiTNode* lchild;
struct _tagBiTNode* rchild;
};
private:
typedef _tagBiTNode BiTNode,*BiTree;
public:
bool CreateBiTree(BiTree& t);
bool PreOrderTraverse(BiTree t,void (*visit)(T data));
bool PreOrderTraverseEx(BiTree t,void (*visit)(T data));
bool InOrderTraverse(BiTree t,void (*visit)(T data));
bool InOrderTraverseEx(BiTree t,void (*visit)(T data));
bool PostOrderTraverse(BiTree t,void (*visit)(T data));
bool PostOrderTraverseEx(BiTree t,void (*visit)(T data));
void CountLeaf(BiTree t,int& count);
int BiTreeDepth(BiTree t);
//二叉排序树的操作
void CreateSortBiTree(BiTree &root,T* a,int n);
void InsertNode(BiTree &root,T e);
bool DeleteNode(BiTree &t,T& e);
bool SearchNode(BiTree t,T key,BiTree f,BiTree& p);
private:
void deleteNode(BiTree& p);
};
//创建一个无序二叉树
template<typename T>
bool CBiTree<T>::CreateBiTree(BiTree& t)
{
int n;
cin>>n;
if(n==0) t=NULL;
else
{
if(!(t = new BiTNode)) return false;
t->data = n;
CreateBiTree(t->lchild);
CreateBiTree(t->rchild);
}
return true;
}
//先根遍历 递归表示
template<typename T>
bool CBiTree<T>::PreOrderTraverse(BiTree t,void (*visit)(T data))
{
if(t!=NULL)
{
visit(t->data);
PreOrderTraverse(t->lchild,visit);
PreOrderTraverse(t->rchild,visit);
}
return false;
}
//先根遍历,栈表示
template<typename T>
bool CBiTree<T>::PreOrderTraverseEx(BiTree t,void (*visit)(T data))
{
try
{
CStack<BiTree>::_tagStack s; //栈
CStack<BiTree> stack ;
//if(stack == NULL)
// return false;
BiTree p = new BiTNode;
if(p == NULL)
return false;
stack.InitStack(s);
p = t;
while(p||!stack.StackEmpty(s))
{
if(p)
{
visit(p->data);
stack.Push(s,p);
p = p->lchild;
}
else
{
stack.Pop(s,p);
p = p->rchild;
}
}
stack.DestroyStack(s);
return true;
}
catch(...)
{
visit(-1);
return false;
}
}
//中序遍历,递归算法
template<typename T>
bool CBiTree<T>::InOrderTraverse(BiTree t,void (*visit)(T data))
{
if(t != NULL)
{
InOrderTraverse(t->lchild,visit);
visit(t->data);
InOrderTraverse(t->rchild,visit);
}
return true;
}
//中序遍历,栈表示
template<typename T>
bool CBiTree<T>::InOrderTraverseEx(BiTree t,void (*visit)(T data))
{
try
{
CStack<BiTree>::_tagStack s;
CStack<BiTree> stack;
BiTree p = new BiTNode;
p = t;
stack.InitStack(s);
while(p||!stack.StackEmpty(s))
{
if(p)
{
stack.Push(s,p);
p = p->lchild;
}
else
{
stack.Pop(s,p);
visit(p->data);
p = p->rchild;
}
}
stack.DestroyStack(s);
return true;
}
catch(...)
{
visit(-1);
return false;
}
}
//后序遍历,递归算法
template<class T>
bool CBiTree<T>::PostOrderTraverse(BiTree t,void (*visit)(T data))
{
if(t != NULL)
{
PreOrderTraverse(t->lchild,visit);
PreOrderTraverse(t->rchild,visit);
visit(t->data);
}
return true;
}
//后序遍历,栈表示
template<class T>
bool CBiTree<T>::PostOrderTraverseEx(BiTree t,void (*visit)(T data))
{
try
{
CStack<BiTree>::_tagStack s;
CStack<BiTree> stack;
BiTree p = new BiTNode;
p = t;
stack.InitStack(s);
while(p||!stack.StackEmpty(s))
{
if(p)
{
stack.Push(s,p->lchild);
p = p ->lchild;
}
else
{
visit(p->data);
stack.Pop(s,p);
p = p->rchild;
visit(p->data);
}
}
return true;
}
catch(...)
{
visit(-1);
return false;
}
}
//计数树叶的个数
template<class T>
void CBiTree<T>::CountLeaf(BiTree t,int& count)
{
if(t != NULL)
{
CountLeaf(t->lchild,count);
CountLeaf(t->rchild,count);
//检查结点t是否为叶子结点,若是,则定量count++
if(t->lchild == NULL &&t->rchild ==NULL)
count++;
}
}
//树的深度
template<class T>
int CBiTree<T>::BiTreeDepth(BiTree t)
{
int dep;
int depleft;
int deprigth ;
if( t==NULL)
dep = -1;
if( t != NULL )
{
depleft = BiTreeDepth(t->lchild);
deprigth = BiTreeDepth(t->rchild);
dep = 1 + ( depleft>deprigth? depleft:deprigth);
}
return dep;
}
//
template<class T>
bool CBiTree<T>::SearchNode(BiTree t,T key,BiTree f,BiTree& p)
{
if(t == NULL)
{
p = f;
return false;
}
else if(key == t->data)
{
p = t;
return true;
}
else if(key < t->data)
{
SearchNode(t->lchild,key,t,p);
}
else
SearchNode(t->rchild,key,t,p);
}
template<class T>
void CBiTree<T>::InsertNode(BiTree &root,T e)
{
BiTree t = root;
BiTree p = NULL;
BiTree newNode = new BiTNode;
while(t)
{
p = t;
if(e <=t->data)
t = t->lchild;
else
t = t->rchild;
}
newNode->data = e;
newNode->lchild = newNode->rchild =NULL;
if(p==NULL)
root = newNode;
else
if(e <p->data)
p->lchild = newNode;
else
p->rchild = newNode;
}
//找到要删除的结点,删除结点
template<class T>
void CBiTree<T>::deleteNode(BiTree& p)
{
BiTree q;
BiTree s;
if(!p->lchild)
{
q = p;
p = p->rchild;
free(q);
}
else if(!p->rchild)
{
q = p;
p = p->lchild;
free(q);
}
else
{
q = p;
s = p->lchild;
while(s->rchild)
{
q = s;
s = s->rchild;
}
p->data = s->data;
if(q!=p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
}
}
//查找要删除的结点,并删除
template<class T>
bool CBiTree<T>::DeleteNode(BiTree &t,T& e)
{
if(!t)
return false;
else
{
if(e == t->data)
deleteNode(t);
else if(e < t->data)
DeleteNode(t->lchild,e);
else
DeleteNode(t->rchild,e);
return true;
}
}
// n 为数据的总长度 用n = sizeof(a) / sizeof(a[0]);
template<class T>
void CBiTree<T>::CreateSortBiTree(BiTree &root,T* a,int n)
{
for(int i=0;i<n;i++)
{
InsertNode(root,a[i]);
}
}
/*
*************************************************************
test
*************************************************************
*/
void print(int data)
{
if(data == -1)
cout<<"\nError"<<endl;
cout<<data<<"\t";
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"\nBiTree:-----------------------\n";
CBiTree<int>::_tagBiTNode *p1= NULL;
CBiTree<int>* tree = new CBiTree<int>;
cout<<"\n树的深度为:"<<tree->BiTreeDepth(t)<<endl;
int n=0;
int a[]={8,6,9,10,23,2,3,0,4,0,5};
tree->CreateSortBiTree(p1,a,sizeof(a)/sizeof(a[0]));
cout<<"\n前序遍历\n";
tree->PreOrderTraverse(p1,&print);
cout<<"\n";
tree->PreOrderTraverseEx(p1,&print);
cout<<"\n中序遍历\n"<<endl;
tree->InOrderTraverse(p1,&print);
cout<<"\n";
tree->InOrderTraverseEx(p1,&print);
tree->CountLeaf(p1,n);
cout<<"\n树的深度为:"<<tree->BiTreeDepth(p1)<<endl;
cout<<"叶子:"<<n<<endl;
cout<<"查找"<<endl;
int k0=3;
if(tree->SearchNode(p1,3,NULL,t))
{
cout<<"找到了"<<endl;
tree->DeleteNode(p1,k0);
tree->InOrderTraverse(p1,&print);
}
else
cout<<"没找到"<<endl;
}
