treenode.h

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

/* 二叉树（二叉树也可用于创建普通树）结点
* 
*/

#ifndef TREENODE_CLASS
#define TREENODE_CLASS

template <class T>
class BinSTree;

template <class T>
class GenTree;

template <class T>
class TreeNode
{
protected:
	// 指向节点左右孩子、父节点的指针
	TreeNode<T> *left;
	TreeNode<T> *right;
	TreeNode<T> *parent;	// 该成员在 GenTree 中使用
	
public:
	// 公有成员，允许外部修改的数据值
	T data;
		
	// 构造函数
	TreeNode (const T& item, TreeNode<T> *lptr = NULL,
		TreeNode<T> *rptr = NULL, TreeNode<T> *pptr = NULL);
		
	// 访问指针域的函数
	TreeNode<T>* Left(void) const;
	TreeNode<T>* Right(void) const;
	TreeNode<T>* Parent(void) const;
		
	friend class BinSTree<T>;
	friend class GenTree<T>;
};

// 构造函数，初始化节点的数据和指针域，对于空子树，将其指针域赋值为 NULL
template <class T>
TreeNode<T>::TreeNode (const T& item, TreeNode<T> *lptr,
					   TreeNode<T> *rptr, TreeNode<T> *pptr): data(item), left(lptr), right(rptr), parent(pptr)
{}

// 允许用户访问左孩子
template <class T>
TreeNode<T>* TreeNode<T>::Left(void) const
{
	return left;
}

// 允许用户访问右孩子
template <class T>
TreeNode<T>* TreeNode<T>::Right(void) const
{
	return right;
}

// 允许用户访问父节点
template <class T>
TreeNode<T>* TreeNode<T>::Parent(void) const
{
	return parent;
}

#endif // TREENODE_CLASS