BinaryTree

此前写过的数据结构，无论是向量亦或链表，元素之间均存在一个线性次序，故他们都是线性结构(linear structure)。树作为图的一种，同时具有无环性与连通性，只要附加某种约束（例如遍历），即可在树的节点中确定某种线性次序，因此树也被称作半线性结构(semi-linear structure)。

二叉树是树的一种，在树的全体中仅占很小一部分。但是任意一棵树或一座森林都可以转化成一棵二叉树，具体方法是将第一个后代作为左孩子，兄弟作为右孩子，后代的兄弟作为后代的右孩子……直至所有节点完全调整完毕。
以下给出二叉树模板类的定义与接口实现：

---

BinaryNode模板类

#define stature(p) ((p)?(p)->height : -1)  //统一约定节点高度

template <typename T> struct BinNode
{
	T data;
	BinNode<T>* parent;
	BinNode<T>* lc;  //左孩子 
	BinNode<T>* rc;  //右孩子
	int height;
	//构造函数
	BinNode() : 
		parent(NULL), lc(NULL), rc(NULL), height(0) {}
	BinNode( T e, BinNode<T>* p=NULL, BinNode<T>* LC=NULL, BinNode<T>* RC=NULL, int h=0) :
		data(e), parent(p), lc(LC), rc(RC), height(h) {}
	//接口
	int size()  //统计以当前节点为根的子树规模，即该节点后代总数
	BinNode<T>* insertAsLC(T const& e)
	{
		return lc=new BinNode(e,this);
	}
	BinNode<T>* insertAsRC(T const& e)
	{
		return rc=new BinNode(e,this);
	}
	BinNode<T>* succ()  //获取当前节点直接后继(BST) 
	{
		BinNode<T>* s=this;
		if(rc)  //若有右孩子，则直接后继在右子树中 
		{
			s=rc;
			while(s->lc) s=s->lc;
		}
		else  //否则，直接后继为将该节点包含于其左子树的最低祖先 
		{
			while(s->isRChild()) s=s->parent;
			s=s->parent;
		}
		return s;
	}
	template <typename VST> void travLevel(VST&);  //子树层次遍历
	template <typename VST> void travPre(VST&);  //子树先序(preorder)遍历
	template <typename VST> void travIn(VST&);  //子树中序(inorder)遍历
	template <typename VST> void travPost(VST&);  //子树后序(postorder)遍历
	//比较器、判等器
	bool operator < (BinNode const& bn) {return data<bn.data;}
	bool operator == (BinNode const& bn) {return data==bn.data;}
	//状态与性质
	bool isRoot(){return !parent;}
	bool isLChild(){return !isRoot()&&(this==parent.lc);} 
	bool isRChild(){return !isRoot()&&(this==parent.rc);}
	bool hasChild(){return lc||rc;}
	bool hasBothChild(){return lc&&rc;}
	bool isLeaf(){return !hasChild();}
 }; 

---

BinaryTree模板类

#include "BinNode.h"

template<typename T>
class BinTree
{
	protected:
		int _size;
		BinNode<T>* _root;
		virtual int updateHeight(BinNode<T>* x);  //更新节点高度
		void updateHeightAbove(BinNode<T>* x);  //更新节点祖先及高度
	public:
		BinTree() : _size(0), _root(NULL) {}  //构造函数
		~BinTree(){if(0<_size) remove _root;}  //析构函数
		int size() const {return _size;}
		bool empty() const {return !_root;}
		BinNode<T>* root() const {return _root;}
		BinNode<T>* insertAsRoot (T const& e);
		BinNode<T>* insertAsLC (BinNode<T>* x, T const& e);
		BinNode<T>* insertAsRC (BinNode<T>* x, T const& e);
		BinNode<T>* attachAsLC (BinNode<T>* x, Bintree<T>* &T);
		BinNode<T>* attachAsRC (BinNode<T>* x, Bintree<T>* &T);
		int remove(BinNode<T>* x);  //删除以x为根的子树，返回规模
		BinNode<T>* secede (BinNode<T>* x);  //将子树x分离
		//操作器 
		template <typename VST>
		void travLevel(VST& visit) {if(_root) _root->travLevel(visit);} 
		template <typename VST>
		void travPre(VST& visit) {if(_root) _root->travPre(visit);}
		template <typename VST>
		void travIn(VST& visit) {if(_root) _root->travIn(visit);}
		template <typename VST>
		void travPost(VST& visit) {if(_root) _root->travPost(visit);}
		//比较器
		bool operator < (BinTree<T> const& t);
		bool operator == (BinTree<T> const& t);
		
};

---

高度更新

template <typename T>
int BInTree<T>::updateHeight(BinNode<T>* x)
{
	return x->height = 1+ max((x->lc? x->lc->height : -1), (x->rc? x->rc->height : -1));	
} 
template<typename T>
void BinTree<T>::updateHeightAbove(BinNode<T>* x)
{
	while (x)
	{
		updateHeight(x);
		x=x->parent; 
	} 
}

---

节点插入

template <typename T>
BinNode<T>* BinTree::insertAsRoot(T const& e)  //将e当作根节点插入空的二叉树 
{
	_size=1;
	return _root = new BinNode<T> (e);
}
template <typename T>
BinNode<T>* BinTree::insertAsLC(BinNode<T>* x, T const& e)
{
	_size++;
	x->insertAsLC(e);
	updateHeightAbove(x);
	return x->lc;
}
template <typename T>
BinNode<T>* BinTree::insertAsRC(BinNode<T>* x, T const& e)
{
	_size++;
	x->insertAsRC(e);
	updateHeightAbove(x);
	return x->rc;
}

---

子树接入

template<typename T>
BinNode<T>* BinTree::attachAsLC(BinNode<T>* x, BinTree<T>* S)
{
	if(x->lc=S->_root) x->lc->parent = x;
	_size+=S->size();
	updateHeightAbove (x);
	remove(S->root());
	return x;	
}
template<typename T>
BinNode<T>* BinTree::attachAsRC(BinNode<T>* x, BinTree<T>* S)
{
	if(x->rc=S->_root) x->rc->parent = x;
	_size+=S->size();
	updateHeightAbove (x);
	remove(S->root());
	return x;	
}

---

子树删除

template <typename T>
int BinTree<T>::remove (BinNode<T>* x)
{
	if(x->parent)  //切断来自父节点的指针 
		x->parent->lc==x? 
		x->parent->lc=NULL : x->parent->rc=NULL;
	updateHeightAbove(x->parent);
	int n=removeAt(x);
	_size-=n;
	return n;
}
template <typename T>
static int removeAt(BinNode<T>* x)
{
	if(!x) return 0;
	int n=1+removeAt(x->lc)+removeAt(x->rc);
	delete (x);
	return n;
}

---

子树分离