bst
二叉排序树/二叉查找树/BST(binary search tree)
或者是一棵空的二叉树，或者是具有下列性质的二叉树：
1、若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
2、若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
3、它的左右子树也都是二叉排序树。
4、中序遍历可以得到一个递增序列
查找：
对于要查找的值，如果比根节点小，就搜索左子树，否则就搜索右子树，如果搜到叶子节点还是没有，则不存在这个值
插入：
1、若二叉排序树是空树，结点s成为二叉排序树的根；
2、若二叉树排序树非空，则将s的关键字值key与二叉树排序树的根进行比较，
①如果s的值等于根结点的值，则停止插入；
②如果s的值小于根结点的值，则将s插入左子树；
③如果s的值大于根结点的值，则将s插入右子树。
删除：
假设删除节点为p
1、p只有右子树，那么找到p的双亲s，如果p是根，,则根节点=p->right，如果s的右孩子是p，那么s->right=p->right,否则s->left=p->right
2、p只有左子树，那么找到p的双亲s，如果p是根，,则根节点=p->left，如果s的右孩子是p，那么s->right=p->left,否则s->left=p->left
3、找到p的右孩子的最左下的节点s，也就是中序遍历中p的后继，或者是右子树中最小的值，用s的值替换p的值，然后按照规则1，2删除s节点
#include<iOStream>
#include<queue>
using namespace std;
template<typename T>
class Node {
public:
T value;
Node* parent, *left, *right;
Node() :parent(nullptr), left(nullptr), right(nullptr) {}
Node(const T &value) :value(value), parent(nullptr), left(nullptr), right(nullptr) {}
};
template<typename T>
class BST {
private:
Node<T>* root;
//以root为根前序遍历
void preorder(Node<T> * root)const {
if (root) {
cout << root->value << ' ';
preOrder(root->left);
preOrder(root->right);
}
}
//以root为根中序遍历
void inOrder(Node<T>* root)const {
if (root) {
inOrder(root->left);
cout << root->value << ' ';
inOrder(root->right);
}
}
//以root为根后序遍历
void postOrder(Node<T>* root)const {
if (root) {
postOrder(root->left);
postOrder(root->right);
cout << root->value << ' ';
}
}
//往以root为根的树插入节点
void insert(Node<T> *rt, const T &value) {
Node<T>* parent = nullptr;
while (rt) {
parent = rt;
//这个值已经有了
if (rt->value == value)return;
if (value < rt->value)rt = rt->left;
else rt = rt->right;
}
rt = new Node<T>(value);
rt->parent = parent;
if (parent == nullptr)root = rt;
else if (value < parent->value)parent->left = rt;
else parent->right = rt;
}
//查找rt为根的最小值
Node<T>* getMin(Node<T>* rt)const {
if (rt == nullptr)return nullptr;
while (rt->left)rt = rt->left;
return rt;
}
//查找rt为根的最大值
Node<T>* getMax(Node<T>* rt)const {
if (rt == nullptr)return nullptr;
while (rt->right)rt = rt->right;
return rt;
}
void destory(Node<T>* rt) {
if (rt) {
destory(rt->left);
destory(rt->right);
delete rt;
}
}
public:
BST() :root(nullptr) {}
~BST() {
destory(root);
}
//前序遍历
void preOrder()const {
preOrder(root);
}
//中序遍历
void inOrder()const {
inOrder(root);
}
//后序遍历
void postOrder()const {
postOrder(root);
}
//插入值为value的节点
void insert(const T &value) {
insert(root, value);
}
//查找最小值
Node<T>* getMin()const {
return getMin(root);
}
//查找最大值
Node<T>* getMax()const {
return getMax(root);
}
//返回value的节点
Node<T>* search(const T &value)const {
Node<T>* rt = root;
while (rt&&rt->value != value) {
if (value < rt->value)rt = rt->left;
else rt = rt->right;
}
return rt;
}
//返回node的节点
Node<T>* search(const Node<T>* node)const {
return search(node->value);
}
//返回rt中序遍历的后继
Node<T>* getsuccessor(const Node<T>* rt)const {
if (rt == nullptr)return nullptr;
if (rt->right)return getMin(rt->right);
Node<T>* parent = rt->parent;
while (parent&&parent->right != rt) {
rt = parent;
parent = parent->parent;
}
return parent;
}
//返回rt中序遍历的前驱
Node<T>* getPredecessor(const Node<T>* rt)const {
if (rt)return nullptr;
if (rt->left) getMax(rt->left);
Node<T>* parent = rt->parent;
while (parent&&parent->left != rt) {
rt = parent;
parent = parent->parent;
}
return parent;
}
//删除值为value的节点
void remove(const T &value) {
Node<T>* z = search(value);
if (z == nullptr)return;
Node<T>*parent = z->parent, *del = z;
if (z == nullptr)return;
//只有右子树
if (z->left == nullptr) {
//删除节点为根节点
if (z == root) {
root = z->right;
if (root != nullptr)root->parent = nullptr;
}
else if (z == parent->left)parent->left = z->right;
else parent->right = z->right;
}
//只有左子树
else if (z->right == nullptr) {
//删除节点为根节点
if (z == root) {
root = z->right;
if (root != nullptr)root->parent = nullptr;
}
else if (z == parent->left)parent->left = z->left;
else parent->right = z->left;
}
else {
//找到右子树的的最小值，也就是中序遍历的后继结点
Node<T>* t = getMin(z->right), *parent = t->parent;
del = t;
z->value = t->value;
if (parent->left == t)parent->left = t->right;
else parent->right = t->right;
}
delete del;
}
};
int main() {
BST<int> test;
test.insert(50);
test.preOrder();
cout << endl;
test.inOrder();
cout << endl;
test.postOrder();
cout << endl;
cout << test.getMin()->value << endl;
cout << test.getMax()->value << endl;
test.remove(50);
test.preOrder();
cout << endl;
test.inOrder();
cout << endl;
test.insert(50);
test.insert(30);
test.insert(20);
test.insert(40);
test.insert(35);
test.insert(32);
test.insert(80);
test.insert(90);
test.insert(85);
test.insert(88);
test.preOrder();
cout << endl;
test.inOrder();
cout << endl;
return 0;
}
文章最后发布于: 2018-09-15 23:08:50
相关阅读
1、wildcard : 扩展通配符2、notdir ： 去除路径3、patsubst ：替换通配符例子：建立一个测试目录，在测试目录下建立一个名为sub的子目录
最近在学习通过墓碑文件定位bug所在位置，网上浏览了很多的博客，大多数只能做到利用addr2line定位到行号 但是对于大型项目，尤其是C++
1.找到hosts文件，在里面加两句话，激活后可注释掉，或删除 0.0.0.0 account.jetbrains.com 0.0.0.0 www.jetbrains.com 2.激活码 Y
js字符串截取函数slice()、substring()、substr()
原文地址为：js字符串截取函数slice()、substring()、substr()摘要在js中字符截取函数有常用的三个slice()、substring()、substr()
在android开发过程中，不可避免的会出现apk崩溃的问题，apk崩溃出现java层时可以被java层捕获，native层崩溃时系统同样会打印出崩溃信