seldef_bst.cpp

二叉树

// self-defined BST 

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

template<class T>
int countAllNode(BSTNode<T>* r);
//int countLeafNode(BSTNode<T>* r);
//int countRightNode(BSTNode<T>* r);
//void deleteLeafNode(BSTNode<T>* r);

void main()
{
	BSTNode<char> d('D',0,0),e('E',0,0);
	BSTNode<char> b('B',&d,&e);
	BSTNode<char> f('F',0,0),c('C',0,&f);
	BSTNode<char> a('A',&b,&c);
	int n=countAllNode(&a);
	cout<<n<<endl;


}

template<class T>
int countAllNode(BSTNode<T>* r)
{
	int n=0;
	BSTNode<T> *p=r;
	LinkedQueue<BSTNode<T>*> Q;
	while(p)
	{
		cout<<p->key;//访问p
		n++;
		//将p的孩子放入队列
		if(p->left) 
			Q.enqueue(p->left);
		if(p->right) 
			Q.enqueue(p->right);
		
		//访问下一个结点
		if(Q.IsEmpty())
			return n;
		else
			Q.dequeue(p);
	}
	/*BSTNode<char>* t=r;
	//char ch;
	int n=0;
	LinkedQueue<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;
}
//int countLeafNode(BSTNode* r);
//int countRightNode(BSTNode* r);
//void deleteLeafNode(BSTNode* r);