seldefbst.cpp

二叉树

// self-defined BST 

#include <iostream>
using namespace std;
#include"selDefBST.h"
//#include"genQueue.h"

template<class T>
int countAllNode(BSTNode<T>* r)
{
	BSTNode<char>* t=r;
	int n=0;
	Queue<BSTNode<char>*> q;
	q.enqueue(t);

	while(!q.IsEmpty())
	{
		q.dequeue(t);
		cout<<t->key<<endl;
		n++;
		if(t->left!=0)
			q.enqueue(t->left);
		if(t->right!=0)
			q.enqueue(t->right);
	}
	return n;
}

template<class T>
int countLeafNode(BSTNode<T>* r)
{
	BSTNode<char>* t=r;
	int leafNode=0;
	Queue<BSTNode<char>*> q;
	q.enqueue(t);

	while(!q.IsEmpty())
	{
		q.dequeue(t);
		if(t->left==0&&t->right==0)
		{
			cout<<t->key<<endl;
			leafNode++;
		}
		if(t->left!=0)
			q.enqueue(t->left);
		if(t->right!=0)
			q.enqueue(t->right);
	}
	return leafNode;

}
template<class T>
int countRightNode(BSTNode<T>* r)
{
	BSTNode<char>* t=r;
	int rightNode=0;
	Queue<BSTNode<char>*> q;
	q.enqueue(t);

	while(!q.IsEmpty())
	{
		q.dequeue(t);
		if(t->right!=0)
		{
			cout<<t->right->key<<endl;
			rightNode++;
		}
		if(t->left!=0)
			q.enqueue(t->left);
		if(t->right!=0)
			q.enqueue(t->right);
	}
	return rightNode;

}
template<class T>
int countHeightOfTree(BSTNode<T>* r)
{
	int lh,rh;
	if(r==0)
		return 0;
	lh=countHeightOfTree(r->left)+1;
	
	rh=countHeightOfTree(r->right)+1;

	if(lh>=rh)
		return lh;
	else
		return rh;

}

template <class T>
void deleteLeafNode(BSTNode<T>* r)
{
	BSTNode<char>* p=0;
	BSTNode<char>* t=r;

	Queue<BSTNode<char>*> q;
	q.enqueue(t);

	while(!q.IsEmpty())
	{
		q.dequeue(t);
		if(t->left!=0)
		{
		    if(t->left->left==0&&t->left->right==0)
			{
			cout<<t->left->key<<endl;
			t->left=0;	 	
			}
		}
		if(t->right!=0)
		{
		    if(t->right->left==0&&t->right->right==0)
			{
			cout<<t->right->key<<endl;
			t->right=0;
			}
		}	
		if(t->left!=0)
		{
			q.enqueue(t->left);
		}
		if(t->right!=0)
		{
			q.enqueue(t->right);
		}
	}
	return ;
}

void main()
{
	BinaryTree<char> tree;
	BSTNode<char>* a=0;
	tree.makeBinaryTree(a);

    /*BSTNode<char> g('G',0,0),h('H',0,0);
	BSTNode<char> d('D',0,0),e('E',&g,&h);
	BSTNode<char> b('B',&d,&e);
	BSTNode<char> f('F',0,0),c('C',0,&f);
	BSTNode<char> a('A',&b,&c);*/

	cout<<"The total number of the tree is "<<countAllNode(a)<<endl<<endl;;

	//cout<<"The leaf node of the tree is "<<countLeafNode(a)<<endl<<endl;

	//cout<<"The right node of the tree is "<<countRightNode(a)<<endl<<endl;

	//cout<<"The height of the tree is "<<countHeightOfTree(a)<<endl<<endl;

	//cout<<"Delete all the leaf nodes, they are \n";
	//deleteLeafNode(a);

}