binstree.h

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

/* 二叉搜索树（树中的成员都是唯一的）
 * 二叉搜索树应属有序表，所以不提供修改当前数据成员的函数，因为如何随意修改，会毁坏树结构
 * 如果使用者有此需要，可自行添加和修改，但务必小心更改数据成员时不要毁坏树结构，否则可能会搜索不到树中的某成员
 */

#ifndef BINARY_SEARCH_TREE_CLASS
#define BINARY_SEARCH_TREE_CLASS

#include "treenode.h"
#include "dclinkedlist.h"	// 链表，用于遍历

template <class T>
class BinSTree
{
    private:
        // 指向树根及当前节点的指针
        TreeNode<T> *root;
        TreeNode<T> *current;

		// 用于遍历的栈
		DCLinkedList < TreeNode<T>* > iterstack;  

        // 树中数据项个数
        int size;
      
        // 用于复制构造函数及赋值运算符
        TreeNode<T> *CopyTree(TreeNode<T> *t);

        // 用于析构函数，赋值运算符及 ClearList 方法
        void DeleteTree(TreeNode<T> *t);

        // 在函数 Find 和 Delete 中用来定位节点及其双亲在树中的位置
        TreeNode<T> *FindNode(const T& item, TreeNode<T>* & parent) const;

		// 用于遍历的函数
		TreeNode<T> *GoFarLeft(TreeNode<T> *t); // 用于中序遍历

    public:
        // 构造函数，析构函数
        BinSTree(void);
        BinSTree(const BinSTree<T>& tree);
        ~BinSTree(void);
        
        // 赋值运算符
        BinSTree<T>& operator= (const BinSTree<T>& rhs);

        // 标准的表处理方法
        bool Find(const T& item);
        void Insert(const T& item);
        void Delete(const T& item);
        void ClearList(void);
        bool ListEmpty(void) const;
        int ListSize(void) const;

		// 遍历树的函数
		// 切记：遍历过程中不可删除树节点（遍历过程中只可访问和修改树节点的数据成员），否则结果无法预料
		// 由于遍历二叉搜索树的顺序通常不重要，就选择中序遍历而不提供遍历选项了
		void Reset(void);
		void Next(void);
		bool EndOfList(void) const;

		// 访问当前节点（无法修改）
		T Data(void);
};

// 复制树 t 并使其存储在当前对象中
template <class T>
TreeNode<T> *BinSTree<T>::CopyTree(TreeNode<T> *t)
{
    TreeNode<T> *newlptr, *newrptr, *newNode;
   
    // 如果树分支为空，返回 NULL
    if (t == NULL)
        return NULL;
        
    // 复制树 t 的左子树并将其根分配给 newlptr
    if (t->left != NULL) 
        newlptr = CopyTree(t->left);
    else
        newlptr = NULL;
 
    // 复制树 t 的右子树并将其根分配给 newrptr
    if (t->right != NULL) 
        newrptr = CopyTree(t->right);
    else
        newrptr = NULL;
 
    // 为当前根节点分配存储器并将其数据值和指针分配给它的子树，返回其指针
    newNode = new TreeNode<T>(t->data, newlptr, newrptr);
    return newNode;
}

// 删除当前对象存储的树
template <class T>
void BinSTree<T>::DeleteTree(TreeNode<T> *t)
{
    if (t != NULL)
    {
        DeleteTree(t->left);
        DeleteTree(t->right);
        delete t;
    }
}

// 在树中搜索数据项，若找到，则返回节点地址及指向其双亲的指针；否则，返回 NULL
template <class T>
TreeNode<T> *BinSTree<T>::FindNode(const T& item, TreeNode<T>* & parent) const
{   
    // 用指针 t 从根开始遍历树
    TreeNode<T> *t = root;
    
    // 根的双亲为 NULL
    parent = NULL;
    
    // 若子树为空，则循环结束
    while(t != NULL)
    {
        // 若找到键值，则退出
        if (item == t->data)
            break;
        else 
        {
            // 修改双亲指针，并移到左子树或右子树
            parent = t;
            if (item < t->data)
                t = t->left;
            else 
                t = t->right;
        }
    }
    
    // 返回指向节点的指针；若没找到，则返回 NULL
    return t;
}

// 构造函数，初始化 root，current 为空，size 为 0
template <class T>
BinSTree<T>::BinSTree(void):root(NULL), current(NULL), size(0)
{}

// 复制构造函数
template <class T>
BinSTree<T>::BinSTree(const BinSTree<T>& tree)
{
    // 将 tree 复制到当前对象，分配 current 和 size
    root = CopyTree(tree.root);
    current = root;
    size = tree.size;
}

// 析构函数
template <class T>
BinSTree<T>::~BinSTree(void)
{
    ClearList();
}

// 删除树中的所有节点
template <class T>
void BinSTree<T>::ClearList(void)
{
    DeleteTree(root);
    root = current = NULL;
    size = 0;
}

// 赋值运算符
template <class T>
BinSTree<T>& BinSTree<T>::operator= (const BinSTree<T>& rhs)
{
    // 不能将树复制到自身
    if (this == &rhs)
        return *this;
        
    // 清除当前树，将新树复制到当前对象
    ClearList();
    root = CopyTree(rhs.root);
    
    // 将 current 指针指向 root 并设置树的 size 值
    current = root;
    size = rhs.size;
    
    // 返回当前对象的指针
    return *this;
}

// 在树中搜索 item，若找到，则将节点数据赋给 item
template <class T>
bool BinSTree<T>::Find(const T& item)
{
    // 使用 FindNode，它需要 parent 参数
    TreeNode<T> *parent;

    // 在树中搜索 item，将匹配的节点赋给 current
    current = FindNode(item, parent);
    return (current != NULL);
}

// 指示树是否为空
template <class T>
bool BinSTree<T>::ListEmpty(void) const
{
    return (size == 0);
}

// 返回树中的数据项个数
template <class T>
int BinSTree<T>::ListSize(void) const
{
    return size;
}

// 往查找树中插入数据项，若元素重复，则更新现有元素
template <class T>
void BinSTree<T>::Insert(const T& item)
{
    // t 为遍历过程中的当前节点，parent 为前一节点
    TreeNode<T> *parent = NULL;
    
	// 如果已有该成员，则返回
	if (FindNode(item, parent) != NULL)
		return;
	else
	{
		// 创建新的叶子节点
		TreeNode<T> *newNode = new TreeNode<T>(item,NULL,NULL);
		
		// 若 parent 为 NULL，则将其作为根节点插入
		if (parent == NULL)
			root = newNode;
        
		// 若 item < parent->data，则将其作为左孩子插入        
		else if (item < parent->data)                   
			parent->left = newNode;
        
		else
			// 若 item >= parent->data，作为右孩子插入     
			parent->right = newNode;
        
		// current 赋值为新节点的地址并将 size 加 1
		current = newNode;
		size++;
	}
}

// 如果 item 在树中，将其删除
template <class T>
void BinSTree<T>::Delete(const T& item)
{
    // DNodePtr = 指向被删除节点 D 的指针
    // PNodePtr = 指定节点 D 的双亲节点 P 的指针
    // RNodePtr = 指向替换 D 的节点 R 的指针
    TreeNode<T> *DNodePtr, *PNodePtr, *RNodePtr;
    
    // 搜索数据值为 item 的节点，并保存该节点的双亲节点的指针
    if ((DNodePtr = FindNode (item, PNodePtr)) == NULL)
        return;
    
    // 如果 D 有一个指针为 NULL，则替换节点为其另一枝的某一节点
    if (DNodePtr->right == NULL)
        RNodePtr = DNodePtr->left;
    else if (DNodePtr->left == NULL)
        RNodePtr = DNodePtr->right;
        
    // DNodePtr 的两个指针均不为 NULL
    else
    {
        // 寻找并卸下 D 的替换节点。从节点 D 的左子树开始，找数据值小于 D 的数据值的
        // 最大值，将该节点从树中断开
        
        // PofRNodePtr = 指向替换节点双亲的指针
        TreeNode<T> *PofRNodePtr = DNodePtr;
        
        // 第一种可能的替换为 D 的左孩子
        RNodePtr = DNodePtr->left;
    
        // 从 D 的左孩子的右子树继续往下搜索最大值，并记录当前节点及其双亲节点的
        // 指针，最后，我们将找到替换节点
        while(RNodePtr->right != NULL)
        {
            PofRNodePtr = RNodePtr;
            RNodePtr = RNodePtr->right;
        }
        
        if (PofRNodePtr == DNodePtr)
            // 被删除节点的左孩子为替换节点，将 D 的右子树赋给 R
            RNodePtr->right = DNodePtr->right;
        else
        {
            // 至少往右子树移动了一个节点，从树中删除替换节点，将其左子树赋给其双亲
            PofRNodePtr->right = RNodePtr->left;
            
            // 用替换节点代替 DNodePtr
            RNodePtr->left = DNodePtr->left;
            RNodePtr->right = DNodePtr->right;
        }
    }

    // 完成到双亲节点的连接。删除根节点，并给新更赋值
    if (PNodePtr == NULL)
        root = RNodePtr;
        
    // 将 R 连到 P 的正确一枝上
    else if (DNodePtr->data < PNodePtr->data)
        PNodePtr->left = RNodePtr;
    else
        PNodePtr->right = RNodePtr;
        
    // 释放被删节点内存并将树的大小减 1
    delete DNodePtr;
    size--;
}

// 返回当前节点的数据值（只能访问，无法修改）
template <class T>
T BinSTree<T>::Data(void)
{
	if (current == NULL)
		throw "BinSTree::Data: invalid reference!";
	
	return current->data;
}

// 返回从 t 开始的子树左边分支最左下方节点的地址，并将经过节点的地址压入栈中
template <class T>
TreeNode<T> *BinSTree<T>::GoFarLeft(TreeNode<T> *t)
{
   // 若 t 为 NULL，则返回 NULL
   if (t == NULL)
      return NULL;
      
   // 遍历树的最左边，往栈中压入每个节点的地址直到遇到左指针为 NULL 的节点
   // 返回指向该节点的指针
   while (t->left != NULL)
   {
      iterstack.InsertFront(t);
      t = t->left;
   }
   return t;
}

// 准备遍历整个树
template <class T>
void BinSTree<T>::Reset(void)
{
	iterstack.ClearList();
	current = GoFarLeft(root);
}

// 将 current 设为下一节点
template <class T>
void BinSTree<T>::Next(void)
{
	if (current == NULL)
		return;
	
	if (current->right != NULL)
		current = GoFarLeft(current->right);
	else if (!iterstack.ListEmpty())
	{
		current = iterstack.Data();
		iterstack.DeleteFront();
	}
	else
		current = NULL;	// 遍历结束
}

// 用来终止循环
template <class T>
bool BinSTree<T>::EndOfList(void) const
{
	return (current == NULL);
}

#endif  // BINARY_SEARCH_TREE_CLASS