二叉排序树

 

1.基本概念

二叉排序树，树的定义就不赘述了，主要就是想说明一下在设计类的过程中需要注意的问题。

a.问题引入？

设计插入，删除等操作的过程中，我们的二叉排序树根节点的指针有可能改变，如删除根结点的指针操作，那么root的指针指向已经不是原来的位置，而是新的位置，怎么样才能返回最新的位置呢？

 

b.问题解决

在设计类中的函数就可以轻易的解决这个问题，这个在函数设计之初就必须详细的考虑这个问题，这里有两种办法

 

首先，通过返回值，返回最新的root结点；

 

Node<T>* deleteBST(T x);
Node<T>* insertBST(T x);

 

 

这样在使用的过程中就需要这样使用：

 

BiSortTree<int> bst;
Node<int>* root = bst.getRoot();
...
bst.deleteBST(20);//这里假定20是根结点
bst.printBST(root);   //这里打印出来的肯定不是现在最新的二叉树，因为原来的root已经改变了
正确的使用方法是：
BiSortTree<int> bst;
Node<int>* root = bst.getRoot();
...
root = bst.deleteBST(20);//这里假定20是根结点
bst.printBST(root); 

 

 

 

其次，可以通过引用，设置函数的参数；

 

void deleteBST(Node<T>* &root, T x);
void insertBST(Node<T>* &root, T x);

 

 

这里利用了指针引用，这样会在删除，插入操作自动更新root

它的使用很简单，直接使用就是了

 

c.设计的缺陷

根据面向对象的原则，在上述设计中void deleteBST(Node<T>* &root, T x);它的设计是不合理的，因为root已经暴露在函数外面，为了实现其隐蔽的原则，就必须将root封装起来，不让使用者接触，那么怎样设计了？

class BiSortTree{

  public:

    ...

    void insertBST(T x){ insertBST(root, x);}

    void deleteBST(T x){ deleteBST(root, x);}

  private:

    ...

    void insertBST(Node<T>* &root, T x);

    void deleteBST(Node<T>* &root, T x);

    Node<T>* &root; //完成隐藏root

};

这样就实现了，隐蔽的原则，实现了面向对象的方法，使得使用者不用关心具体的实现，只是直接调用就ok了

 

2.代码实现

代码中就没有完全按照上述原则实现，所以需要自己改装

a.bisorttree.h

 

//二叉排序树
#ifndef BISORTTREE_H
#define BISORTTREE_H

//数据域，里面存放结点数据
template<class T>
struct Data{
	T data;			//结点数据
	int count;  //次数
	//int bf;   //平衡因子（对于AVL平衡二叉树是需要的）
};

template<class T>
struct Node{
	Data<T> data;
	Node<T> *rchild, *lchild;
};

/**
	*注意插入，删除都可能改变根结点，故而可能改变root指向的指针，就要注意设计函数的参数或者返回值
	*例如：void delete(T x);如果删除x是根结点，则删除后访问，就不能在找到root，访问内存出错
	*故而要想删除之后访问不出错，应该设计成
	*1.Node<T>* delete(T x);(利用返回值)返回最新根结点,使用方法Node<T>* root = delete(12); printBST(root); 注意不能这么用delete(12); printBST(root);root必须是返回最新的
	*2.void delete(Node<T>* &root, T x);(利用函数参数，这样不是很好，破坏封装性，可以设计成private，在加public函数void delete(T x))
	*  它的使用简单，直接就是delete(root, 12); printBST(root);
	*/
template<class T>
struct BiSortTree{
	public:
		BiSortTree();
		BiSortTree(T a[], int n);
		~BiSortTree();
		Node<T>* getRoot();

		//--------删除-------
		void deleteBST(Node<T>* &root, T x);	//设计方法1
		//返回根结点
		Node<T>* deleteBST(T x);			//设计方法2：当删除根结点之后，root改变，必须重新获取，如果写成void deleteBST(T x)则访问内存出错，root已经删除
	
		//--------插入-------
		//void insertBST(Node<T>* root, T x);		//递归插入,不使用引用是不行的
		void insertBST(Node<T>* &root, T x);		//root写成引用，这样root改变就会自动实现,上面就不行(下面也是一种写法)
		//返回根结点（在首次插入之后，其实root就不会改变）
		Node<T>* insertBST(T x);			//最好不写成void insertBST(T x)，这样每次必须手动调用getRoot，才能获取最新,返回的结点都是最新的root结点
		
		//--------搜索-------
		//返回搜索结点
		Node<T>* searchBST(T x);
		//返回搜索结点
		Node<T>* searchBST(Node<T>* root, T x);	//递归搜索
		void printBST(Node<T>* root);
	private:
		Node<T>* root;
		Node<T>* pre;//用于递归插入时，记录前序结点
		void releaseBST(Node<T>* &root);
		void create(Node<T>* &root);
		void deleteNode(Node<T>* &root, Node<T>* r, Node<T>* pre);//删除结点p
};
#endif

 

 b.bisorttree.cpp

 

#include <iostream>
#include "bisorttree.h"
using namespace std;

template<class T>
BiSortTree<T>::BiSortTree(){
	pre = NULL;
	root = NULL;
	create(root);
}

template<class T>
BiSortTree<T>::BiSortTree(T* a, int n){
	if(n <= 0) return;
	pre = NULL;
	root = NULL;
	for(int i=0; i<n; i++){
		insertBST(root, a[i]);
		//insertBST(a[i]);
	}
}

template<class T>
BiSortTree<T>::~BiSortTree(){
	releaseBST(root);
}


template<class T>
Node<T>* BiSortTree<T>::getRoot(){
	return root;	
}

//返回根结点
template<class T>
Node<T>* BiSortTree<T>::insertBST(T x){
	Node<T>* r = root;
	if(r == NULL){
		Node<T>* t = new Node<T>;
		(t->data).data = x;
		(t->data).count = 1;
		t->lchild = t->rchild = NULL;
		root = t;//必须设置新的root结点，因为t和root在内存指向位置不同
	}else{
		Node<T>* p = r;
		//查找待插入结点位置
		while(r){
			if((r->data).data == x){
				(r->data).count++;
				return root;
			}
			p = r;
			r = ((r->data).data > x)?r->lchild:r->rchild;
		}
		Node<T>* t = new Node<T>;
		(t->data).data = x;
		(t->data).count = 1;
		t->lchild = t->rchild = NULL;
		if((p->data).data > x){//插入左
			p->lchild = t;
		}else{
			p->rchild = t;
		}
	}
	return root;
}

//用于检测不用root引用是否会修改root,结果不使用root是不能改变root，必须是指针的引用
template<class T>
void BiSortTree<T>::insertBST(Node<T>* &root, T x){
	if(root){
		pre = root;
		if((root->data).data > x) insertBST(root->lchild, x);
		else if((root->data).data < x) insertBST(root->rchild, x);
		else (root->data).count++;
	}else{ 
		Node<T>* r = new Node<T>;
		(r->data).data = x;
		(r->data).count = 1;
		r->lchild = r->rchild = NULL;
		if(pre){
			if((pre->data).data > x) pre->lchild = r;
			else pre->rchild = r;
		}else{
			root = r;
		}
	}
}

template<class T>
void BiSortTree<T>::deleteBST(Node<T>* &root, T x){
	if(!root) return;
	Node<T>* pre = NULL, *r = root;
	//查找待插入结点位置(p是r的前序结点)
	while(r){
			if((r->data).data == x){
				if((r->data).count > 1){ 
					(r->data).count--; return;
				}else{
					break;
				}
			}
				
			pre = r;
			r = ((r->data).data > x)?r->lchild:r->rchild;
	}
	//没找到
	if(!r) return;
	//如果pre == NULL说明是root结点
	deleteNode(root, r, pre);
}


template<class T>
Node<T>* BiSortTree<T>::deleteBST(T x){
	if(!root) return root;
	Node<T>* pre = NULL, *r = root;
	//查找待删除结点位置(pre是r的前序结点)
	while(r){
			if((r->data).data == x){
				if((r->data).count > 1){ 
					(r->data).count--; return root;
				}else{
					break;
				}
			}
				
			pre = r;
			r = ((r->data).data > x)?r->lchild:r->rchild;
	}
	//没找到
	if(!r) return root;
	//如果pre == NULL说明是root结点
	deleteNode(root, r, pre);
	return root;
}


template<class T>
Node<T>* BiSortTree<T>::searchBST(T x){
	Node<T>* r = root;
	while(r){
		if(r->data.data == x) break;
		r = ((r->data).data > x)?r->lchild:r->rchild;
	}
	//如果没找到，返回空
	return r;
}

template<class T>
Node<T>* BiSortTree<T>::searchBST(Node<T>* root, T x){
	if(!root) return NULL;
	else{
		if(root->data.data == x) return root;
		else if(root->data.data > x) return searchBST(root->lchild, x);
		else return searchBST(root->rchild, x);
	}
}

template<class T>
void BiSortTree<T>::printBST(Node<T>* root){
	if(root){
		cout<<root->data.data<<" ";
		printBST(root->lchild);
		printBST(root->rchild);
	}
}

template<class T>
void BiSortTree<T>::releaseBST(Node<T>* &root){
	if(root){
		releaseBST(root->lchild);
		releaseBST(root->rchild);
		delete root;
	}
}
	
template<class T>
void BiSortTree<T>::create(Node<T>* &root){
	T ch;
	cout<<"请输入创建一棵二叉排序树的结点数据(输入#结束)："<<endl;
	while(cin>>ch){
		if(ch == '#') break;
		//insertBST(root, ch);
		insertBST(ch);
	}
}
	

//pre为空，说明删除的是根结点
template<class T>
void BiSortTree<T>::deleteNode(Node<T>* &root, Node<T>* r, Node<T>* pre){
	Node<T>* p;
	if(!r->rchild && !r->lchild){			//如果是叶子结点
		if(pre){
			if(pre->lchild == r){
				pre->lchild = NULL;
			}else{
				pre->rchild = NULL;
			}
		}else{
			root = NULL;
		}
		delete r;
	}else if(r->rchild && r->lchild){			//如果左右子树都有(还有一种处理办法就是用右子树的最左结点替换待删除结点，然后删除最左结点)
		p = r;
		//寻找右子树的最左结点
		r = r->rchild;
		while(r->lchild){
		 r = r->lchild;
		}
		//将删除结点的左结点接到找到的最左结点之后
		r->lchild = p->lchild;
		//删除结点(如果pre是空，说明删除结点是根结点,不用改变前序结点指针)
		if(pre){
			if(pre->lchild == p) pre->lchild = p->rchild;
			else pre->rchild = p->rchild;
		}else{
			root = p->rchild;
		}
		delete p;
	}else if(r->lchild){			//如果只有左子树
		p = r;
		if(pre){
			if(pre->lchild == p) pre->lchild = r->lchild;
			else pre->rchild = r->lchild;
		}else{
			root = r->lchild;
		}
		delete p;
	}else{					//如果只有右子树
		p = r;
		if(pre){
			if(pre->lchild == p) pre->lchild = r->rchild;
			else pre->rchild = r->rchild;
		}else{
			root = r->rchild;
		}
		delete p;
	}
}

 

 c.main.cpp

 

#include <iostream>
#include "bisorttree.cpp"
using namespace std;

int main(){
	cout<<"----------二叉排序树测试----------"<<endl;
	BiSortTree<int> bst;
	Node<int>* root = bst.getRoot();
	
	bst.printBST(root);
	cout<<"\n插入23"<<endl;
	bst.insertBST(23);
	//root = bst.insertBST(23);
	//bst.insertBST(24);
	root = bst.insertBST(24);//如果初始的root为空，则必须这样使用，因为root已经改变，如果上面那样用，就算插入了还是空的;当然如果已经不是空了，则root就没改变，可以输出，注：只有root改变就必须返回新的root
	bst.printBST(root);
	
	/*
	int a[] = {60, 40, 65, 30, 45, 70, 68, 20, 43};
	BiSortTree<int> bst(a, 9);
	Node<int>* root = bst.getRoot();
	if(root == NULL){
		 cout<<"---null---"<<endl;
	}
	cout<<"----------遍历结果------------"<<endl;
	bst.printBST(root);
	cout<<"\n插入23"<<endl;
	bst.insertBST(23);
	bst.printBST(root);
	
	Node<int> *p;
	cout<<"\n搜索23"<<endl;
	p = bst.searchBST(root,23);
	if(p) cout<<"搜索结果："<<p->data.data<<",count:"<<p->data.count<<endl;
	else cout<<"无"<<endl;
	
	cout<<"删除叶子23"<<endl;
	bst.deleteBST(root, 23);
	bst.printBST(root);
	
	//测试构造函数和几种删除，一个root
	cout<<"\n删除叶子结点20"<<endl;
	bst.deleteBST(root, 20);
	bst.printBST(root);
	
	cout<<"\n删除根结点60"<<endl;
	//bst.deleteBST(root, 60); //1.方案1
	root = bst.deleteBST(60);  //2.方案2，	不获取返回值bst.deleteBST(60);是不正确的使用方法
	bst.printBST(root);
	*/
	return 0;
}