データ構造実験------ツリー(Binary Tree)

使用する教材は電子工業出版社が出版した『Data Structures and Algorithm Analysis in C+』(『データ構造とアルゴリズム分析(C++)』(第3版))、著者は【美】Clifford A Shaffer、翻訳者は張銘、劉暁丹などである.したがって、一部のコードは本に与えられたものとほぼ同じであり、権利侵害があれば本人に連絡してください([email protected])、文章を削除します.
実験内容:1、再帰関数searchを記述し、入力パラメータは1本の二叉木と1つの値kであり、値kがツリーに現れるとtrueを返し、そうでないとflaseを返す.
2、再帰関数を作成してツリーの高さを返します.
3、再帰関数を作成して二叉木の葉結点数を計算する.
4、広さ優先で木を検索する.
------------BSTNode.h----------------

//   ADT
template<typename E>
class BinNode
{
public:
    virtual ~BinNode() {}
	virtual E& element() =0 ;
	virtual void setElement(const E& ) =0;
	virtual BinNode* left() const = 0;
	virtual void setLeft(BinNode* ) =0;
	virtual BinNode* right() const =0;
	virtual void setRight(BinNode*) = 0;
	virtual bool isLeaf() = 0;
};

template<typename E>
class BSTNode:public BinNode<E>
{
private:
    char k;
	E it;
	BSTNode* lc;
	BSTNode* rc;
	
public:
    BSTNode()
	{
	    lc = rc = NULL;
	}
	
	BSTNode(char temp, E e, BSTNode* l=NULL, BSTNode* r=NULL)
	{
	    k = temp;
		it = e;
		lc = l;
		rc = r;
	}
	
	~BSTNode()  {}
	
	E& element()
	{
	    return it;
	}
	
	void setElement(const E& e)
	{
	    it = e;
	}
	
	char& key() { return k; }
	
	void setKey(const char& temp )  
	{
	    k = temp;
	}
	
	inline BSTNode* left() const
	{
	    return lc;
	}
	
	void setLeft(BinNode<E>* b)
	{
	    lc = (BSTNode*) b;
	}
	
	inline BSTNode* right() const
	{
	    return rc;
	}
	
	void setRight(BinNode<E>* b)
	{
	    rc = (BSTNode*) b;
	}
	
	bool isLeaf()
	{
	    return lc==NULL&&rc==NULL;
	}
};

//   ADT
template<typename E>
class Queue
{
	void operator = (const Queue&) {}
	Queue(const Queue&) {}
public:
	Queue() {}
	virtual ~Queue() {}
	virtual void clear() = 0;
	virtual void enqueue(BSTNode<E>*) = 0;
	virtual BSTNode<E>* dequeue() = 0;
	virtual const BSTNode<E>* frontValue() const = 0;
	virtual  int length() const = 0;
};


template<typename E>
class Knot
{
public:
	BSTNode<E>* value;
	Knot* next;
	Knot( BSTNode<E>* v = NULL ,Knot* n = NULL)
	{
		value = v;
		next = n;
	}
};

template<typename E>
class Lqueue : public Queue<E>
{
	int size;
	Knot<E>* front;
	Knot<E>* rear;

public :
	Lqueue()  { front = rear = new Knot<E>(); size = 0; }
	~Lqueue() { clear();  delete front; }
	void clear()
	{
		while(front->next != NULL)
		{
			rear = front->next;
			delete rear;
		}
		rear = front;
		size = 0;
	}
	void enqueue( BSTNode<E>* it)
	{
		rear->next = new Knot<E>(it,NULL);
		rear = rear->next;
		size++;
	}
	BSTNode<E>* dequeue()
	{
		if(size==0)
			return NULL;
		BSTNode<E>* it = front->next->value;
		Knot<E>* temp = front->next;
		front->next = temp->next;
		size--;
		if(size==0)
			rear = front;
		delete temp;
		temp = NULL;
		return it;
	}

	const BSTNode<E>* frontValue() const
	{
		return front->next->value;
	}

	int length() const
	{
		return size;
	}
};

------------Main.cpp----------

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

//       
template<typename E>
bool search(BSTNode<E>* root,char temp)
{
    if(root==NULL) return false;
	if(root->key()==temp)
	    return true;
	if(search(root->left(),temp))
	    return true;
	return search(root->right(),temp);
}

//      
template<typename E>
int getHight(BSTNode<E>* root)
{
	int h = 0,h1 = 0;
	if(root == NULL)
		return h;
	else
	{
		h1 = h = 1;
	}
	h += getHight(root->left());
	h1 += getHight(root->right());
	return h > h1? h : h1;
}

//     
template<typename E>
int getNumOfLeaves(BSTNode<E>* root)
{
	if(root == NULL)
		return 1;
	return getNumOfLeaves(root->left())+getNumOfLeaves(root->right());
}

//build the tree
/*         A(0)
     -----/  \-----
	 |            |
	 B(1)         C(2)
----/\-----   ----/\----
|         |   |       |
D(3)     E(4) F(5)    G(6)  */
template<typename E>
void asign(BSTNode<E>*& root)
{
	root = new BSTNode<int>('A',0);
	root->setLeft(new BSTNode<int>('B',1));
	root->setRight(new BSTNode<int>('C',2));
	BSTNode<E>* temp = root->left();
	temp->setLeft(new BSTNode<int>('D',3));
	temp->setRight(new BSTNode<int>('E',4));
	temp = root->right();
	temp->setLeft(new BSTNode<int>('F',5));
	temp->setRight(new BSTNode<int>('G',6));
}

//       
template<typename E>
void breadthFirstSearch(BSTNode<E>*& root)
{
	Lqueue<E> lq;
	lq.enqueue(root);

	//        ，          
	int h = getHight(root);
	int* level = new int[h];
	int i = 0;
	for(;i<h;i++)
		level[i] = 0;
	i = 0;
	level[i]++;

	while(lq.length()>0)
	{
		BSTNode<E>* temp = lq.dequeue();
		level[i]--;
		if(temp->left()!=NULL)
		{
			lq.enqueue(temp->left());
			level[i+1]++;
		}
		if(temp->right()!=NULL)
		{
			lq.enqueue(temp->right());
			level[i+1]++;
		}
		cout<<temp->key()<<"     ";
		if(level[i]==0)
		{
			i++;
			cout<<endl;
		}
	}
}

int main()
{
	BSTNode<int>* root = NULL;
	asign<int>(root);
	cout<<"search 'E'  is :";
	if(search(root, 'E'))
		cout<<"true"<<endl;
	else
		cout<<"false"<<endl;
	
	cout<<"search 'J'  is :";
	if(search(root, 'J'))
		cout<<"true"<<endl;
	else
		cout<<"false"<<endl;

	cout<<"The hight of the tree is :"<<getHight<int>(root)<<endl;

	cout<<"The count of the leaf is :"<<getNumOfLeaves<int>(root)<<endl;

	cout<<"Breadth first search tree is:
";
	breadthFirstSearch<int>(root);

	system("PAUSE");
}

スクリーンショットの実行: