二叉排序树的构造输出插入删除C++
时间: 2023-09-23 13:03:27 浏览: 59
二叉排序树(Binary Search Tree,BST)也称为二叉查找树或二叉搜索树,是一种特殊的二叉树,它满足以下性质:
1. 左子树所有节点的键值小于根节点的键值;
2. 右子树所有节点的键值大于根节点的键值;
3. 左右子树分别也是二叉排序树。
基于这个性质,我们可以实现二叉排序树的构造、输出、插入和删除操作。
下面是基于 C++ 的代码实现:
```c++
#include <iostream>
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 插入节点
void insertNode(TreeNode*& root, int val) {
if (root == NULL) {
root = new TreeNode(val);
return;
}
if (val < root->val) {
insertNode(root->left, val);
} else {
insertNode(root->right, val);
}
}
// 构造二叉排序树
TreeNode* buildBST(int* nums, int n) {
TreeNode* root = NULL;
for (int i = 0; i < n; i++) {
insertNode(root, nums[i]);
}
return root;
}
// 中序遍历输出二叉排序树
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 删除节点
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == NULL) {
return NULL;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
// 找到要删除的节点
if (root->left == NULL) {
TreeNode* rightChild = root->right;
delete root;
return rightChild;
} else if (root->right == NULL) {
TreeNode* leftChild = root->left;
delete root;
return leftChild;
} else {
// 左右子树都不为空,找到后继节点(右子树的最小值)
TreeNode* successor = root->right;
while (successor->left != NULL) {
successor = successor->left;
}
swap(root->val, successor->val);
root->right = deleteNode(root->right, key);
}
}
return root;
}
int main() {
int nums[] = {5, 1, 4, 7, 3, 6, 8};
int n = sizeof(nums) / sizeof(int);
TreeNode* root = buildBST(nums, n);
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 5);
inorderTraversal(root);
cout << endl;
return 0;
}
```
在上面的代码中,我们定义了一个 `TreeNode` 结构体来表示二叉树节点,其中包含一个 `val` 成员表示节点的值,以及 `left` 和 `right` 成员表示左右子树。
我们实现了以下函数:
- `insertNode`:插入节点,如果当前节点为空则直接插入,否则根据比较当前节点的值与待插入节点的值的大小关系递归地插入到左子树或右子树。
- `buildBST`:构造二叉排序树,遍历给定的数组,依次插入节点。
- `inorderTraversal`:中序遍历输出二叉排序树,按照左子树 -> 根节点 -> 右子树的顺序输出。
- `deleteNode`:删除节点,如果当前节点为空则返回 NULL,否则根据比较当前节点的值与待删除节点的值的大小关系递归地删除节点。如果找到待删除节点,分三种情况处理:(1)左子树为空,返回右子树;(2)右子树为空,返回左子树;(3)左右子树都不为空,找到后继节点,将其值与待删除节点的值交换,然后在右子树中递归地删除后继节点。
我们可以在 `main` 函数中测试这些函数的功能。首先构造一个二叉排序树,然后输出中序遍历结果。接着删除一个节点,再次输出中序遍历结果,可以看到节点已经被删除了。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)