一个简单的二叉搜索树的实现

上一篇文章简单实现了一个普通的二叉树,参见这里

二叉搜索树是二叉树的一种变体,它相比普通二叉树的特性就是里面的数据都是有序的,中序遍历它就可以得到一个升序数组。

BSTreet实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#pragma once
#include<iostream>
using namespace std;
template<typename T>
struct BSTreeNode
{
T _data;
BSTreeNode<T>* _left;
BSTreeNode<T>* _right;
BSTreeNode(const T& t=T())
:_data(t)
,_left(NULL)
,_right(NULL)
{}
};
template<typename T>
class BSTree
{
typedef BSTreeNode<T> Node;
public:
BSTree()
:_root(NULL)
{}
bool insert(const T& t)
{
Node* s=new Node(t);
if(_root==NULL)
{
_root=s;
return true;
}
else
{
Node* father=NULL;
Node* cur=_root;
while(cur!=NULL)
{
if(cur->_data==s->_data)
return false;
if(cur->_data<s->_data)
{
father=cur;
cur=cur->_right;
}
else
{
father=cur;
cur=cur->_left;
}
}
if(father->_data<s->_data)
father->_right=s;
else
father->_left=s;
return true;
}
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
protected:
void _InOrder(Node* root)
{
if(root==NULL)
return;
_InOrder(root->_left);
cout<<root->_data<<" ";
_InOrder(root->_right);
}
private:
Node* _root;
};

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往