6_12_2.cpp

该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现

#include<iostream.h>
#include"lQueue.h"
#include"BST.h"
template<class T>
int nodeNumber(BSTNode<T> *root)
{
	int i=0;
	if(root==NULL)
		return 0;
	else
	{
		
		lQueue<BSTNode<T>*> a;
		a.enqueue(root);
		while(!a.isEmpty())
		{
			root=a.dequeue();
			i++;
			if(root->left!=NULL)
				a.enqueue(root->left);
			if(root->right!=NULL)
				a.enqueue(root->right);
		}
		return i;
	}
}
template<class T>
int leavesNumber(BSTNode<T> *root)
{
	int i=0;
	if(root==NULL)
		return 0;
	else
	{
		
		lQueue<BSTNode<T>*> a;
		a.enqueue(root);
		while(!a.isEmpty())
		{
			root=a.dequeue();
			if(root->left==NULL&&root->right==NULL)
				i++;
			if(root->left!=NULL)
				a.enqueue(root->left);
			if(root->right!=NULL)
				a.enqueue(root->right);
		}
		return i;
	}
}
template<class T>
int rightNodeNumber(BSTNode<T> *root)
{
	int i=0;
	if(root==NULL)
		return 0;
	else
	{
		
		lQueue<BSTNode<T>*> a;
		a.enqueue(root);
		while(!a.isEmpty())
		{
			root=a.dequeue();
			if(root->right!=NULL)
			i++;
			if(root->left!=NULL)
				a.enqueue(root->left);
			if(root->right!=NULL)
				a.enqueue(root->right);
		}
		return i;
	}
}
template<class T>
int height(BSTNode<T> *root)
{
	if(root==NULL)
		return 0;
	else if(root->left==NULL&&root->right==NULL)
		return 1;
	else
	{
		int l=height(root->left),r=height(root->right);
		if(l>r)
			return 1+l;
		else 
			return 1+r;
	}

}
template<class T>
void delLeaves(BSTNode<T> *root)
{
	int i=0;
	if(root==NULL)
		cout<<"NO NODE!"<<endl;
	else if(root->left==NULL&&root->right==NULL)
	{
		delete root;
		root=NULL;
	}
	else
	{
		
		lQueue<BSTNode<T>*> a;
		a.enqueue(root);
		while(!a.isEmpty())
		{
			root=a.dequeue();
			if(root->left!=NULL)
				if(root->left->left==NULL&&root->left->right==NULL)
				{
					BSTNode<T> *p=root->left;
					root->left=NULL;
					delete p;
				}
			if(root->right!=NULL)
				if(root->right->left==NULL&&root->right->right==NULL)
				{
					BSTNode<T> *p=root->right;
					root->right=NULL;
					delete p;
				}
			if(root->left!=NULL)
				a.enqueue(root->left);
			if(root->right!=NULL)
				a.enqueue(root->right);
		}
	}
}
void main()
{
	BST<int> a;
	int b1,b2,b3,b4;
	a.insert(2);
	a.insert(3);
	BSTNode<int> *p=a.getRoot();
	b1=nodeNumber(p);
	b2=leavesNumber(p);
	b3=rightNodeNumber(p);
	b4=height(p);
	cout<<b1<<" "<<b2<<" "<<b3<<" "<<b4<<endl;
	delLeaves(p);
	cout<<nodeNumber(p)<<endl;


	
	
}