学步园

tree.h

#ifndef RBTREE_H
#define RBTREE_H
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <Stack>
#include <Queue>
using namespace std;

template<class T>
struct Node
{
	int item;
	Node<T>* parent;
	Node<T>* left;
	Node<T>* right;
};
template<class T>
class Tree
{
public:
	//树的基本构建析构
	Tree();
	~Tree();
	//树的操作符
	virtual void breadthSearch();//广度优先遍历
	virtual void depthSearch();//深度优先遍历
	//virtual void traverseTree();//遍历
	virtual bool addNode(T rhs);//添加
	//virtual void deleteNode(Node<T>* rhs);//删除
	//virtual Node<T>* searchNode(T value);//查找

private:
	Node<T>* root;
};
#endif

tree.cpp

#include "RBtree.h"

template<class T>
Tree<T>::Tree()
{
	root = new Node<T>;
	root = NULL;
}

template<class T>
Tree<T>::~Tree()
{
	delete root;
}


template<class T>
bool Tree<T>::addNode(T rhs)
{
	Node<T>* s =  new Node<T>;
	s->item = rhs;
	s->left = NULL;
	s->parent = NULL;
	s->right = NULL;
	Node<T>* lhs = root;
	int m;
	while(lhs)
	{
		m =rand()%2;
		if(m == 0)
		{
			if (lhs->left ==NULL)
			{
				lhs->left = s;
				s->parent = lhs;
				return true;
			}else
				lhs = lhs->left;
		}else{
			if (lhs->right ==NULL)
			{
				lhs->right = s;
				s->parent = lhs;
				return true;
			} else
				lhs = lhs->right;
		}
	}
	root = s;
	return true;
}

template<class T>
void Tree<T>::breadthSearch()
{
	queue<Node<T>*> que;
	que.push(root);
	Node<T>* s ;
	while(!que.empty())
	{
		s = que.front();
		que.pop();
		std::cout<< s->item<<" ";
		if (s->left != NULL)
		{
			que.push(s->left);
		}
		if (s->right != NULL)
		{
			que.push(s->right);
		}
		
	}
	std::cout<<std::endl;
}

template<class T>
void Tree<T>::depthSearch()
{
	stack<Node<T>*> sta;
	sta.push(root);
	Node<T>* s;
	while(!sta.empty())
	{
		s = sta.top();
		std::cout<< s->item<<" ";
		sta.pop();
		if (s->right != NULL)
		{
			sta.push(s->right);
		}
		if (s->left != NULL)
		{
			sta.push(s->left);
		}
	}
	std::cout<<std::endl;
}

test.cpp

#include "RBtree.cpp"
#include <Windows.h>

void main()
{
	Tree<int> a;
	int m;
	srand(unsigned(time(NULL)));
	for (int i = 0;i < 20;i++)
		{
			
			m = rand()%10;
			Sleep(1000);
			a.addNode(m);
			cout<< m<<" ";
	}
	cout<<endl;
	a.breadthSearch();
	a.depthSearch();
	system("pause");
}