bst.h

数据结构与算法设计学习得素材

//--------------------------------------------------------------------------------
#ifndef _BSTREES_H
#define _BSTREES_H
// 文件名:  bst.h
// 目标:  模板二叉搜索树（Templated binary search trees）类
// 
// 模板类 T 支持：
//   -  assignment 和 copy 构造器
//   -  operator< 运算符
//            
// 结点没有双亲指针域，所以删除操作需显式地保持结点的双亲的跟踪
//            
// 这个版本不能插入同一个元素的多重备份（如果项目已存在返回false，不做任何事情）
//--------------------------------------------------------------------------------

#pragma warning(disable: 4786)
#include <queue>
#include <string>
#include <iostream>
#include <iomanip>
#include "BSTree_Input.h"
using namespace std;
//--------------------------------------------------------------------------------
// classes defined herein

template<class T>  class  BSTree;
template<class T>  class  BSTNode;

//--------------------------------------------------------------------------------
// 结点
template<class T>
class BSTNode
{
   private:
      friend class BSTree<T>;
      BSTNode *lch, *rch;	    // 左、右孩子
      T data;		            // 数据，结点存取内容
      T& content() { return data; }
   public:
      BSTNode(const T& x): lch(NULL), rch(NULL), data(x) {}
	  // 删除整棵子树
	  // 按照BSTree::erase()清除它之前，必须使它未连接任何结点
	  // 否则整棵子树将消失
/*
      ~BSTNode() {
	     delete lch;
	     delete rch;
      }
*/
};
//--------------------------------------------------------------------------------
// 实际的二叉查找树类
template<class T>
class BSTree
{
   private:
      BSTNode<T> *root;	        // 树根结点
      size_t numbr;				// 结点数
      vector<T> tarr;           // 存储二叉树结点表
      T flag;
   public:
      // 构造器1：空二叉搜索树
      BSTree(): root(NULL), numbr(0) {}
      // 构造器2：非空二叉搜索树
      BSTree(const BSTree_DATA<T>& tinfo);
      // 为字符串空搜索树插入C串
      void insertCstr(const BSTree_DATA<char*>& tinfo);
      // 析构器
      ~BSTree() { deleteTree(root); }
      // 返回树的结点数
      int size() const { return numbr; }
      // 返回树的根结点
      BSTNode<T> *getroot() { return root; }
      // 插入操作
      bool insert(const T& x);
      // 删除操作
      bool erase(const T& x);
      // 查找操作
      bool search(const T& x);
      // 按层遍历并输出二叉树结点表
      void nodesTable(int maxlen=1);
      // 输出二叉树示意图
      void displayTree(int maxlen=1);
   private:
      // 供本类调用的辅助函数
      // 定位
      BSTNode<T> *locate(const T& x, BSTNode<T>*& pp);
      // 释放指定结点
      void deleteNode(BSTNode<T> *p);
      // 释放二叉树
      void deleteTree(BSTNode<T> *p);
};
//--------------------------------------------------------------------------------
// 实现

template<class T>
BSTree<T>::BSTree(const BSTree_DATA<T>& tinfo): root(NULL), numbr(0)
{
   for(int i=0; i<tinfo.n; i++)
       insert(tinfo.x[i]);
   flag=(T)"-";
}
// 插入一个新项目到树中
// 如果插入成功，返回true；如果项目已存在，返回false
template<class T>
bool BSTree<T>::insert(const T& x)
{
   bool lflag;  		    // 是否是左孩子?
   BSTNode<T>* par;		    // 当前结点的父结点
   BSTNode<T>* curr = root;
   while(curr) {
      if(x == curr->data)	// 不重复插入
	  return false;
      if(x < curr->data) {
	     par = curr;
	     curr = curr->lch;
	     lflag = true;
      }
      else {
	     par = curr;
	     curr = curr->rch;
	     lflag = false;
      }
   }
   if(!root) {
      root = new BSTNode<T>(x);
      ++numbr;
      return true;
   }
   if(lflag)
      par->lch = new BSTNode<T>(x);
   else
      par->rch = new BSTNode<T>(x);
   numbr++;
   return true;
}
template<class T>
void BSTree<T>::insertCstr(const BSTree_DATA<char*>& tinfo)
{   
    for(int i=0; i<tinfo.n; i++) 
       insert((string)tinfo.x[i]);
}
template<class T>
bool BSTree<T>::erase(const T& x)
{
   // p:   指向被删除的结点的指针
   // pp:  指向被删除结点的双亲的指针
   // r:   指向替换的结点的指针
   // q:   指向替换结点双亲的指针
   BSTNode<T> *p,*pp,*q,*r;
   // 用定位函数locate()搜索数据项x的位置，同时保存其双亲结点指针
   if ((p=locate(x, pp)) == NULL) return false;
   // 若有一个指针为NULL，则替换结点为另一枝的某个结点
   if (p->rch==NULL) r=p->lch;
   else
   if (p->lch==NULL) r=p->rch;
   else {
     // 被删除的结点的左、右孩子均非空
     // 寻找并卸下被删除结点的替换结点。从结点的左子树开始，寻找数据值小于被删
     // 除数据值的最大值，将该结点从树中断开
	   q=p;             // 记录替换结点的双亲
       r=p->lch;        // 可能替换为被删除结点的左孩子
       // 从被删除结点的左孩子的右子树继续下行搜索最大值，并记录当前指针及其双亲
       // 结点的指针
	   while (r->rch!=NULL) {
          q=r;  r=r->rch;
       }
	   if (q==p)
          r->rch=p->rch;
	   else {
          // 至少向右子树移动一个结点，从树中删除替换结点，将左子树赋给其双亲结点
          // 最终找到替换结点
          q->rch=r->lch;
          // 用被删除结点取代替换结点
          r->lch=p->lch;
          r->rch=p->rch;
       }
   }
   // 完成到双亲结点的连接
   if (pp==NULL) root=r;
   else
   // 将替换结点连接到被删除结点双亲的正确的一枝上
   if (p->data < pp->data)
       pp->lch=r;
   else
       pp->rch=r;
   // 释放被删除结点并将树大小减值1
   deleteNode(p);
   numbr--;
   return true;
}
// 可以使用 locate() 函数搜索，但这里未显式地调用它
template<class T>
bool BSTree<T>::search(const T& x)
{
   BSTNode<T>* curr = root;
   while(curr) {
      if(x == curr->data)
         return true;
      if(x < curr->data)
         curr = curr->lch;
      else
      	 curr = curr->rch;
   }
   return false;
}
//--------------------------------------------------------------------------------
// 按层遍历并输出二叉树结点表
template<class T>
void BSTree<T>::nodesTable(int maxlen)
{
   queue<BSTNode<T>* > Q;           // 声明一个结点指针队列
   int i=0,j;
   int num=0;
   BSTNode<T> *p=root;
   tarr.resize(0);
   cout << "按层遍历: ";
   if(p!=NULL) {
      Q.push(p);                    // 根结点入队
      tarr.push_back(p->data);
   }
   while (!Q.empty()) {
      p = Q.front();
      Q.pop();                      // 出队
      num++;
      cout << p->data << "  ";
      if(p->lch!=NULL) {
         Q.push(p->lch);            // p左孩子不空则入队
         i++;
         tarr.push_back(p->lch->data);
      }
      else {
         i++;
         tarr.push_back(flag);
      }
      if(p->rch!=NULL) {
         Q.push(p->rch);            // p右孩子不空则入队
         i++;
         tarr.push_back(p->rch->data);
      }
      else {
         i++;
         tarr.push_back(flag);
      }
      if(num>0 && num<numbr)
         while(tarr[i/2]==flag) {
             i++;  tarr.push_back(flag);
             i++;  tarr.push_back(flag);
         }
   }
   cout << endl;
   // 清除tarr中后面多余的为空标志
   int k=1, s=1;
   bool b = true, bb = true;
   while((size_t)s<=tarr.size()) { k *= 2; s += k; }
   s = s-k;
   int d = tarr.size()-s;
   while(k>1 && bb) {
      if (d>0) {
         b = true;
         j = s+d-1;
         while(b && j>s) {
            b = b && tarr[j]==flag;
            j--;
         }
         if(b) {
            for(i=j; i<j+d; i++)  tarr.pop_back();
            bb = false;
         }
      }
      k = k/2;
      d = k;
      s = s - k;
   }
   cout << "二叉搜索树结点表如下（Φ表示结点不存在）：" << endl;
   int n=1, level=0;
   k=0; 
   cout << "层次0:";
   for(j=0; j<tarr.size(); j++) {   
      cout << setw(6);
      if(tarr[j]==flag)
         cout << "Φ";
      else
         cout << tarr[j];
      k++;
      if(k % 10 == 0) 
         cout << endl << "      ";
      if (k==n) {
         cout << endl;
         level++;
         k=0;
         n *= 2;
         if (n<=tarr.size())
            cout << "层次" << level << ":";
      }
   }
   cout << endl;
}
// 输出二叉搜索树示意图
#include <stack>
template<class T>
void BSTree<T>::displayTree(int maxlen)
{
   cout << "二叉搜索树示意图如下：" << endl;
   nodesTable(maxlen);
   int midpos=41;
   int fw=(midpos-2*maxlen)/4;

   int h=0, sum=1, count=1;
   while(sum<tarr.size()) {
      count *= 2;
      sum += count;
      h++;
   }

   int n=1, k=0;
   int indx = 0, strtpos = midpos;
   int x=0, p;
   string S=" ";
   stack<int> st;
   for(int j=0; j<=h; j++) 
   {
      sum = 0;  x = 0;
      int m = (n-1)/2;
      for(k=m; k>=0; k--) 
      {          
         if(tarr[indx]==flag) 
         {
            if(k==m)  
               cout << setw(strtpos) << S;
            else
            if(k==m-1) {
               x = fw+2*(k-m+2);
               cout << setw(x) << S;
            }
            else {
               if(k==0) {
                  x = fw+2*(k-m+1);
                  if(x<=3) x=3;
                  cout << setw(x) << S;
               }
               else {
                  x = fw+2*(k-m+1)-1;
                  if(x<=3) x=3;
                  cout << setw(x) << S;
               }
            }
         }
         else 
         {
            if(k==m)  
               cout << setw(strtpos) << tarr[indx];
            else
            if(k==m-1) {
               x = fw+2*(k-m+2);
               cout << setw(x) << tarr[indx];
            }
            else {
               if(k==0) {
                  x = fw+2*(k-m+1);
                  if(x<=3) x=3;
                  cout << setw(x) << tarr[indx];
               }
               else {
                  x = fw+2*(k-m+1)-1;
                  if(x<=3) x=3;
                  cout << setw(x) << tarr[indx];
               }
            }
         }
         sum += x; 
         if (n>1) {
            if(k!=m) st.push(x);
            if(k==0) st.push((midpos-sum)/2-(4-j));
         }
         indx++;
      }

      for(k=1; k<=n/2; k++) 
      {          
         p = st.top(); st.pop();
         if(tarr[indx]==flag) 
            cout << setw(p) << S;
         else  
            cout << setw(p) << tarr[indx];
         indx++;
      }

      cout << endl << endl;
      n *= 2;
      strtpos -= fw;
   }
}
//--------------------------------------------------------------------------------
// 辅助函数
// 若定位函数locate()找到位置，则
// 返回值指向找到的结点x的指针
// pp:  指向相应双亲结点的指针
template<class T>
BSTNode<T>* BSTree<T>::locate(const T& x, BSTNode<T>*& pp)
{
   BSTNode<T>* t = root;
   pp = NULL;
   while(t) {
      if(x == t->data) break;
      else {
         pp = t;
         if(x < t->data) {
	        pp = t;
	        t = t->lch;
        }
        else
		   t = t->rch;
      }
   }
   return t;
}
template<class T>
void BSTree<T>::deleteNode(BSTNode<T> *p)
{
   p->BSTNode<T>::~BSTNode();
   delete(p);
}
template<class T>
void BSTree<T>::deleteTree(BSTNode<T> *p)
{
   if(p!=NULL) {
      deleteTree(p->lch);
      deleteTree(p->rch);
      p->BSTNode<T>::~BSTNode();
      delete(p);
   }
}
#endif