数据结构 二叉检索树的C++实现_给定一组无序序列,建立一棵二叉检索树c++

1. 定义
   二叉检索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉检索树。又称二叉搜索树，二叉排序树。

2. 结点的实现

template<typename Key, typename E>
struct BSTNode {
	typedef BSTNode<Key, E>node;
	node* left;
	node* right;
	Key key;
	E val;
	BSTNode(const Key& k, const E& v,
         node* l = nullptr, node* r = nullptr)
		:key(k), val(v), left(l), right(r) {}
	void setleft(node* t) { left = t; }
	void setright(node* t) { right = t; }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 基本操作

• 查找

  设查找的值为K，若k小于当前结点的值，则检索该节点的左子树，否则检索该节点的右子树。该过程一直持续到查找到该值或到达叶结点。若到达叶结点还未找到，则该值不在该树中。

//E为数值的数据类型,Key为键值的数据类型 
E* find(const Key& k) {
        return findhelp(root, k);
}
E* findhelp(node* t, const Key& k) {
        //已空或为空子树，未查找到，返回空指针
		if (t == nullptr) return nullptr;
		//查询左子树
		if (k < t->key)return findhelp(t->left, k);    
		//查询右子树
		else if (k > t->key)return findhelp(t->right, k);
		//返回键对应的值
		else return &(t->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 插入

要插入一个值，首先要明确它应该被插到什么地方。递归查询它应该被插入的地方，最终达到一个叶结点或在待插入方向上没有子节点的分支结点。最后将该值插进去。

void insert(const Key& k, const E& v) {
        //n为结点数目
	     ++n; root = inserthelp(root, k, v);
}
node* inserthelp(node* t, const Key& k, const E& v) {
        //空树，直接new一个结点
		if (t == nullptr)return new node(k, v);
		//键值大于要插入的键值，往左边插
		if (k < t->key)
			t->setleft(inserthelp(t->left, k, v));
		//否则插入右边
		else
			t->setright(inserthelp(t->right, k, v));
		//返回新的根节点
		return t;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 删除
  在考虑如何删除任一结点时，先着眼于如何删除键值最小(大)的结点。
  由于二叉检索树的性质，只要沿着左边的链一直移动直到叶结点，该叶结点就是键值最小的结点。要移走该叶结点，只需将它的父节点指向它的左子树(如果有的话

node* deletemin(node* t) {
        //直到没有左节点，返回右结点
		if (t->left == nullptr)return t->right;
		else {
		    //删除最小键值结点
			t->setleft(deletemin(t->left));
			//返回新的根节点
			return t;
		}
}
1
2
3
4
5
6
7
8
9
10

还可以根据这个性质来找到最小键值结点

node* getmin(node* t) {
        //搜索到空指针，返回
		if (t->left == nullptr)return t;
		//一直沿着左边移动
		return getmin(t->left);
}
1
2
3
4
5
6

接下来就考虑如何删除任一结点了。首先找到这一节点，
如果它没有子节点，就将它的父节点指向它的指针设为空指针。
如果它有一个子节点，那么将它的父节点指向它的指针改为指向它的子节点的指针。
如果它有两个子节点，较好的做法是从它的子树中找到一个可以替代它的值。为了保持二叉检索树的性质，我们应该选择大于等于被替换值的最小值或小于等于它的最大值。即左子树中值最大的结点或右子树中值最小的结点。由于我们在建立二叉检索树时，大于等于结点的值都在结点的右子树，故我们最好选择右子树的最小值。否则树的性质就会发生改变。

void remove(const Key& k) {
		root = removehelp(root, k);
		--n;    //结点数减一
}
node* removehelp(node* t, const Key& k) {
        //k不在树中
		if (t == nullptr)return nullptr;
		//改变父节点的指向
		if (k < t->key)
			t->setleft(removehelp(t->left, k));
		else if (k > t->key)
			t->setright(removehelp(t->right, k));
		//找到对应结点
		else {
			node* temp = t;
			//左子树为空的情况
			if (t->left == nullptr) {
				t = t->right;
				safe_delete(temp);
			}
			//右子树为空的情况
			else if (t->right == nullptr) {
				t = t->left;
				safe_delete(temp);
			}
			else {
			    //找到右子树的最小值
				temp = getmin(t->right);
				//替换
				t->val = temp->val;
				t->key = temp->key;
				//删除该节点
				t->setright(deletemin(t->right));
				safe_delete(temp);
			}
		}
		//放hi新的根节点
		return t;
	}
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

• 完整代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define safe_delete(p) if(p){delete p;p=nullptr;}
using namespace std;

template<typename Key, typename E>
struct BSTNode {
	typedef BSTNode<Key, E>node;
	node* left;
	node* right;
	Key key;
	E val;
	BSTNode(const Key& k, const E& v,
         node* l = nullptr, node* r = nullptr)
		:key(k), val(v), left(l), right(r) {}
	void setleft(node* t) { left = t; }
	void setright(node* t) { right = t; }
};

template<typename Key, typename E>
class BST {
typedef BSTNode<Key, E>node;
private:
	node* root;
	int n;
	node* inserthelp(node* t, const Key& k, const E& v) {
		if (t == nullptr)return new node(k, v);
		if (k < t->key)
			t->setleft(inserthelp(t->left, k, v));
		else
			t->setright(inserthelp(t->right, k, v));
		return t;
	}
	node* deletemin(node* t) {
		if (t->left == nullptr)return t->right;
		else {
			t->setleft(deletemin(t->left));
			return t;
		}
	}
	node* getmin(node* t) {
		if (t->left == nullptr)return t;
		return getmin(t->left);
	}
	node* removehelp(node* t, const Key& k) {
		if (t == nullptr)return nullptr;
		if (k < t->key)
			t->setleft(removehelp(t->left, k));
		else if (k > t->key)
			t->setright(removehelp(t->right, k));
		else {
			node* temp = t;
			if (t->left == nullptr) {
				t = t->right;
				safe_delete(temp);
			}
			else if (t->right == nullptr) {
				t = t->left;
				safe_delete(temp);
			}
			else {
				temp = getmin(t->right);
				t->val = temp->val;
				t->key = temp->key;
				t->setright(deletemin(t->right));
				safe_delete(temp);
			}
		}
		return t;
	}
	E* findhelp(node* t, const Key& k) {
		if (t == nullptr) return nullptr;
		if (k < t->key)return findhelp(t->left, k);
		else if (k > t->key)return findhelp(t->right, k);
		else return &(t->val);
	}
	void clearhelp(node* t) {
		if (t == nullptr)return;
		clearhelp(t->left);
		clearhelp(t->right);
		safe_delete(t);
	}
	void printhelp(node* t, int dep) {
		if (t == nullptr)return;
		printhelp(t->left, dep + 1);
		for (int i = 0; i < dep; ++i)
			putchar(' ');
		cout << t->key << " " << t->val << endl;
		printhelp(t->right, dep + 1);
	}
public:
	BST() { n = 0; root = nullptr; }
	~BST() { clearhelp(root); }
	void clear() {
	    clearhelp(root); n = 0; root = nullptr;
    }
	void insert(const Key& k, const E& v) {
	     ++n; root = inserthelp(root, k, v);
    }
	void remove(const Key& k) {
		root = removehelp(root, k);
		--n;
	}
	E* find(const Key& k) {
        return findhelp(root, k);
    }
	int size()const { return n; }
	void print() {
		if (root != nullptr)
			printhelp(root, 1);
	}
};

int main(int argc, char** argv) {
	BST<int, int>t;
	int n = 5;
	int a, b;
	for (int i = 0; i < n; ++i){
        scanf("%d%d",&a,&b);
		t.insert(a, b);
	}
	t.print();
	scanf("%d",&a);
	int *x = t.find(a);
	if (x != nullptr)
		cout << *x << endl;
    safe_delete(x);
	t.clear();
	return 0;
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133