## 待修改，树的深度搜索和广度搜索

2017年11月15日 ⁄ 综合 ⁄ 共 1741字 ⁄ 字号 评论关闭

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 depthSearch();//深度优先遍历
//virtual void traverseTree();//遍历
//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>
{
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>
{
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);