#include <iostream>
using namespace std;
class Node {
public:
Node(int key_):left(NULL),right(NULL),key(key_){}
Node* left;
Node* right;
int key;
};
class BST {
public:
BST() : root(NULL) {}
~BST() {
clear(root);
}
void clear(Node* node) {
if (node == NULL) return;
clear(node->left);
clear(node->right);
delete node;
}
Node* searchNode(int key) {
Node* result = root;
while(result != NULL) {
if (result->key == key) return result;
result = key < result->key ? result->left : result->right;
}
return result;
}
Node* minSubNode(Node* node) {
Node* result = node;
while(result->left != NULL) result = result->left;
return result;
}
void insertNode(Node*& node, Node* new_node) {
if (node == NULL) node = new_node;
else if (new_node->key < node->key) insertNode(node->left, new_node);
else insertNode(node->right, new_node);
}
void insertKey(int key) {
Node* new_node = new Node(key);
insertNode(root, new_node);
}
Node* parNode(Node* child_node) {
if (child_node == root) return NULL;
Node* result = root;
while (result->left != child_node && result->right != child_node)
result = child_node->key < result->key ? result->left : result->right;
return result;
}
void sliceNode(Node* slice_node) {
Node* par = parNode(slice_node);
Node* slice_child_node = slice_node->left != NULL ? slice_node->left : slice_node->right;
if (par == NULL) {
root = slice_child_node;
} else {
if (par->left == slice_node) par->left = slice_child_node;
else par->right = slice_child_node;
}
}
void deleteNode(Node* del_node) {
if (del_node->left == NULL || del_node->right == NULL) {
sliceNode(del_node);
delete del_node;
} else {
Node* suc_node = minSubNode(del_node->left);
sliceNode(suc_node);
del_node->key = suc_node->key;
delete suc_node;
}
}
bool deleteKey(int key) {
Node* del_node = searchNode(key);
if (del_node == NULL) return false;
deleteNode(del_node);
return true;
}
private:
Node* root;
};
分享到:
相关推荐
函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针; 函数Delete将X从二叉搜索树BST中删除,并返回结果树的根结点指针;如果X不在树中,则打印一行Not Found并返回原树的根结点指针; 函数Find在二叉搜索树...
1.1.3 给定一个二叉搜索树(BST),找到树中第 K 小的节点
主要介绍了Python实现二叉搜索树BST的方法示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
二叉搜索树(BST)是一种常见的二叉树结构,它具有有序性质,使得在插入、删除和搜索操作上非常高效。本教程将向您展示如何使用Java编写代码来执行二叉搜索树的插入操作。我们将提供一个简单而清晰的示例,以帮助您...
二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造实验报告
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:1.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2.若它的右...
二叉查找树, 创建、查找、插入、删除、打印等功能都能实现,还包括先序、中序、后序遍历。可以参考,这资源规则都变了囧。
二叉搜索树 转为 双向链表, 导入eclipse时要改包名package classOne; BST To Double LinkedList change package name,
二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。 一般地,除了key和位置数据之外,每个结点...
简单的BST二叉搜索树的实现,测试数据可更改
C++实现二叉搜索树(BST),通过控制台能够实现增删改查,同时还能求树的高度,其中树的增加,删除等都是采用递归的方式生成的
当二叉排序树BST中不存在结点值等于e时,插入e并返回0,否则返回-1. ③int deleteBST(BTree *T, char key);删除 若二叉排序树T中存在结点值等于key时,则删除该数据元素,并返回0;否则返回-1。 ④BTree searchBST...
资源内容:完整的二叉查找树C++头文件,包括运算符重载,bst类构造器、bst类析构器、destroy()、size()、insert(),迭代器类的声明与实现,++运算符重载(前置、后置)、--运算符重载、*运算符重载、!=运算符重载、...
二叉搜索树中的搜索给定二叉搜索树(BST)的根节点和一个值。例如,给定二叉搜索树:和值: 2你应该返回如下子树:在上述示例中,如果要找的值是 5,但因为没有节点
数据结构中的二叉搜索树,对于插入和遍历的功能,有动画显示
二叉搜索树,包括插入、删除、查找、显示等功能
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node's key. The right ...
主要介绍了C++ 二叉搜索树(BST)的实现方法,非常不错,具有参考借鉴价值,需要的的朋友参考下
0501. 二叉搜索树中的众数标签:树、深度优先搜索、二叉搜索树、二叉树难度:简单题目大意给定一个有相同值的二叉搜索树(BST),要求找出 BST 中所有众数