gentree.h

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

/* 一般树（使用二叉树方法实现的一般树）
 * 函数传回指针是为效率问题，得到指针只可用于访问其数据成员，不可在外部调用 delete 释放，要删除树节点请调用本类的 delete 函数
 */

#ifndef GENERAL_TREE_CLASS
#define GENERAL_TREE_CLASS

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

enum NextItemPos {TI_CURRENT, TI_ROOT, TI_CHILD, TI_NEXT, TI_PARENT /*TI_PREVIOUS*/};
enum InsertItemPos {TI_FIRST, TI_LAST};
enum IterMathod {TI_PREORDER, TI_POSTORDER, TI_LEVERORDER};	// 遍历方法（前序、后序和层次）

template <class T>
class GenTree
{
private:
	// 指向树根及当前节点的指针
	TreeNode<T> *root;
	TreeNode<T> *current;
	
	// 树中数据项个数
	int size;

	// 上次选择的遍历方法
	enum IterMathod itermathod;
	// 用于遍历的堆栈
	DCLinkedList < TreeNode<T>* > iterstack;
	// 用于遍历的函数
	TreeNode<T> *GoFarLeft(TreeNode<T> *t); // 用于后序遍历
	void GoAllChild(TreeNode<T> *t);		// 用于层次遍历 	

	// 用于复制构造函数及赋值运算符
	TreeNode<T> *CopyTree(TreeNode<T> *t);
	
public:
	// 构造函数，析构函数
	GenTree(void);
	GenTree(const GenTree<T>& tree);
	~GenTree(void);
	
	// 赋值运算符
	GenTree<T>& operator= (const GenTree<T>& rhs);
	
// 返回匹配元素（得到指针后不可在外部 delete，否则会造成树结构损坏）
//	TreeNode<T> *Find(const T& item);
	/*
		TI_FIRST	// 插入兄弟节点的头部
		TI_LAST		// 插入兄弟节点的末尾
	*/
	TreeNode<T> *Insert(const T& item, TreeNode<T>* parent, enum InsertItemPos insertpos = TI_LAST);
	void Delete(TreeNode<T> *t);	// 如果删除了 current 指向的节点，会导致 current = NULL
	void ClearTree(void);
	bool TreeEmpty(void) const;
	int TreeSize(void) const;		// 树的总节点数

	// 遍历树的函数
	// 切记：遍历过程中不可删除树节点（遍历过程中只可访问和修改树节点的数据成员），否则结果无法预料
	void Reset(enum IterMathod itm = TI_POSTORDER);
	void Next(void);
	bool EndOfList(void) const;
	
	// 树的特殊方法（得到指针后不可在外部 delete，否则会造成树结构损坏）
	/*	
		TI_CURRENT	// 取得当前节点
		TI_ROOT		// 取得树根节点
		TI_CHILD	// 取得当前节点的第一个子节点
		TI_NEXT		// 取得当前节点的下一个兄弟节点
		TI_PREVIOUS	// 取得当前节点的上一个兄弟节点(sorry, not implement) 
		TI_PARENT	// 取得当前节点的父节点	
	*/
	TreeNode<T> *GetNext(enum NextItemPos nextpos);
};

// 构造函数，初始化 root、current 为空，size 为 0，itermathod 为后序遍历
template <class T>
GenTree<T>::GenTree(void):root(NULL), current(NULL), size(0), itermathod(TI_POSTORDER)
{}

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

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

// 删除以 t 为根的子树
template <class T>
void GenTree<T>::Delete(TreeNode<T> *t)
{
    if (t != NULL)
    {
        Delete(t->left);
        Delete(t->right);
		if (t == current)
			current = NULL;
        delete t;
		size--;
	}
}

// 复制树 t 并使其存储在当前对象中
template <class T>
TreeNode<T> *GenTree<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);
	if (newlptr != NULL)
	{
		newlptr->parent = newNode;
		TreeNode<T> *rptr = newlptr->right;
		while (rptr != NULL)
		{
			rptr->parent = newNode;
			rptr = rptr->right;
		}
	}

    return newNode;
}

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

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

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

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

// 返回从 t 开始的子树左边分支最左下方节点的地址，并将经过节点的地址压入栈中
template <class T>
TreeNode<T> *GenTree<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;
}

// 取得 t 的所有孩子并依次加入链表末尾
template <class T>
void GenTree<T>::GoAllChild(TreeNode<T> *t)
{
	if (t != NULL)
	{
		TreeNode<T> *rptr = t->left;
		while (rptr != NULL)
		{
			iterstack.InsertRear(rptr);
			rptr = rptr->right;
		}
	}
}

// 以选定的遍历顺序遍历整个树
template <class T>
void GenTree<T>::Reset(enum IterMathod itm)
{
	itermathod = itm;
	iterstack.ClearList();

	switch (itm)
	{
		case TI_PREORDER:
			current = root;
			break;
		case TI_POSTORDER:
			current = GoFarLeft(root);
			break;
		case TI_LEVERORDER:
			current = root;
			GoAllChild(root);
			break;
		default:
			throw "GenTree::Reset: Unknown iterator method";
	}
}

// 按指定遍历顺序将 current 设为下一节点
template <class T>
void GenTree<T>::Next(void)
{
	if (current == NULL)
		return;

	switch (itermathod)
	{
		case TI_POSTORDER:	// 前序遍历
			if (current->right != NULL)
				current = GoFarLeft(current->right);
			else if (!iterstack.ListEmpty())
			{
				current = iterstack.Data();
				iterstack.DeleteFront();
			}
			else
				current = NULL;	// 遍历结束
			break;
		case TI_PREORDER:	// 后序遍历
			if (current->left != NULL)
			{
				iterstack.InsertFront(current);
				current = current->left;
			}
			else if (current->right != NULL)
				current = current->right;
			else if (!iterstack.ListEmpty())
			{
				current = iterstack.Data();
				iterstack.DeleteFront();
				current = current->right;
			}
			else
				current = NULL;
			break;
		case TI_LEVERORDER:	// 层次遍历
			if (!iterstack.ListEmpty())
			{
				iterstack.Reset();
				current = iterstack.Data();
				iterstack.DeleteFront();
				GoAllChild(current);
			}
			else
				current = NULL;
			break;
		default:
			throw "GenTree::Next: Unknown iterator method";
	}
}

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

template <class T>
TreeNode<T> *GenTree<T>::Insert(const T& item, TreeNode<T>* parent, enum InsertItemPos insertpos)
{
	TreeNode<T> *newNode = new TreeNode<T>(item);

	// 没有 parent 的节点，只能是根节点
	if (parent == NULL)
	{
		ClearTree();
		root = current = newNode;
		size++;
		return newNode;
	}

	current = newNode;
	size++;
	switch (insertpos)
	{
		case TI_FIRST:
			newNode->right = parent->left;
			parent->left = newNode;
			break;
		case TI_LAST:
			{
				TreeNode<T> *rptr = parent->left;
				if (rptr == NULL)	// 这个节点还没有孩子
				{
					parent->left = newNode;
					break;
				}
				while (rptr->right != NULL)
					rptr = rptr->right;
				rptr->right = newNode;
			}
			break;
		default:
			throw "GenTree::Insert: Unknown insert pos";
	}
	return newNode;
}

template <class T>
TreeNode<T> *GenTree<T>::GetNext(enum NextItemPos nextpos)
{
	if (nextpos == TI_ROOT)
		return root;
	else if (current == NULL)
		return NULL;
	
	switch (nextpos)
	{
		case TI_CURRENT:
			return current;
		case TI_CHILD:
			return current->left;
		case TI_NEXT:
			return current->right;
		case TI_PARENT:
			return current->parent;
		default:
			throw "GenTree::GetNext: Unknown next pos";
	}
}

#endif  // GENTREE_CLASS