BST树基本操作_bst中序遍历

BST树的概念

一、二叉搜索树（binary search tree）即就是我们所说的BST树
二、BST树的特征：任何一个节点比它的左孩子大，比它的右孩子小，
如图所示就是一颗BST树

三、定义BST树的节点类型

struct BSTNode
	{
		BSTNode(T data = T())
			:_data(data)
			, _left(nullptr)
			, _right(nullptr)
		{}
		T _data;
		BSTNode *_left;
		BSTNode *_right;
	};
1
2
3
4
5
6
7
8
9
10
11

BST树的实现

BST树的插入操作

1、非递归实现BST树的插入操作

void noninsert(const T &val)
	{
		if (_root == nullptr)
		{
			_root = new BSTNode(val);
			return;
		}
		BSTNode* pre = nullptr;
		BSTNode * cur = _root;
		while (cur != nullptr)
		{
			pre = cur;
			if (val < cur->_data)
			{
				cur = cur->_left;
			}
			else if (val > cur->_data)
			{
				cur = cur->_right;
			}
			else
			{
				return;
			}
		}
		if (val < pre->_data)
		{
			pre->_left = new BSTNode(val);
		}
		else
		{
			pre->_right = new BSTNode(val);

		}
	}
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

2、递归实现BST树的插入

void insert(const T &val)
	{
		_root = insert(_root,val);
	}

BSTNode* insert(BSTNode * node, const T &val)
	{
		if (node == nullptr)
		{
			return new BSTNode(val);
		}

		if (val > node->_data)
		{
			node->_right = insert(node-_right,val);
		}
		else if (val < node->_data)
		{
			node->_left = insert(node->_left,val);
		}
		else
		{
			;
		}
		return node;
	}
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

3、非递归实现层序遍历,从根结点开始，一层一层从左向右遍历，相当于打印

void nonlevelOrder()
	{
		//1.如果_root为空，直接返回
		if (_root == nullptr)
			return;
		//2._root -> queue
		queue<BSTNode*> que;
		que.push(_root);
		//3.循环判断队列是否为空，不为空取出队头元素，分别判断左右孩子是否为空，不为空就要依次入队，然后打印队头元素，继续判断下一个队头元素
		
		while (!que.empty())
		{
			BSTNode *front = que.front();
			cout << front->_data << " ";
			que.pop();
			if (front->_left != nullptr)
			{
				que.push(front->_left);
			}
			if (front->_right != nullptr)
			{
				que.push(front->_right);
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

BST树的删除操作

1、删除操作分三种情况：
1）、删除的节点没有孩子节点
2）、删除的节点只有一个孩子节点
3）、删除的节点有两个孩子节点
2、非递归实现BST树的删除操作

void nonremove(const T &val)
	{
		//1.从_root开始寻找值为val的节点，cur指向它
		BSTNode *cur = _root;
		BSTNode *pre = nullptr;
		while (cur != nullptr)
		{
			if (val < cur->_data)
			{
				pre = cur;
				cur = cur->_left;
			}
			else if (val > cur->_data)
			{
				pre = cur;
				cur = cur->_right;

			}
			else
			{
				break;
			}
		}
		if (cur == nullptr)
			return;
		//2.先判断是否满足情况3，如果满足，需要找cur的前驱节点，用前驱把cur节点的值覆盖，直接删前驱
		//前驱节点：当前节点左子树中的最大值
		//后继节点：当前节点右子树元素中的最小值
		if (cur->_left != nullptr && cur->right != nullptr)
		{
			BSTNode *old = cur;
			pre = cur;
			cur = cur->_left;
			while (cur->_right != nullptr)
			{
				pre = cur;
				cur = cur->_right;
			}
			old->_data = cur->_data;//找到了cur的前驱节点把原来要删除的节点覆盖
		}
		//3.删除情况1和情况2  直接删除cur指针指向的节点就可以了
		BSTNode *child = cur ->_left;
		if (child == nullptr)
		{
			child = cur->_right;
		}
		if (pre == nullptr)//cur指向的根节点
		{
			_root = child;
		}
		else
		{
			//要把删除节点的孩子赋给cur父节点相应的地址域里面
			if (cur == pre->_left)
			{
				pre->_left = child;
			}
			else
			{
				pre->_right = child;
			}
		}

		delete cur;
	}
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

3、递归实现BST树的删除操作

void remove(const T &val)
	{
		_root = remove(_root,val);
	}

//以node 为根节点，递归实现BST树的删除操作,并返回其孩子节点的地址更新父节点相应地址域
	BSTNode *remove(BSTNode * node, const T &val)
	{
		if (node == nullptr)
			return nullptr;
		if (val < node->_data)
		{
			node->_left =  remove(node->_left,val);
		}
		else if (val > node->_data)
		{
			node->_right = remove(node->_right,val);
		}
		else
		{
			if (node->_left != nullptr && node->_right != nullptr);
			{
				BSTNode *pre = node->_left;
				while (pre->_right != nullptr)
				{
					pre = pre->_right;
				}
				node->_data = pre->_data;
				//直接删除前驱 node = remove(pre,pre->_data);
				node->_left = remove(node->_left, pre->_data);
			}
			else
			{
				if (node->_left != nullptr)
				{
					BSTNode *left = node->_left;
					delete node;
					return left;
				}
				else if (node->_right != nullptr)
				{
					BSTNode *right = node->_right;
					delete node;
					return right;
				}
				else
				{
					delete node;
					return nullptr;
				}
			}
		}
		
	}
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

BST树的查找

1、递归实现查询val的值，找到返回true,否则返回false

bool query(const T &val)
	{
		return query(_root,val);
	}

//以node为根节点开始搜索值为val的节点
	bool query(BSTNode * node, const T &val)
	{
		if (node == nullptr)
		{
			return false;
		}
		if (val > node->_data)
		{
			return query(node->_right,val);
		}
		else if (val < node->_data)
		{
			return query(node->_left, val);
		}
		else
		{
			return true;

		}

	}
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

BST树的遍历

BST有前序遍历（VLR）、中序遍历（LVR）、后序遍历（LRV）以及层序遍历。

BST树的前序遍历

1、递归实现前序遍历 根左右VLR

void preOrder()
	{
		cout << "递归实现前序遍历: ";
		preOrder(_root);
		cout << endl;
	}

//以node为根节点（v）前序遍历BST树
	void preOrder(BSTNode *node)
	{
		if (node != nullptr)
		{
			cout << node->_data << " "; //先打印根节点
			preOrder(node->_left); //以VLR的方式继续访问左孩子
			preOrder(node->_right);//以VLR的方式继续访问右孩子
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BST树的中序遍历

//递归实现中序遍历 左根右 LVR
	void inOrder()
	{
		cout << "递归实现中序遍历：";
		inOrder(_root);
		cout << endl;

	}
	

//以node为根节点（v）中序遍历BST树 LVR
	void inOrder(BSTNode *node)
	{
		if (node != nullptr)
		{
			inOrder(node->_left);
			cout << node->_data << " ";
			inOrder(node->_right);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

BST树的后序遍历

//递归实现后序遍历 左右根 LRV
	void postOrder()
	{
		cout << "递归实现后序遍历:";
		postOrder(_root);
		cout << endl;

	}

//以node为根节点（v）后序遍历BST树  LRV
	void postOrder(BSTNode *node)
	{
		if (node != nullptr)
		{
			postOrder(node->_left);
			postOrder(node->_right);
			cout << node->_data << " ";
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

BST树的层序遍历

//递归实现层序遍历
	void levelOrder()
	{
		cout << "递归实现层序遍历:";
		int l = level(_root);
		for (int i = 0; i < l; ++i)
		{
			 levelOrder(_root,i);
		}
		cout << endl;
	}

//打印以node为根节点的树的层序遍历
	void levelOrder(BSTNode *node, int k)
	{
		if (node != nullptr)
		{
			if (k == 0)
			{
				cout << node->_data << " ";
				return;
			}
			levelOrder(node->_left, k - 1);
			levelOrder(node->_right, k - 1);
		}
	}
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

BST树的一些常见题型

1、判断当前二叉树是不是一颗BST树

bool isBSTree()
	{
		BSTNode *pre = nullptr;
		return isBSTree(_root,pre);
	}

//以node为根节点判断当前BST树是不是一颗二叉树
	bool isBSTree(BSTNode *node, BSTNode *&pre)
	{
		if (node == nullptr)   
		{
			return true;
		}
		if (!isBSTree(node->_left, pre))
		{
			return false;
		}

		if (pre != nullptr)
		{
			if (node->_data < pre->_data)
			{
				return false;
			}
		}
		pre = node;

		return isBSTree(node->_right,pre);
	}
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

2、在当前BST树中，把满足区间[first,last]的所有元素找出来并打印
3、获取两个节点的最近公共祖先节点
4、获取中序遍历倒数第k个节点的值
5、已知一颗BST树的前序遍历结果pre数组，和中序遍历结果in数组，重建二叉树
等等，这都是BST树的经典题型题。