使用C++实现二叉查找树（二叉搜索树）的创建、查找、插入、删除等操作_二叉搜索树 创建与插入 c++

主要实现了以下接口：

1、二叉查找树的结构定义

2、二叉查找树中建立新节点

3、二叉查找树中查找

4、二叉查找树的插入

5、二叉查找树的建立

6、二叉查找树的删除

#include <iostream>
using namespace std;

// 二叉树的节点结构体
struct node {	
	int data;	  // 数据域 
	node* lchild; // 指针域：左孩子
	node* rchild; // 指针域：右孩子
};

// 创建新节点
node* newNode(int v) {
    node* Node = new node;
    Node->data = v;
    Node->lchild = Node->rchild = nullptr;
    return Node;
}

// 二叉查找树的查找操作
bool search(node* root, const int& val) {
	if (root == nullptr)   return false;
	if (root->data == val) return true;
	else if (root->data > val) {
		search(root->lchild, val);
	} else {
		search(root->rchild, val);
	}
}

// 二叉查找树的插入操作
void insert(node* root, const int& val) {
	if (root == nullptr) {
		root = newNode(val);
	}

	if (root->data == val) {
		return; // 已经有相同的值
	} else if (root->data > val) {
		insert(root->lchild, val);
	} else {
		insert(root->rchild, val);
	}
}

// 二叉查找树的建立
node* create(vector<int>& data) {
	node* root = nullptr;
	for (auto& iter : data) {
		insert(root, iter);
	}
	return root;
}

// 二叉查找树的删除
/*
	为保证删除某一个节点之后仍然为一个二叉查找树，
	一种方法是，找到删除节点的左子树中的最大值，替换掉删除的节点
	另一种方法是，找到删除节点的右子树中的最小值，替换掉删除的节点
	替换的方法是进行删除节点的递归操作
*/

// 传入的是左孩子节点，找到左子树中的最大值，
node* GetLeftMax(node* root) {
	while (root != nullptr) {
		root = root->rchild;
	}
	return root; 
}

// 传入的是右孩子节点，找到右子树中的最小值，
node* GetRightMin(node* root) {
	while (root != nullptr) {
		root = root->lchild;
	}
	return root; 
}

// 二叉查找树的删除操作
void deleteNode(node* &root, int& val) {
	if (root == nullptr) return;
	if (root->data > val) {
		deleteNode(root->lchild, val);
	} else if (root->data < val) {
		deleteNode(root->rchild, val);
	} else {
		if (root->lchild == nullptr && root->rchild == nullptr) {
			delete root;	// 释放内存
			root = nullptr; // 指针置空
		} else if (root->lchild != nullptr) { 
			node* pre = GetLeftMax(root->lchild);
			root->data = pre->data; // 使用前驱节点替换要删除的节点
			deleteNode(root->lchild, pre->data); // 递归删除掉替换的节点
		} else if (root->rchild != nullptr) { 
			node* post = GetRightMin(root->rchild);
			root->data = post->data; // 使用后继节点替换要删除的节点
			deleteNode(root->rchild, post->data); // 递归删除掉替换的节点
		}
	}
}

int main() {
	
	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

谢谢阅读