binarysearchtree.h

二叉树

//实现二叉搜索树的类定义、插入、删除、查找操作

# ifndef BINARY_SEARCH_TREE
# define BINARY_SEARCH_TREE

#include<iostream.h>
#include<math.h>
#include"Queue.h"

template<class T>
class BSTNode {             // 一般搜索二叉树的节点定义
public:
    BSTNode() { 
        left = right = 0; 
    }
    BSTNode(const T& el, BSTNode<T> *l = 0, BSTNode<T> *r = 0) {
        key = el; left = l; right = r; 
    }
    T key;
    BSTNode<T> *left, *right;
};
//--------------------------------------------------------------------
template<class T>
class BinarySearchTree  {     //一般二叉搜索树的类定义，后面为了简单，写作BST代替BinarySearchTree
public:
    BinarySearchTree()
	{
		root=0;
	}
	BinarySearchTree(BSTNode<T>* r)
	{
		root=r;
	}
	void setRoot(BSTNode<T>* r)  {root=r;}
    BSTNode<T>* getRoot() const  { return root;}
	int countHeight(BSTNode<T> *t);                   //计算高度
	void makeBST();
    void insertBSTNode(T k);
	bool findBSTNode(T k);
	void findAndDelete(T k);
	void deleteByMerging(BSTNode<T>*& node);
    void deleteByCopying(BSTNode<T>*& node);
	bool isTreeBalanced(BSTNode<T>* r);
	bool isTreeCompletelyBalanced(BSTNode<T>* r,int& i);
	bool isTreePerfect();
	void balance(T data[],int first,int last);
	
    void preOrder(BSTNode<T>* r);
	void inOrder(BSTNode<T>* r);
	void postOrder(BSTNode<T>* r);


	/*BSTNode<T>* makeBinaryTree(BSTNode<T>* r);
	BSTNode<T>* makeBinaryTree(BSTNode<T>* r,T el);
	void makeBinaryTree(const T& el,BinaryTree<T>& left,BinaryTree<T>& right);
	void preOrder(BSTNode<T>* r);
	void iterativePreOrder();
	void inOrder(BSTNode<T>* r);
	void iterativeInOrder();
	void postOrder(BSTNode<T>* r);
	void iterativePostOrder();
	BSTNode<T> * PreInToTree(BSTNode<T> *root,TNode<T>* ph,TNode<T>* ih);
	BSTNode<T> * InPostToTree(BSTNode<T> *r,TNode<T>* ih,TNode<T>* poh);*/

	//int countAllNode(BSTNode<T>* r);
    //int countLeafNode(BSTNode<T>* r);
	//int countRightNode(BSTNode<T>* r);
	//void deleteLeafNode(BSTNode<T>* r);
private:
	BSTNode<T>* root;
};


template <class T>
int BinarySearchTree<T>::countHeight(BSTNode<T> *t) //返回树*t的高度
{
	if(!t) return 0;
	int hl=countHeight(t->left);
	int hr=countHeight(t->right);
	if(hl>hr) return ++hl;
	else return ++hr;
}
template<class T>
void BinarySearchTree<T>::preOrder(BSTNode<T>* r)
{
	if(r)
	{
		cout<<r->key<<' ';
		preOrder(r->left);
		preOrder(r->right);
	}
}
template<class T>
void BinarySearchTree<T>::inOrder(BSTNode<T>* r)
{
	if(r)
	{
		inOrder(r->left);
		cout<<r->key<<' ';
		inOrder(r->right);
	}
}
template<class T>
void BinarySearchTree<T>::postOrder(BSTNode<T>* r)
{
	if(r)
	{	
		postOrder(r->left);
		postOrder(r->right);
		cout<<r->key<<' ';
	}
}

template<class T>
void BinarySearchTree<T>::makeBST()
{
	BSTNode<T>* r=root;
	T k;
	cout<<"Input the key you want to insert(-1 to end).\n";
	cin>>k;
	while(k!=-1)
	{	
		insertBSTNode(k);
	
	cout<<"Input the key you want to insert(-1 to end).\n";
	cin>>k;
	}
}
template<class T>
bool BinarySearchTree<T>::findBSTNode(T k)
{
	BSTNode<T>* p=0;
	if(root==0)
	{
		cout<<"Tree is empty!\n";
		return 0;
	}
	else
	{	
		BSTNode<T>* t=root;
		while(t!=0)
		{
			p=t;
			if(t->key==k)
				return 1;		
			else if(t->key<k)
			    t=t->right;
			else
				t=t->left;				
		}
		return 0;
	}

}
template<class T>
void BinarySearchTree<T>::insertBSTNode(T k)
{
	BSTNode<T>* p=0;
	if(root==0)
	{
		root=new BSTNode<T>(k);
	}
	else
	{	
		BSTNode<T>* t=root;
	
		while(t!=0)
		{
			p=t;
			if(t->key>k)
				t=t->left;
			else if(t->key<k)
			    t=t->right;
			else
			{
				cout<<"The key has existed in the tree,you can't insert it any more.\n";
				return ;
			}			
		}
		if(p->key>k)
			p->left=new BSTNode<T>(k);
		else
			p->right=new BSTNode<T>(k);
	}
}

template<class T>
void BinarySearchTree<T>::deleteByMerging(BSTNode<T>*& node) {   
    BSTNode<T> *tmp = node;
    if (node != 0) {
        if (node->right==0)           
             node = node->left;    
        else if (node->left == 0)   
             node = node->right;    
        else {                      
             tmp = node->left;      
             while (tmp->right != 0)
                tmp = tmp->right;
             tmp->right = node->right;                                            
             tmp = node;            
             node = node->left;    
        }
        delete tmp;                 
     }
}
template<class T>
void BinarySearchTree<T>::deleteByCopying(BSTNode<T>*& node) 
{    
    BSTNode<T> *previous, *tmp = node;
     if (node->right == 0)                  // node has no right child;
          node = node->left;   
     else if (node->left == 0)              // node has no left child;
          node = node->right;
     else {
          tmp = node->left;                 // node has both children;
          previous = node;                  // 1.
          while (tmp->right != 0) {         // 2.
              previous = tmp;
              tmp = tmp->right;
          }
          node->key = tmp->key;             // 3.
          if (previous == node)
               previous->left  = tmp->left;
          else previous->right = tmp->left; // 4.
     }
     delete tmp;                            // 5.
}
template<class T>
void BinarySearchTree<T>::findAndDelete(T k)
{
	BSTNode<T>* n=root, *pre=0;
	while(n!=0)
	{
		if(n->key==k)  break;     //寻找
		pre=n;
		if(n->key>k)
			n=n->left;
		else
			n=n->right;
	}
	if(n->key!=k)                 //找不到
	{
		cout<<"No such node include the key!\n";
		return;
	}
	if(n->left==0&&n->right==0)   //删除叶子节点
	{
		if(pre->left==n)
		{
			pre->left=0;
            delete n;
		}
		else
		{
			pre->right=0;
			delete n;
		}
	}
	else if(n->left==0)        //被删的左孩子空
	{
		if(pre->left==n)
		{
			pre->left=n->left;
		    delete n;
		}
		else
		{
			pre->right=n->right;
		    delete n;
		}
	}
	else if(n->right==0)        //被删的右孩子空
	{
		if(pre->left==n)
		{
			pre->left=n->left;
		    delete n;
		}
		else
		{
			pre->right=n->right;
		    delete n;
		}
	}
	else           //左右都不为空
	{
		if(pre->left==n)
			deleteByMerging(pre->left);
		else
			deleteByMerging(pre->right);
	}

}
template<class T>
bool BinarySearchTree<T>::isTreeBalanced(BSTNode<T>* r)
{
	int lflag,rflag;
	if(r!=0)
	{
	    int leftHeight=countHeight(r->left);
	    int rightHeight=countHeight(r->right);
		if(fabs(leftHeight-rightHeight)>1)
			return 0;
		else
		{
		    lflag=isTreeBalanced(r->left);
			rflag=isTreeBalanced(r->right);
		}
	}
	else
		return 1;
	if(rflag&&lflag)
		return 1;
	else
        return 0;
}

template<class T>
bool BinarySearchTree<T>::isTreeCompletelyBalanced(BSTNode<T>* r,int& i)
{
	int h=countHeight(root);
	if(r==0)
	{
		if(fabs(h-i)<1)
			return 1;
		else
			return 0;
	}

    int leftbool=isTreeCompletelyBalanced(r->left,++i);
	int rightbool=isTreeCompletelyBalanced(r->right,++i);
	if(leftbool&&rightbool)
		return 1;
	else
		return 0;
}


	//判断一棵树是不是完全二叉树
	/*Queue<BSTNode<T>*> queue;
    BSTNode<T> *p = root;
    if (p != 0) {
        queue.enqueue(p);
        while (!queue.IsEmpty()) 
		{
            queue.dequeue(p);

            if (p->left != 0)
                 queue.enqueue(p->left);
			else 
			{
				if(p->right != 0)
				    return 0;
				else
				{
					queue.dequeue(p);
					if(p->left||p->right)
						return 0;
					else 
						return 1;
				}					
			}
            if (p->right != 0)
                 queue.enqueue(p->right);
        }
}
	return 1;*/

template<class T>
void BinarySearchTree<T>::balance(T data[],int first,int last)
{
    if (first <= last) 
	{
        int middle = (first + last)/2;
        insertBSTNode(data[middle]);
        balance(data,first,middle-1);
        balance(data,middle+1,last);
    }
}

# endif