binarysorttree.h

二叉排序树 算法 数据结构 希望对初学者有所帮助 c++源程序

#pragma once
#include"BinaryTreeNode.h"

template<typename elemType>
class BinarySortTree
{
private:
   BinarySortNode<elemType> *root;
public:
	BinarySortTree();
	void insert(const elemType &val);
	void show()const;
   
private:
	void _insert(BinarySortNode<elemType> *&root,const elemType &val);
	void _inorder(BinarySortNode<elemType> *p)const;
	BinarySortNode<elemType>*_insertl(BinarySortNode<elemType> *t,BinarySortNode<elemType> *s);
	BinarySortNode<elemType> *_insertz(BinarySortNode<elemType> *t,BinarySortNode<elemType> *s);
};

template<typename elemType>
BinarySortTree<elemType>::BinarySortTree()
{
	root=NULL;
}
template<typename elemType>
void BinarySortTree<elemType>::insert(const elemType & val)
{
	_insert(root,val);
}

template<typename elemType>
void BinarySortTree<elemType>::_insert(BinarySortNode<elemType> *&root,const elemType &val)
{
	if(!root)
		root=new BinarySortNode<elemType>(val);
	else
	{
		if(val<root->data)
		{
			if(!root->lch)
				root->lch=new BinarySortNode<elemType>(val);
			else
				_insert(root->lch,val);
		}
		else
		{
			if(!root->rch)
				root->rch=new BinarySortNode<elemType>(val);
			else
		       _insert(root->rch,val);
		}
	}
}

template<typename elemType>
void BinarySortTree<elemType>::show()const
{
	if(!root)
		return ;
	_inorder(root);
	cout<<endl;
}

template<typename elemType>
void BinarySortTree<elemType>::_inorder(BinarySortNode<elemType> *p)const
{
	if(!p)
		return ;
	_inorder(p->lch);
	cout<<p->data<<' ';
	_inorder(p->rch);
}


template<typename elemType>
BinarySortNode<elemType> *BinarySortTree<elemType>::_insertl(BinarySortNode<elemType> *t,BinarySortNode<elemType> *s)
{
	if(!t)
		t=s;
	else
	{
		if(s->data<t->data)
			t=_insertl(t->lch,s);
		else
			t=_insertl(t->rch,s);
	}
	return t;
}



template<typename elemType>
BinarySortNode<elemType> *BinarySortTree<elemType>::_insertz(BinarySortNode<elemType> *t,BinarySortNode<elemType> *s)
{
	if(!t)
		t=s;
	else
	{
	    BinarySortNode<elemType> *p,*q;
		p=q=t;
		while(p)
		{
			q=p;
			if(s->data<p->data)
				p=p->lch;
			else
				p=p->rch;
		}
		if(s->data<q->data)
			q->lch=s;
		else
			q->rch=s;
	}
	return t;
}