数据结构-树和二叉树（五）二叉排序树

二叉排序树🚉

二叉排序树，又称二叉查找树（ BST， Binary Search Tree）
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

1. 左子树上所有结点的关键字均小于根结点的关键字；

2. 右子树上所有结点的关键字均大于根结点的关键字。

3. 左子树和右子树又各是一棵二叉排序树。

4. 左子树结点值 < 根结点值 < 右子树结点值

5. 进行中序遍历，可以得到一个递增的有序序列

1 代码实现

//
// Created by Wang on 2021/8/23.
//
#include <iostream>
#include <string>
using namespace std;
typedef struct  BSTNode{
    int value;
    struct BSTNode *lChild, *rChild;
}BSTNode, *BSTree;

/**
 * 非递归插入
 * @param T
 * @param e
 * @return
 */
void InsertBST(BSTree &T,int e) {
    auto *newNode = (BSTNode *)malloc(sizeof(BSTNode));
    if (T == nullptr) {
        newNode->value = e;
        newNode->lChild = nullptr;
        newNode->rChild = nullptr;
        T = newNode;
        return;
    }
    BSTNode *p = T, *parent = nullptr;

    while (p != nullptr) {
        if (p->value == e) {
            cout << e << "值已存在" << endl;
            return;
        }
        parent = p;
        if (parent->value > e) {
            p = p->lChild;
        }else {
            p = p->rChild;
        }
    }
    newNode->value = e;
    newNode->rChild = nullptr;
    newNode->lChild = nullptr;
    if (parent->value > e) {
        parent->lChild = newNode;
    }else {
        parent->rChild = newNode;
    }
    return;
}

/**
 * 递归插入
 * @param T
 * @param e
 * @return
 */
void RecursionInsertBST(BSTree &T, int e) {
    auto *newNode = (BSTNode *)malloc(sizeof(BSTNode));
    if (T == nullptr) {
        newNode->value = e;
        newNode->lChild = nullptr;
        newNode->rChild = nullptr;
        T = newNode;
        return;
    }
    else if (T->value == e) {
        cout << e << "值已存在" << endl;
        return;
    } else if (e > T->value) {
        return RecursionInsertBST(T->rChild, e);
    }else {
        return RecursionInsertBST(T->lChild, e);
    }
}

/**
 * 构造二叉排序树
 * @param T
 * @param str
 * @param n
 * @return
 */
bool CreatBST(BSTree &T, int str[], int n) {
    T = nullptr;
    int i = 0;
    while (i < n) {
        InsertBST(T, str[i]);
//      RecursionInsertBST(T, str[i]);
        i++;
    }
}

/**
 * 非递归查找
 * @param T
 * @param e
 * @return
 */
BSTNode *SearchBST(BSTree T, int e) {
    while (T != nullptr && e != T->value) {
        if (e < T->value) {
            T = T->lChild;
        }else
            T = T->rChild;
    }
    return T;
}

/**
 * 递归查找
 * @param T
 * @param e
 * @return
 */
BSTNode *RecursionSearchBST(BSTree T, int e) {
    if (T == nullptr) {
        return nullptr;
    }
    if (e == T->value) {
        return T;
    }else if (e < T->value) {
        return RecursionSearchBST(T->lChild, e);
    }else {
        return RecursionSearchBST(T->rChild, e);
    }
}

/**
 * 查找子树最小值结点即，父节点的直接后继结点
 * @param T
 * @return
 */
BSTNode *SearchMin(BSTree T) {
    while (T->lChild != nullptr) {
        T  = T->lChild;
    }
    return T;
}
/**
 * 删除
 * @param T
 * @param e
 * @return
 */
bool DeleteBST(BSTree &T, int e) {
    if (T == nullptr) {
        return false;
    }
    BSTNode *p = T;
    BSTNode *parent = nullptr;
    int tag = 0; //左子树0，右子树1
    while (p != nullptr && e != p->value) {  //寻找要删除的结点
        parent = p; //得其父节点
        if (e < T->value) {
            p = p->lChild;
            tag = 0;
        }
        else {
            p = p->rChild;
            tag = 1;
        }
    }
    if (p->rChild == nullptr && p->lChild == nullptr) { //左右子树为空，
        if (tag == 0) {
            parent->lChild = nullptr;
        } else {
            parent->rChild = nullptr;
        }
        free(p);
    }else if (p->rChild == nullptr && p->lChild != nullptr) { //右子树为空
        if (tag == 0) {
            parent->lChild = p->lChild;
        } else {
            parent->rChild = p->lChild;
        }
        free(p);
    }else if (p->rChild != nullptr && p->lChild == nullptr) { //左子树为空
        if (tag == 0) {
            parent->lChild = p->rChild;
        } else {
            parent->rChild = p->rChild;
        }
        free(p);
    }else { // 左右子树均不为空
        if (tag == 0) {
            BSTNode *t = SearchMin(p->lChild); //寻找p结点右子树的最小结点
            int tValue = t->value;
            DeleteBST(T, t->value); //删除最小结点
            p->value = tValue; //将此结点替换到删除结点

        } else {
            BSTNode *t = SearchMin(p->rChild);
            int tValue = t->value;
            DeleteBST(T, t->value); //删除最小结点
            p->value = tValue;
        }
    }
}

/**
 * 中序遍历
 * @param root
 */
void InOrderTraversal(BSTree root) {
    if (root == nullptr) {
        return;
    }
    InOrderTraversal(root->lChild);
    cout << root->value << "->";
    InOrderTraversal(root->rChild);
}

int main() {
    BSTree T;
    T = (BSTree)malloc(sizeof(BSTNode));
    int arr[] = {54, 20, 66, 40, 28, 58, 79};
    int len = sizeof(arr) / sizeof(arr[0]);
    cout << "创建二叉排序树" << endl;
    CreatBST(T, arr, len);
    cout << "中序遍历" << endl;
    InOrderTraversal(T);
    printf("\n");
    cout << "查找20子树" << endl;
    InOrderTraversal(SearchBST(T, 20));
    printf("\n");
    cout << "删除结点20" << endl;
    DeleteBST(T, 20);
    InOrderTraversal(T);
    printf("\n");
    return 0;
}

创建二叉排序树
中序遍历
20->28->40->54->58->66->79->
查找20子树
20->28->40->
删除结点20
28->40->54->58->66->79->

2、查找效率分析

查找长度——在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度

若树高h， 找到最下层的一个结点需要对比 h 次

最好情况： n个结点的二叉树最小高度为[log2n] + 1。平均查找长度 = O(log2n)

最坏情况：每个结点只有一个分支，树高 h = 结点数n。 平均查找长度 = O(n)