bintree.cpp

树的建立算法和树的遍历操作。。。下载解压即可

#ifndef BinTree_CPP
#define BinTree_CPP

#include "BinTree.h"

#include <iostream>
#include <queue>
using namespace std;

template <class T>
BinTree<T>::BinTree()
{ m_Root=NULL; } 


template <class T>
BinTree<T>::~BinTree()
{ Free(); }

template <class T>
BinTree<T>::BinTree(vector<T> &pre) // 根据pre创建二叉树
{ m_pre=pre; m_prei=0;      // 完成数据准备
  m_Root=DoCreateByPre(); // 调用核心函数
}

template <class T>
BinTreeNode<T> *BinTree<T>::DoCreateByPre()
{ T e=m_pre[m_prei];   m_prei++;
  if(e=='*') return(NULL); 
  BinTreeNode<T> *p=new BinTreeNode<T>;
  p->data=e;
  p->lchild=DoCreateByPre();  // 建左子树
  p->rchild=DoCreateByPre();  // 建右子树
  return(p);
}

template <class T>
BinTree<T>::BinTree(vector<T> &pre,vector<T> &mid)
{ m_pre=pre;  m_mid=mid; // 完成数据准备
  int n=m_pre.size();
  m_Root=DoCreateByPreMid(0,0, n);   // 调用核心函数
}

template <class T>
BinTreeNode<T> *BinTree<T>::DoCreateByPreMid(int ipre,int imid,int n)
{ if(n==0) return(NULL); // 最终解决方案
  BinTreeNode<T> *p=new BinTreeNode<T>;
  p->data = m_pre[ipre];
  for(int i=0; i<n; i++)    // 在中序序列中定位根结点
    if(m_pre[ipre]==m_mid[imid+i]) break;
  p->lchild = DoCreateByPreMid(ipre+1, imid, i);
  p->rchild = DoCreateByPreMid(ipre+i+1,imid+i+1,n-i-1);
  return p;
}

template <class T>
void BinTree<T>::Free()  // 释放整个树的空间
{ DoFree(m_Root); m_Root=NULL; }

template <class T>
void BinTree<T>::DoFree(BinTreeNode<T> *p)
{ if(p==NULL)  return;
  DoFree( p->lchild );  // 释放左子树
  DoFree( p->rchild );  // 释放右子树
  delete p;           
}

template <class T>
void BinTree<T>::TraverseDFS(int kind)	// 深度遍历二叉树
{ switch(kind)
  { case 1: TraversePre (m_Root); break;
    case 2: TraverseMid (m_Root); break;
    case 3: TraversePost(m_Root); break;
  }
  cout<<endl;
}

template <class T>
void BinTree<T>::TraversePre(BinTreeNode<T> *p)
{ if(p==NULL) return;
  cout<<p->data; 
  TraversePre(p->lchild); 
  TraversePre(p->rchild); 
}

template <class T>
void BinTree<T>::TraverseMid(BinTreeNode<T> *p)
{ if(p==NULL) return;
  TraverseMid(p->lchild); 
  cout<<p->data; 
  TraverseMid(p->rchild); 
}

template <class T>
void BinTree<T>::TraversePost(BinTreeNode<T> *p)
{ if(p==NULL) return;
  TraversePost(p->lchild); 
  TraversePost(p->rchild); 
  cout<<p->data; 
}

template <class T>
void BinTree<T>::TraverseBFS()	// 层次/广度遍历二叉树
{ BinTreeNode<T> *p; 
  queue<BinTreeNode<T> *>Q;  // Q为指针队列
  if(m_Root==NULL) return;
  Q.push(m_Root);  // 将m_Root进队列
  while(!Q.empty()) 
  { p=Q.front();   // 将队首元素赋给p
    Q.pop();       // 队首元素出队列
    cout<<p->data;
    if(p->lchild)  Q.push(p->lchild);
    if(p->rchild)  Q.push(p->rchild);
  }
	cout<<endl;
}

template <class T>
int BinTree<T>::GetHeight()   // 计算高度
{ return Height(m_Root); }

template <class T>
int BinTree<T>::Height(BinTreeNode<T> *p)
{ int left,right;
  if(p==NULL) return(0);
  left =Height(p->lchild); 
  right=Height(p->rchild); 
  if (left>right) return left+1;
  return right+1;
}

template <class T>
int BinTree<T>::Count(BinTreeNode<T> *p)
{ int left,right;
  if(p==NULL)   return(0);
  left= Count(p->lchild);
  right=Count(p->rchild);
  return 1+left+right;
}

template <class T>
int BinTree<T>::GetCount()    // 计算结点数
{ return Count(m_Root); }

template <class T>
BinTreeNode<T> *BinTree<T>::Search(T e)
{ return DoSearch(m_Root, e); }

template <class T>
BinTreeNode<T> *BinTree<T>::DoSearch(BinTreeNode<T> *p,T e)
{ if(p==NULL)     return(NULL);
  if(p->data==e)  return(p);
  BinTreeNode<T> *q=DoSearch(p->lchild, e);
  if(q)   return q;
  return DoSearch(p->rchild, e);
}


template <class T>
BinTreeNode<T> *BinTree<T>::SearchParent(T e) // 查找父结点
{ return DoSearchParent(m_Root, e); }

template <class T>
BinTreeNode<T> *BinTree<T>::DoSearchParent(BinTreeNode<T> *p,T e)
{ if(p==NULL) return NULL;
  if(p->lchild && p->lchild->data==e) return p;
  if(p->rchild && p->rchild->data==e) return p;
  BinTreeNode<T> *q=DoSearchParent(p->lchild, e);
  if(q)  return q;
  return DoSearchParent(p->rchild, e);
}

template <class T>
BinTree<T>::BinTree(BinTree<T> &tree) // 复制树对象
{ m_Root=DoCopy(tree.m_Root); }

template <class T>
BinTreeNode<T> * BinTree<T>::DoCopy(BinTreeNode<T> *p)
{ if(p==NULL)  return NULL;
  BinTreeNode<T> *newp=new BinTreeNode<T>;
	newp->data=p->data;
  newp->lchild= DoCopy(p->lchild);  // 复制左子树
  newp->rchild= DoCopy(p->rchild);  // 复制右子树
  return newp; 
}

template <class T>
int BinTree<T>::GetTreeCount(int n)
{ int left,count=0;
  if(n==0 || n==1)    return(1); 
  for(left=n-1; left>=0; left--)
     count+=GetTreeCount(left)*GetTreeCount(n-1-left);
  return(count);
}

#endif