模板的练习---二叉树

类别:编程语言 点击:0 评论:0 推荐:

以下是对二叉树的基本操作的实现,如创建无序二叉树,二叉排序树,三种递归遍历和非递归遍历,查找,插入,删除,以及树叶的计算和树的深度的计算等。
#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;
}

本文地址:http://com.8s8s.com/it/it25122.htm