建立二叉排序树以及进行查找、插入、删除等操作的算法的代码
时间: 2023-11-22 13:54:02 浏览: 43
以下是基于C++语言的二叉排序树的实现:
```c++
#include<iostream>
using namespace std;
//定义二叉树结点结构
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};
//初始化根节点为空
TreeNode* root = nullptr;
//插入节点
void insertNode(int value) {
//如果根节点为空,则创建一个新节点作为根节点
if (root == nullptr) {
root = new TreeNode;
root->data = value;
root->left = nullptr;
root->right = nullptr;
return;
}
//否则遍历树,找到合适的位置插入新节点
TreeNode* node = root;
while (node != nullptr) {
if (value < node->data) {
if (node->left == nullptr) {
node->left = new TreeNode;
node->left->data = value;
node->left->left = nullptr;
node->left->right = nullptr;
return;
}
else {
node = node->left;
}
}
else {
if (node->right == nullptr) {
node->right = new TreeNode;
node->right->data = value;
node->right->left = nullptr;
node->right->right = nullptr;
return;
}
else {
node = node->right;
}
}
}
}
//查找节点
TreeNode* searchNode(int value) {
TreeNode* node = root;
while (node != nullptr) {
if (node->data == value) {
return node;
}
else if (value < node->data) {
node = node->left;
}
else {
node = node->right;
}
}
return nullptr;
}
//删除节点
void deleteNode(int value) {
//查找要删除的节点
TreeNode* node = root;
TreeNode* parentNode = nullptr;
while (node != nullptr) {
if (node->data == value) {
break;
}
else if (value < node->data) {
parentNode = node;
node = node->left;
}
else {
parentNode = node;
node = node->right;
}
}
//如果未找到要删除的节点,则直接返回
if (node == nullptr) {
return;
}
//如果要删除的节点有两个子节点
if (node->left != nullptr && node->right != nullptr) {
//查找右子树中最小的节点
TreeNode* minNode = node->right;
TreeNode* minParentNode = node;
while (minNode->left != nullptr) {
minParentNode = minNode;
minNode = minNode->left;
}
//将右子树中最小的节点的值赋给要删除的节点
node->data = minNode->data;
//将要删除的节点变为右子树中最小的节点
node = minNode;
parentNode = minParentNode;
}
//如果要删除的节点只有一个子节点或者没有子节点
TreeNode* childNode = nullptr;
if (node->left != nullptr) {
childNode = node->left;
}
else if (node->right != nullptr) {
childNode = node->right;
}
//如果要删除的节点没有子节点,则将其父节点的对应子节点指针设为nullptr
if (childNode == nullptr) {
if (parentNode == nullptr) {
root = nullptr;
}
else if (node == parentNode->left) {
parentNode->left = nullptr;
}
else {
parentNode->right = nullptr;
}
delete node;
}
//如果要删除的节点只有一个子节点,则将其父节点的对应子节点指针设为其子节点
else {
if (parentNode == nullptr) {
root = childNode;
}
else if (node == parentNode->left) {
parentNode->left = childNode;
}
else {
parentNode->right = childNode;
}
delete node;
}
}
//中序遍历
void inorderTraversal(TreeNode* node) {
if (node == nullptr) {
return;
}
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
int main() {
insertNode(5);
insertNode(3);
insertNode(7);
insertNode(1);
insertNode(9);
insertNode(4);
insertNode(2);
cout << "中序遍历结果为:";
inorderTraversal(root);
cout << endl;
TreeNode* node = searchNode(7);
if (node != nullptr) {
cout << "查找结果:" << node->data << endl;
}
else {
cout << "未找到该节点" << endl;
}
deleteNode(5);
cout << "删除节点后中序遍历结果为:";
inorderTraversal(root);
cout << endl;
return 0;
}
```
以上代码实现了二叉排序树的插入节点、查找节点、删除节点和中序遍历等操作。其中,插入节点和删除节点的实现都需要遍历整棵树,时间复杂度为O(log n)。而查找节点的时间复杂度也为O(log n)。