binarytree_app.h

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

//--------------------------------------------------------------------------------
#ifndef BINARYTREE_APP_H_
#define BINARYTREE_APP_H_

#include <iostream>
#include "BinaryTree_Bas.h"
//----------------------------------------------------------------------
template<class T>  class  BTreeApp;
// 二叉树应用的派生类
template<class T>
class BTreeApp: public BTreeBas<T>
{
   private:
      int nodeCount,        // 结点总数
	  leafCount,            // 叶子结点总数
      lchCount,rchCount,    // 左、右孩子总数
	  height;               // 二叉树树高
      // 递归计算二叉树各种结点数
      void inorder_node_count(const BTNode<T> *p);
      // 递归计算二叉树的树高
      void preorder_height(const BTNode<T> *p,int i);
      // 递归复制二叉树
      BTNode<T>* copytree(BTNode<T> *p);
   public:
      // 构造器1：空二叉树，本书未使用
      BTreeApp(): BTreeBas() {}
      // 构造器2：使用二叉树输入类
      BTreeApp(BTree_DATA<T> tinfo): BTreeBas<T>(tinfo)
      { nodeCount=0; leafCount=0; lchCount=0; rchCount=0; height=0; }
      // 计算并显示各种结点数
      void getnodecount(BTNode<T> *p);
      // 计算并显示树高
      void getheight(BTNode<T> *p);
      // 计算并返回二叉树的备份
      void getcopytree(BTNode<T> *p,BTNode<T>*& newroot);

      // 方式1（计算各种结点数）、方式2（计算树高）
      void traver_appmode(int mode);
};
//--------------------------------------------------------------------------------
// 实现
template<class T>
void BTreeApp<T>::getnodecount(BTNode<T> *p)
{
    cout << "用中根递归遍历做统计，结点顺序为：";
    inorder_node_count(getroot());
    cout << "\n结点总数 nodeCount = " << nodeCount
         << "，叶子个数 leafCount =" << leafCount
         << "，\n左孩子数 lchCount = " << lchCount
         << "，右孩子数 rchCount = " << rchCount << endl;
}
template<class T>
void BTreeApp<T>::getheight(BTNode<T> *p)
{
    cout << "用先根遍历递归算法：";
    preorder_height(getroot(),height);
    cout << "\n树高 height = " << height << endl;   
}
template<class T>
void BTreeApp<T>::getcopytree(BTNode<T> *p,BTNode<T>*& newroot)
{
   newroot=copytree(getroot());
   cout << "复制完成！" << endl;   
}
template<class T>
void BTreeApp<T>::traver_appmode(int mode)
{
   switch(mode) {
      case 1: cout << "用中根递归遍历做统计，结点顺序为：";
              inorder_node_count(getroot());
              cout << "\n结点总数 nodeCount = " << nodeCount
                   << "，叶子个数 leafCount =" << leafCount
                   << "，\n左孩子数 lchCount = " << lchCount
                   << "，右孩子数 rchCount = " << rchCount;
              break;
      case 2: cout << "用先根遍历递归算法：";
              preorder_height(getroot(),height);
              cout << "\n树高 height = " << height;
              break;
   }
   cout << endl;   
}

// 用中根遍历统计二叉树各种结点的算法
template<class T>
void BTreeApp<T>::inorder_node_count(const BTNode<T> *p)
{
   if (p!=NULL) {
      inorder_node_count(p->lch);   // 中根遍历左子树
      cout << p->data << "  ";      // 访问根结点
      nodeCount++;                  // 结点计数
      if(p->lch==NULL && p->rch==NULL)
          leafCount++;              // 叶子计数
      if(p->lch!=NULL) lchCount++;  // 左孩子计数
      if(p->rch!=NULL) rchCount++;  // 右孩子计数
      inorder_node_count(p->rch);   // 中根遍历右子树
   }
}
// 利用先根递归遍历算法，求二叉树的树高
template<class T>
void BTreeApp<T>::preorder_height(const BTNode<T> *p,int i)
{
   if (p!=NULL) {
      cout << p->data << "  ";      // 访问根结点
      if (height<i) height=i;       // i表示当前被访问结点所在层次
      i++;     
      preorder_height(p->lch,i);    // 先根遍历左子树
	  preorder_height(p->rch,i);    // 先根遍历右子树
   }
}
// 复制二叉树
template<class T>
BTNode<T> *BTreeApp<T>::copytree(BTNode<T> *p)
{
   // newnode指向生成的新结点,newlch和newrch指向其左右子树
   BTNode<T> *newnode,*newlch,*newrch;
   if(!p) return 0;
   // 按后根次序复制左子树
   newlch=copytree(p->lch);
   // 按后根次序复制右子树
   newrch=copytree(p->rch);
   // 生成新结点
   newnode = new BTNode<T>(p->data);
   newnode->lch=newlch;
   newnode->rch=newrch;
   // 返回新复制的树的根结点指针
   return newnode;
}
//--------------------------------------------------------------------------------
#endif