数据结构学习----二叉树

#include "Common.h"
#include "DCirList.h"
#pragma once
#pragma region
//二叉树类
//测试日期 2010-3-13
#ifndef BINTREENODE_H
#define BINTREENODE_H
template<class T>
class BinTreeNode
{
public:
    BinTreeNode<T>* leftchild;
	BinTreeNode<T>* rightchild;
	T data;

    BinTreeNode(){leftchild=rightchild=NULL;}                            //默认构造函数
	BinTreeNode(T item,BinTreeNode<T>* pl=NULL,BinTreeNode<T>* pr=NULL)  //重载构造函数
	{data=item;leftchild=pl;rightchild=pr;}      
};
#endif 

#ifndef BINTREE_H
#define BINTREE_H
template<class T>
void _visit(BinTreeNode<T>* x){}
template<class T>
class BinTree
{
protected:
	BinTreeNode<T>* root;                                                //二叉树根结点指针
	BinTreeNode<T>* current;                                             //二叉树当前结点指针
	DCirList<BinTreeNode<T>*> L;                                         //遍历链表
	//[3个函数]
    BinTreeNode<T>* Copy(BinTreeNode<T>* t);                             //复制二叉树
    BinTreeNode<T>* CreateBinTree(T *VLR,T *LVR,int n);                  //由VLR,LVR序列创建二叉树 
	BinTreeNode<T>* SearchParent(BinTreeNode<T>* t,BinTreeNode<T>* s);   //在二叉树t中回溯查找s的父结点
public:
	BinTree(){root=current=NULL;}                                        //构造函数
	~BinTree(){ClearTree();}                                             //析构函数
	void ClearList(){L.ClearList();}                                     //清空遍历表
    
	//[4个函数]
	BinTree<T>& CreateBinTree(DCirList<T> vlr, DCirList<T> lvr);         //由VLR,LVR序列创建二叉树
	void ClearTree(){DeleteSubTree(root);}                               //清空二叉树
	int TreeSize(BinTreeNode<T>* t);                                     //返回以t为根结点的二叉树的结点个数
	int TreeSize(){return TreeSize(root);}                               //二叉树的结点数

	//获取结点指针[6个函数]
	BinTreeNode<T>* GetRoot(){return root;}                              //返回根结点指针
	BinTreeNode<T>* GetCurrent(){return current;}                        //返回当前结点指针
	BinTreeNode<T>* GetParent(){return SearchParent(root,current);}      //返回当前结点的父结点指针
	BinTreeNode<T>* GetLeftChild();                                      //返回当前结点的左孩子结点指针
	BinTreeNode<T>* GetRightChild();                                     //返回当前结点的右孩子结点指针
	BinTreeNode<T>* GetSibling();                                        //返回当前结点的兄弟结点指针
	

	//四种遍历[8个函数]
	void PreOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x));   //前序遍历以t为根结点的数据域
	DCirList<BinTreeNode<T>*> GetPreList(BinTreeNode<T>* t);
	void InOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x));    //中序遍历以t为根结点的数据域
	DCirList<BinTreeNode<T>*> GetInList(BinTreeNode<T>* t);
	void PosOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x));   //后序遍历以t为根结点的数据域
	DCirList<BinTreeNode<T>*> GetPosList(BinTreeNode<T>* t);
	void LevelOrderTree(BinTreeNode<T>* t,void(*visit)(BinTreeNode<T>* x)); //层序遍历以t为根结点的数据域
	DCirList<BinTreeNode<T>*> GetLevelList(BinTreeNode<T>* t);

	//设置当前结点并返回当前结点指针[7个函数]
	BinTreeNode<T>* SetRoot(){return current=root;}                      //把根结点设置为当前结点
	BinTreeNode<T>* SetCurrent(BinTreeNode<T>* t){return current=t;}     //把t所指向的结点设置为当前结点
	BinTreeNode<T>* SetCurrent(char* p);                                 //设置当前节点,如p='lrlrlr';l代表左,r代表右
	BinTreeNode<T>* SetParent(){return current=GetParent();}             //把当前结点的父结点设置为当前结点
	BinTreeNode<T>* SetLeftChild(){return current=GetLeftChild();}       //把当前结点的左孩子结点设置为当前结点
	BinTreeNode<T>* SetRightChild(){return current=GetRightChild();}     //把当前结点的右孩子结点设置为当前结点
	BinTreeNode<T>* SetSibling(){return current=GetSibling();}           //把当前结点的兄弟结点设置为当前结点
	
	//插入删除操作[7个函数]
	void InsertLeftChild(T x);                                           //把x插入为当前结点的左孩子结点
	void InsertRightChild(T x);                                          //把x插入为当前结点的右孩子结点
	void InsertLeftTree(BinTree<T> &tree);                               //把tree插入为当前结点的左孩子树[原孩子树被替换]
	void InsertRightTree(BinTree<T> &tree);                              //把tree插入为当前结点的右孩子树[原孩子树被替换]
	void DeleteLeftChild();                                              //删除当前结点的左孩子结点
	void DeleteRightChild();                                             //删除当前结点的右孩子结点
	void DeleteSubTree(BinTreeNode<T>* &t);                              //删除以t为根结点的子树 

    //其他4个函数
	bool IsLeaf();                                                       //判断当前结点是否为叶子结点
	int Depth(BinTreeNode<T>* t);                                        //返回以t为根结点的二叉树的深度
	int LeafCount(BinTreeNode<T>* t);                                    //返回以t为根节点的二叉树的叶子的个数
    BinTree<T>& operator=(BinTree<T>& t);
};
#endif


template<class T>
BinTreeNode<T>* BinTree<T>::Copy(BinTreeNode<T> *t)
{
	if(t==NULL)
		return NULL;
	BinTreeNode<T>* p=new BinTreeNode<T>;
	p->data=t->data;
	if(t->leftchild!=NULL)
	  p->leftchild=Copy(t->leftchild);
	if(t->rightchild!=NULL)
	  p->rightchild=Copy(t->rightchild);
	return p;
}


template<class T>
BinTreeNode<T>* BinTree<T>::CreateBinTree(T *VLR, T *LVR, int n)
{
	if(n==0)
		return NULL;
	int k=0;
	while(k<n&&VLR[0]!=LVR[k])
		k++;
	BinTreeNode<T> *t=new BinTreeNode<T>(VLR[0]);
	t->leftchild=CreateBinTree(VLR+1,LVR,k);
	t->rightchild=CreateBinTree(VLR+k+1,LVR+k+1,n-k-1);
	return t;
}

template<class T>
BinTreeNode<T>* BinTree<T>::SearchParent(BinTreeNode<T> *t, BinTreeNode<T> *s)
{
	if(t==NULL||s==NULL||s==root)
		return NULL;
	if(t->leftchild==s||t->rightchild==s)
		return t;
	BinTreeNode<T> *p;
	if((p=SearchParent(t->leftchild,s))!=NULL)
		return p;
	if((p=SearchParent(t->rightchild,s))!=NULL)
		return p;
}

template<class T>
BinTree<T>& BinTree<T>::CreateBinTree(DCirList<T> vlr, DCirList<T> lvr)
{
	int n=vlr.Size();
	if(n!=lvr.Size()){root=NULL;return *this;}
	T* VLR=new T[n];
	T* LVR=new T[n];
	for(int i=0;i<n;i++)
	{
		VLR[i]=vlr.GetData(i);
		LVR[i]=lvr.GetData(i);
	}
	current=root=CreateBinTree(VLR,LVR,n);
	delete VLR;
	delete LVR;
	return *this;
}

template<class T>
int BinTree<T>::TreeSize(BinTreeNode<T>* t)
{
	if(t==NULL)
		return 0;
	else
		return 1+TreeSize(t->leftchild)+TreeSize(t->rightchild);
}
template<class T>
BinTreeNode<T>* BinTree<T>::GetLeftChild()
{
	return current==NULL?NULL:current->leftchild;
}
template<class T>
BinTreeNode<T>* BinTree<T>::GetRightChild()
{
	return current==NULL?NULL:current->rightchild; 
}
template<class T>
BinTreeNode<T>* BinTree<T>::GetSibling()
{
	if(current=root||current==NULL)
		return NULL;
	BinTreeNode<T> *p;
	p=GetParent();
	if(p1->leftchild==current)
		return p->rightchild;
	else
		return p->leftchild;
}
template<class T>
void BinTree<T>::PreOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
	if(t==NULL)
		return;
	visit(t); L.PushBack(t);
	if(t->leftchild!=NULL)
		PreOrderTree(t->leftchild,visit);
	if(t->rightchild!=NULL)
		PreOrderTree(t->rightchild,visit);
}
template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetPreList(BinTreeNode<T> *t)
{
   ClearList();
   PreOrderTree(t,_visit);
   return L;
}
template<class T>
void BinTree<T>::InOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
	if(t==NULL)
		return;
	if(t->leftchild!=NULL)
		InOrderTree(t->leftchild,visit);
	visit(t); L.PushBack(t);
	if(t->rightchild!=NULL)
		InOrderTree(t->rightchild,visit);
}
template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetInList(BinTreeNode<T> *t)
{
	ClearList();
	InOrderTree(t,_visit);
	return L;
}
template<class T>
void BinTree<T>::PosOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
	if(t==NULL)
		return;
	if(t->leftchild!=NULL)
		PosOrderTree(t->leftchild,visit);
	if(t->rightchild!=NULL)
		PosOrderTree(t->rightchild,visit);
	visit(t);  L.PushBack(t);
}

template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetPosList(BinTreeNode<T> *t)
{
	ClearList();
	PosOrderTree(t,_visit);
	return L;
}

template<class T>
void BinTree<T>::LevelOrderTree(BinTreeNode<T> *t, void (*visit)(BinTreeNode<T>* x))
{
	if(t==NULL)
		return;
	DCirList<BinTreeNode<T>* >q;
	BinTreeNode<T> *p;  
	q.PushBack(t); 
	while(!q.IsEmpty())
	{
		p=q.PopFront();                                               
		visit(p); L.PushBack(p);
		if(p->leftchild!=NULL)  q.EnterQueue(p->leftchild);           
		if(p->rightchild!=NULL)  q.EnterQueue(p->rightchild);             
	}
}

template<class T>
DCirList<BinTreeNode<T>*> BinTree<T>::GetLevelList(BinTreeNode<T> *t)
{
	ClearList();
	LevelOrderTree(t,_visit);
	return L;
}
 

template<class T>
BinTreeNode<T>* BinTree<T>::SetCurrent(char *p)
{
    current=root;
	int n=strlen(p);
    for(int i=0;i<n;i++)
	{
		if(p[i]=='l')
           SetLeftChild();
		if(p[i]=='r')
		   SetRightChild();
	}
	return current;
}
template<class T>
void BinTree<T>::InsertLeftChild(T x)
{
	BinTreeNode<T> *newnode=new BinTreeNode<T>(x);
	if(root==NULL){root=current=newnode;return;}
	if(current==NULL)return;
	newnode->leftchild=current->leftchild;
	current->leftchild=newnode;
}
template<class T>
void BinTree<T>::InsertRightChild(T x)
{
	BinTreeNode<T> *newnode=new BinTreeNode<T>(x);
	if(root==NULL){root=current=newnode;return;}
	if(current==NULL)return;
	newnode->rightchild=current->rightchild;
	current->rightchild=newnode;
}
template<class T>
void BinTree<T>::InsertLeftTree(BinTree<T> &tree)
{
	BinTreeNode<T>* p=Copy(tree.root);
	DeleteLeftChild();
	current->leftchild=p;
}
template<class T>
void BinTree<T>::InsertRightTree(BinTree<T> &tree)
{
	BinTreeNode<T>* p=Copy(tree.root);
	DeleteRightChild();
	current->rightchild=p;
}
template<class T>
void BinTree<T>::DeleteLeftChild()
{
	DeleteSubTree(current->leftchild);
}
template<class T>
void BinTree<T>::DeleteRightChild()
{
	DeleteSubTree(current->rightchild);
}
template<class T>
void BinTree<T>::DeleteSubTree(BinTreeNode<T> *&t)
{
	if(t==NULL) return;
	if(t->leftchild!=NULL)
		DeleteSubTree(t->leftchild);
	if(t->rightchild!=NULL)
		DeleteSubTree(t->rightchild);
	BinTreeNode<T> *p=SearchParent(root,t);
	if(p!=NULL)
	{
		if(p->leftchild==t)
			p->leftchild=NULL;
		if(p->rightchild==t)
			p->rightchild=NULL;
	}
	delete t;
	t=NULL;
}
template<class T>
bool BinTree<T>::IsLeaf()
{
	if(current==NULL)
		return false;
	return (current->leftchild==NULL&&current->rightchild==NULL);
}
template<class T>
int BinTree<T>::Depth(BinTreeNode<T>* t)
{
	if(t==NULL)
		return 0;
	int ldep=Depth(t->leftchild);
	int rdep=Depth(t->rightchild);
	return ldep>rdep?ldep+1:rdep+1;
}
template<class T>
int BinTree<T>::LeafCount(BinTreeNode<T>* t)
{
	int count=0;
	if(t!=NULL) 
	{
		count+=CountLeaf(t->leftchild);
		count+=CountLeaf(t->rightchild);
		if(t->leftchild==NULL&&t->rightchild==NULL)
			count++;
	}
	return count;
}
template<class T>
BinTree<T>& BinTree<T>::operator =(BinTree<T> &t)
{
	current=root=Copy(t.root);
	return *this;
}