exp14_1.cpp

一个C++的中序遍历程序

#include<iostream.h>
#include<stdlib.h>

template<typename T>class BinaryTree;
template<typename T>class Node{
	Node<T> *lchild,*rchild;
	T info;
public:
	Node(){lchild=NULL;rchild=NULL;}
	Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
		info=data;
		lchild=left;
		rchild=right;
	}
	friend class BinaryTree<T>;
};
template<typename T>class BinaryTree{
	Node<T> *root;                  //二叉树的根指针
	void InOrder(Node<T> *Current);                //中序遍历
	void Insert(const T &data,Node<T> * &b); //插入结点，第二参数为引用！
	void Remove(const T &data,Node<T> * &a,Node<T> * &b);//删除结点
	void Destory(Node<T> * Current);         //删除树
public:
	BinaryTree(){root=NULL;}						//空树构造函数
	~BinaryTree(){Destory(root);}						//析构函数
	void Creat(T* data,int n);                    //建立（排序）二叉树
	void InOrder(){InOrder(root);}                //中序遍历，公有函数为接口
	void Remove(const T &data){Remove(data,root,root);}//删除结点
};
template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
	if(Current!=NULL){
		Destory(Current->lchild);
		Destory(Current->rchild);
		delete Current;  						//后序释放根结点
	}
}
template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
	if(b==NULL){								//已到空树,插入
		b=new Node<T>(data);
		if(b==NULL){
			cout<<"空间不足"<<endl;
			exit(1);
		}
	}
	else if(data<b->info) Insert(data,b->lchild);			//小于,向左子树去查
	     else Insert(data,b->rchild);	//大于等于,向右子树去查
}
template<typename T>void BinaryTree<T>::Creat(T* data,int n){		//建立一棵二叉排序树
	for(int i=0;i<n;i++) Insert(data[i],root);
}
template<typename T>void BinaryTree<T>::InOrder(Node<T> *Current){
	if(Current!=NULL){							//递归终止条件
		InOrder(Current->lchild);					//中序遍历左子树
		cout<<Current->info<<'\t';					//访问根结点，注意所放位置
		InOrder(Current->rchild);					//中序遍历右子树
	}
}
template<typename T>void BinaryTree<T>::Remove(const T &data,Node<T> * &a,Node<T> * &b){
	Node<T> *temp1,*temp2;
	if(b!=NULL)
		if(data<b->info) Remove(data,b,b->lchild);	//所查数小，去左子树
		else if(data>b->info) Remove(data,b,b->rchild);//所查数大，去右子树
		     else if (b->lchild!=NULL&&b->rchild!=NULL){
				 //查到值为data的结点,它有两个孩子
				 temp2=b;
				 temp1=b->rchild;		//向右一步
				 if(temp1->lchild!=NULL){
					 while(temp1->lchild!=NULL){
						 //向左到极左的结点，将要用来取代被删结点
						 temp2=temp1;
						 temp1=temp1->lchild;
					 }					
					 temp2->lchild=temp1->rchild;
					 //将取选中结点的右子树或NULL，接到该结点的父结点的左子树上
				 }
				 else temp2->rchild=temp1->rchild;//向右一步后无左子树
				 b->info=temp1->info;
				 delete temp1;
			 }
			 else{							// 只有一个孩子或是叶结点
				 temp1=b;
				 if(b->rchild!=NULL){	//只有右孩子
					 temp1=b->rchild;
					 b->info=temp1->info;
					 b->rchild=temp1->rchild;
					 b->lchild=temp1->lchild;
				 }
				 else if(b->lchild!=NULL){	//只有左孩子
					 temp1=b->lchild;
					 b->info=temp1->info;
					 b->rchild=temp1->rchild;
					 b->lchild=temp1->lchild;
				 }
				 else if(b==root) root=NULL;//叶结点，仅有根结点
				      else if(a->rchild==temp1) a->rchild=NULL;//被删结点在父结点右
				           else a->lchild=NULL;//被删结点在父结点左
				 delete temp1;
			 }
}

void main(){
	const int n=15;
	int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
	BinaryTree<int> btree;
	btree.Creat(a,n);
	cout<<"输入数据："<<endl;
	for(i=0;i<n;i++) cout<<a[i]<<'\t';
	cout<<endl<<"中序："<<endl;
	btree.InOrder();    //中序遍历输出升序
	btree.Remove(a[13]);//删叶结点
	cout<<endl<<"中序："<<endl;
	btree.InOrder();    //中序遍历输出升序
	btree.Remove(a[3]);//删单孩子结点
	cout<<endl<<"中序："<<endl;
	btree.InOrder();    //中序遍历输出升序
	btree.Remove(a[9]);//删叶结点
	cout<<endl<<"中序："<<endl;
	btree.InOrder();    //中序遍历输出升序
	btree.Remove(a[2]);//被删结点的右子树根结点无左子树
	cout<<endl<<"中序："<<endl;
	btree.InOrder();    //中序遍历输出升序
	btree.Remove(a[0]);//删根结点
	cout<<endl<<"中序："<<endl;
	btree.InOrder();    //中序遍历输出升序
	int a1[1]={10};//仅有根结点
	BinaryTree<int> btree1;
	btree1.Creat(a1,1);
	cout<<"输入数据："<<'\t'<<a1[0]<<'\t';
	cout<<endl<<"中序："<<'\t';
	btree1.InOrder();    //中序遍历输出升序
	btree1.Remove(a[0]);//删叶结点
	cout<<endl<<"中序："<<endl;
	btree1.InOrder();    //中序遍历输出升序
}