treelib.h

安全数组 普通链表 哈希表 二叉搜索树 AVL树 集合类 通用自动机 所有类均使用模板编写

#ifndef TREE_LIBRARY_FUNCTIONS
#define TREE_LIBRARY_FUNCTIONS

#include <stdlib.h>
#include "treenode.h"

// 创建左右指针域分别为 lptr 和 rptr 的对象 TreeNode，指针的缺省值为 NULL
template <class T>
TreeNode<T> *GetTreeNode(T item,TreeNode<T> *lptr = NULL,
                         TreeNode<T> *rptr = NULL)
{
   // 调用函数 new 创建新的结点，将参数 lptr 和 rptr 传递给函数
   TreeNode<T> *p = new TreeNode<T> (item, lptr, rptr);
   
   // 返回指针
   return p;
}

// 释放与结点相连的动态内存
template <class T>
void FreeTreeNode(TreeNode<T> *p)
{
   delete p;
}

// 本函数用后序遍历法遍历树。访问函数判断结点是否为叶子结点
template <class T>
void CountLeaf (TreeNode<T> *t, int& count)
{
   // 后序遍历
   if (t != NULL) 
   {
      CountLeaf(t->Left(), count);  // 遍历左子树
      CountLeaf(t->Right(), count); // 遍历右子树

      // 检查结点 t 是否为叶子结点（无后代）。若是，则变量 Count 加 1
      if (t->Left() == NULL && t->Right() == NULL)
         count++;
   }
}

// 本函数用后序遍历法计算左、右子树深度并返回该树的深度为
// 1 + max(depthLeft,depthRight)。空树的深度为 -1
template <class T>
int Depth (TreeNode<T> *t)
{
   int depthLeft, depthRight, depthval;

   if (t == NULL) 
	  depthval = -1;
   else
   {
      depthLeft= Depth(t->Left());
	  depthRight= Depth(t->Right());
      depthval = 1 +
		 (depthLeft > depthRight? depthLeft:depthRight);
   }
   return depthval;
}

// 复制树 t 并返回新树的根 
template <class T>
TreeNode<T> *CopyTree(TreeNode<T> *t)
{  
   // 变量 newnode 指向每个由调用 GetTreeNode 产生的新结点，然后将这个结点连入
   // 新树 p。newlptr 和 newrptr 指向 newnode 的孩子结点，作为参数传给 GetTreeNode
   TreeNode<T> *newlptr, *newrptr, *newnode;
   
   // 当树为空时终止递归
   if (t == NULL)
      return NULL;
      
   if (t->Left() != NULL) 
      newlptr = CopyTree(t->Left());
   else
      newlptr = NULL;
 
   if (t->Right() != NULL) 
      newrptr = CopyTree(t->Right());
   else
      newrptr = NULL; 
   
   // 先创建孩子结点，然后再创建双亲结点，自底向上地建立一颗新树
   newnode = GetTreeNode(t->data, newlptr, newrptr);
   
   // 返回指向新创建结点的指针
   return newnode;
}

// 使用后序扫描算法遍历树中结点并删除每个结点
template <class T>
void DeleteTree(TreeNode<T> *t)
{
   if (t != NULL)
   {
      DeleteTree(t->Left());
      DeleteTree(t->Right());
      FreeTreeNode(t);
   }
}

#endif   // TREE_LIBRARY_FUNCTIONS