seldefbt.h

二叉树

// binaty tree defined by myself
//本定义中采用的老师的queue定义，用数组实现，希望自己用链表实现

# ifndef SELF_DEFINE_BT
# define SELF_DEFINE_BT

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

template<class T>
class Queue
{
public:
	Queue(int MaxQueueSize=10);
	~Queue(){delete [] queue;}
	bool IsEmpty() {return front==rear;}
	bool IsFull() 
	{
		if((rear+1)%MaxSize==front)
			return 1;
		else 
			return 0;
	}
	T First();//返回队首元素
	T Last() ;//返回队尾元素
	void enqueue(const T& x);
	void dequeue(T& x);
private:
	int front; //与第一个元素在反时针方向上相差一个位置
	int rear; //指向最后一个元素
	int MaxSize;//队列数组的大小
	T *queue; //数组 
};

template<class T>
Queue<T>::Queue(int MaxQueueSize)
{
	MaxSize=MaxQueueSize;
	queue=new T[MaxSize];
	front=rear=0;
}

template<class T>
T Queue<T>::First()
{
	if(IsEmpty())
		return -1;
	else
		return queue[(front+1)%MaxSize];
}

template<class T>
T Queue<T>::Last()
{
	if(IsEmpty())
		return -1;
	else
		return queue[rear];
}

template<class T>
void Queue<T>::enqueue(const T& x)
{
	if(IsFull())
	{  cout<<"no memeory";return;  }
	rear=(rear+1)%MaxSize;
	queue[rear]=x;
	return;
}

template<class T>
void Queue<T>::dequeue(T& x)
{
	if(IsEmpty())
	{  cout<<"no element";return;  }
	front=(front+1)%MaxSize;
	x=queue[front];
	return;
}
//------------------------------------------------------------------
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 BinaryTree  {
public:
    BinaryTree()
	{
		root=0;
	}
	BinaryTree(BSTNode<T>* r)
	{
		root=r;
	}

    BSTNode<T>* getRoot() const { return root;}
	void makeBinaryTree(BSTNode<T>* r);
	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>
void BinaryTree<T>::makeBinaryTree(BSTNode<T>* r)
{
	T ch;
	cout<<"Please input the key of the node \n";
	cin>>ch;
	if(ch!='#')
	{
	root=new BSTNode<T>(ch);
	makeBinaryTree(root->left);
	makeBinaryTree(root->right);
	}

	root=new BSTNode<T>(ch);
	root->left=0;
	root->right=0;
	return;

}
/*
const char *CreateBiTree(BiTree &T, const char *s) 
{ 
if (*s==’#’) 
{ 
    T = NULL; 
    return s+1; 
} 
else 
{ 
    T = new BiNode; 
    T->data = *s; 
    s = CreateBiTree(T->lchild, s+1); 
    s = CreateBiTree(T->rchild, s); 
    return s; 
} 

*/

# endif