BST二叉排序树C++实现

BST二叉排序/查找/搜索树C++实现

实现代码

/*
author : eclipse
email  : eclipsecs@qq.com
time   : Thu May 07 10:28:33 2020
*/
#include<bits/stdc++.h>
using namespace std;struct Node {int data;Node *left;Node *right;Node(int value) : data(value), left(NULL), right(NULL) {}Node(int value, Node* l, Node* r) : data(value), left(l), right(r) {}
};class BST {
private:Node* root;void inOrderTraverse(Node* p);//中序遍历得到递增序列void reverseInOrderTraverse(Node *p);//“逆”中序遍历得到递减序列，先遍历右子树再遍历左子树
public:BST();Node* search(int value);void insert(int value);void del(int value);void incrementalSequence();void decreasingSequence();
};Node* BST::search(int value) {// 搜索，返回结点指针Node *p = root;while (p && p->data != value) {p = (value > p->data ? p->right : p->left);}return p;
}void BST::insert(int value) {Node *parent = NULL;Node *p = root;while (p) {parent = p;if (value == p->data) {// 若插入值value已经存在于BST中printf("The element has exist!\n");return;} else {//若插入值value大于当前值到右子树寻找//若插入值value小于当前值到左子树寻找p = (value > p->data ? p->right : p->left);}}if (parent == NULL) {//若父结点为NULL，树为空树，创建根结点并赋值root = new Node(value);} else if (value < parent->data) {//若为关键字小于父结点关键字，为左孩子，原左子树值必然比新插入结点关键字小，为新插入结点左子树parent->left = new Node(value, parent->left, NULL);} else if (value > parent->data) {//若为关键字小于父结点关键字，为右孩子，原右子树值必然比新插入结点关键字大，为新插入结点右子树parent->right = new Node(value, NULL, parent->right);}
}void BST::del(int value) {Node *parent = NULL;Node* p = root;while (p && p->data != value) {parent = p;p = (value > p->data ? p->right : p->left);}if (!p) {//若未找到return;} else if (!p->left && !p->right) {//若该节点为叶节点，直接删除if (parent->left == p) {parent->left = NULL;} else {parent->right = NULL;}delete p;} else if (p->left && !p->right) {//若该节点仅存在左子树，将该节点左子树作为欲删除结点父结点的左/右子树if (parent->left == p) {parent->left = p->left;} else {parent->right = p->left;}delete p;} else if (!p->left && p->right) {//若该节点仅存在右子树，将该节点右子树作为欲删除结点父结点的左/右子树if (parent->left == p) {parent->left = p->right;} else {parent->right = p->right;}delete p;} else {//若该节点同时拥有左右子树//取得左子树最大值或右子树最小值//右子树最大值比左子树的所有节点值大，比右子树出它以外所有值小，符合BST的要求//左子树最大值比右子树的所有节点值大，比左子树出它以外所有值大，符合BST的要求//右子树中，递归查找左子树到底可以得到右子树最小值，中序遍历的第一个节点//左子树中，递归查找右子树到底可以得到左子树最大值，“逆”中序遍历的第一个节点//下面采用右子树最小值Node *q = p->right;Node *parentQ = p;while (q->left) {parentQ = q;q = q->left;}p->data = q->data;if (parentQ->left == q) {parentQ->left = q->right;} else {parentQ->right = q->right;}delete q;}
}BST::BST() {root = NULL;
}void BST::incrementalSequence() {inOrderTraverse(root);
}void BST::inOrderTraverse(Node *p) {//中序遍历得到递增序列if (!p) {return;}inOrderTraverse(p->left);printf("%d ", p->data);inOrderTraverse(p->right);
}void BST::decreasingSequence() {reverseInOrderTraverse(root);
}void BST::reverseInOrderTraverse(Node *p) {//“逆”中序遍历得到递减序列，先遍历右子树再遍历左子树if (!p) {return;}reverseInOrderTraverse(p->right);printf("%d ", p->data);reverseInOrderTraverse(p->left);
}int main(int argc, char const *argv[])
{BST binarySearchTree;int N;scanf("%d", &N);for (int i = 0; i < N; i++) {int value;scanf("%d", &value);binarySearchTree.insert(value);}printf("Incrementail sequence:\n");binarySearchTree.incrementalSequence();printf("\n");printf("Delete elements:");int value;scanf("%d", &value);binarySearchTree.del(value);printf("Incrementail sequence:\n");binarySearchTree.incrementalSequence();printf("\nDecrease sequence:\n");binarySearchTree.decreasingSequence();printf("\nSearch value:");scanf("%d", &value);printf("Search %d", binarySearchTree.search(value)->data);return 0;
}

输入数据

10
10 24 88 20 5 8 4 99 90 9
10
24

输出数据

10
10 24 88 20 5 8 4 99 90 9
Incrementail sequence:
4 5 8 9 10 20 24 88 90 99
Delete elements:10
Incrementail sequence:
4 5 8 9 20 24 88 90 99
Decrease sequence:
99 90 88 24 20 9 8 5 4
Search value:24
Search 24

二叉排序树

  • 简介
    BST，二叉排序树（Binary Sort Tree），也称二叉查找（排序）树（Binary Search Tree）
  • 定义
    递归地，或者是一棵空树，或者是具有下列性质的二叉树：
  1. 若左子树非空，则左子树上所有结点的关键字均小于它的根结点的值；
  2. 若右子树非空，则右子树上所有结点的关键字均大于它的根结点的值；
  3. 左、右子树本身也分别为二叉排序树；
  4. 二叉排序树中所有结点关键字唯一
  • 实现
    实现的思路和重要代码部分在上述实现中已详细注释
  • 时间复杂度
    搜索、插入、删除时间复杂度为O(lgn)，n为BST结点总数

样例图解

  • BST
  • 删除关键字为10的节点后

最后

  • 最坏情况下，即二叉树构造输入序列为有序，会形成一个单支树，深度为BST中结点总数，时间复杂度为O(n)，此时BST性能显著降低，时间复杂度取决于BST的深度
  • 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！