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"); }