数据结构之二叉树

BinaryTreeNode.h

二叉树节点的定义

二叉树节点的ATD

template <class T> class BinaryTree;//提前声明，为了friend class BinaryTree<T>; 使用
template<class T> // 二叉树节点ADT
class BinaryTreeNode{
private:
	T info; // 二叉树节点的数据域
	BinaryTreeNode<T>* left;		   		//二叉树结点指向左子树的指针
	BinaryTreeNode<T>* right;    			//二叉树结点指向左子树的指针
public:
	BinaryTreeNode(); 	
	BinaryTreeNode(const T& ele);	
	BinaryTreeNode(const T& ele,BinaryTreeNode<T> *l,BinaryTreeNode<T> *r);
	T value() const; //返回 当前节点的数据域
	BinaryTreeNode<T>* leftchild() const; // 返回左子树
	BinaryTreeNode<T>* rightchild() const; // 返回右子树
	void setLeftchild(BinaryTreeNode<T>*);	// 设置左子树
	void setRightchild(BinaryTreeNode<T>*) ;	//设置当前结点的右子树
	void setValue(const T& val); //设置当前结点的数据域void setRightchild(BinaryTreeNode<T>*); // 
	bool isLeaf() const; //判定当前结点是否为叶结点,若是返回true
	BinaryTreeNode<T>& operator=(const BinaryTreeNode<T>& node);	

	friend class BinaryTree<T>; //  友元函数：使BinaryTree可以访问BinaryTreeNode的私有数据成员
};

BinaryTreeNode Implementation

template<class T>
BinaryTreeNode<T>::BinaryTreeNode()  {
	left = right = NULL;
}
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T& inf)  {	//给定数据的构造函数
	info = inf;
	left = right = NULL;
}
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T& inf,BinaryTreeNode* l, BinaryTreeNode* r)  {//给定数据的左右指针的构造函数
	info = inf;
	left = l;
	right = r;
}
template<class T>
T  BinaryTreeNode<T>::value() const  {
	return info; 
}	
template<class T>
BinaryTreeNode<T>*  BinaryTreeNode<T>::leftchild() const  { //返回当前结点指向左子树的指针
	return left;
}												
template<class T>
BinaryTreeNode<T>*  BinaryTreeNode<T>::rightchild() const  { //返回当前结点指向右子树的指针
	return right;								
}			
template<class T>
void  BinaryTreeNode<T>::setLeftchild(BinaryTreeNode<T>* subroot)  { //设置当前结点的左子树
	left = subroot;
}
template<class T>
void  BinaryTreeNode<T>::setRightchild(BinaryTreeNode<T>* subroot)  { //设置当前结点的右子树
	right = subroot;
}
template<class T>
void  BinaryTreeNode<T>::setValue(const T& val)  {	//设置当前结点的数据域
	info = val; 
} 									
template<class T>
bool  BinaryTreeNode<T>::isLeaf() const	 {	//判定当前结点是否为叶结点,若是返回true
	return (left == NULL) && (right == NULL); 
}

BinaryTree.h

二叉树的ADT

template<class T>
class BinaryTree{
private:
	BinaryTreeNode<T>* root; // root 节点
public:
	BinaryTree(){root=NULL;}
	~BinaryTree(){DeleteBinaryTree(root);}
	bool isEmpty() const;
	BinaryTreeNode<T>* Root(){return root;}

	BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current);//返回current的父结点
	BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T>* current);//返回current结点的左兄弟
	BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T>* current);//返回current结点的右兄弟
	
	void CreateTree(const T& info, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree);//构造一棵以info为根、leftTree和rightTree为左右子树的新二叉树
	
	void PreOrder(BinaryTreeNode<T>* root);  	//前序周游二叉树或其子树
	void InOrder(BinaryTreeNode<T>* root);		//中序周游二叉树或其子树
	void PostOrder(BinaryTreeNode<T>* root);	//后序周游二叉树或其子树

	void PreOrderWithoutRecursion(BinaryTreeNode<T>* root);//非递归前序周游二叉树或其子树
	void InOrderWithoutRecursion(BinaryTreeNode<T>* root);//非递归中序周游二叉树或其子树
	void PostOrderWithoutRecursion(BinaryTreeNode<T>* root);//非递归后序周游二叉树或其子树
	void LevelOrder(BinaryTreeNode<T>* root); 	//按层次周游二叉树或其子树
	void DeleteBinaryTree(BinaryTreeNode<T>* root);	//删除二叉树或其子树
	void Visit(T Value) {cout << Value;};           //访问
};

BianryTree Implementation