44. 二叉搜索树

定义：【比它（当前根节点）小的放左边，比它（当前根节点）大的放右边】

1. 普通二叉搜索树的中序遍历，就是从小到大的排序 （解决了 数据排序）
   能快速找到最大值，最小值，能找到排名第一，第二的数据。搜索快。
2. 删除
   当左右两节点都不为空的情况下，左和右放上去都不行
   从左边找最大值来替代，或者从右边找最小值
3. 下次（AVL）下周六
   致命的弱点，接近排好序的数据，查找时会退化成 0(N)
   找资料（google）
   左旋，右旋，先左旋后右旋，先右旋后左旋

二叉搜索树，折半查找，O(logN)的级别。
致命的弱点，对与接近排序的数据，查找时 会退化成O(N)级别。
进而衍生出AVL树，两端均衡。

1.二叉搜索树-新增

2.二叉搜索树-查找

3.二叉搜索树-搜索

#include <jni.h>
#include <string>
#include "BST.hpp"
#include <android/log.h>

// 传入回调函数
void visit(int key, int value) {
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "key = %d , value = %d", key, value);
}

extern "C"
JNIEXPORT jstring
JNICALL
Java_com_darren_ndk_day44_MainActivity_stringFromJNI(
        JNIEnv *env,
        jobject /* this */) {

    BST<int, int> *bst = new BST<int, int>();
    bst->put(2, 2);
    bst->put(-11, -11);
    bst->put(-13, -13);
    bst->put(0, 0);
    bst->put(8, 8);
    bst->put(3, 3);
    bst->put(7, 7);

    bst->remove(2);
    bst->inOrderTraverse(visit); // 中序遍历
  
    int* value = bst->get(100);
    if(value !=null) {
        //...
    } 
       
    // __android_log_print(ANDROID_LOG_ERROR,"TAG","%d", bst->contains(100));
    // __android_log_print(ANDROID_LOG_ERROR,"TAG","%d", bst->contains(7));
    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}

// BST.hpp
#ifndef NDK_DAY44_BST_H
#define NDK_DAY44_BST_H
#include <iostream>

// c++   Map  MlitiMap  红黑树
// java Map 和 c++ Map 比较
template<class K, class V> // 两个泛型key,value
struct TreeNode {
public:
    TreeNode(TreeNode<K, V> *pNode) {
        this->left = pNode->left;
        this->right = pNode->right;
        this->key = key;
        this->value = value;
    }
    // 左右指针
    TreeNode<K, V> *left = NULL;
    TreeNode<K, V> *right = NULL;
   // 数据域
    K key;
    V value;

    TreeNode(K key, V value) {
        this->right = NULL;
        this->left = NULL;
        this->key = key;
        this->value = value;
    }
};

template<class K, class V>
class BST {
    TreeNode<K, V> *root;// 根节点
    int count; // 个数

public:
    BST() {
        root = NULL;
        count = 0;
    }
    ~BST() {
        // 大家自己去完成，delete所有节点。递归去delete。
    }

public:
// 新增 （key相等时 修改）
    void put(K key, V value) {
        root = addNode(root, key, value);
    }

    // 查找 （自己实现）
// 1.先判断是否包含，包含了再去查找,没包含不查找；
// 2.没找到返回V*, 没找到返回NULL。
    V *get(K key) {
        return NULL;
    }
    int size() {
        return count;
    }

    // 是否包含目标key，采用非递归方式实现(迭代)。
    bool contains(K key) {
        TreeNode<K, V> *node = root;
        while (node) {
            if (node->key == key) { // 找到了
                return node->value;
            } else if (node->key > key) { // 左子树中继续找
                node = node->left;
            } else { // 右子树中继续找
                node = node->right;
            }
        }
        return false;
    }

    // 删除 (最主要的内容)
    void remove(K key) {
        // 分情况解决
        root = removeNode(root, key);
    }

    // 中序遍历
    void inOrderTraverse(void (*fun)(K, V)) {
        inOrderTraverse(root, fun);
    }

private:
    // 返回一个节点 ，多去理解
    TreeNode<K, V> *addNode(TreeNode<K, V> *pNode, K key, V value) {
        if (pNode == NULL) {
            count++;
            return new TreeNode<K, V>(key, value); // 根节点
        }

        // 比较key
        if (pNode->key > key) {// 小：当前的key  大于插入的key，递归：插入到左边子树。
            pNode->left = addNode(pNode->left, key, value);
        } else if (pNode->key < key) { // 大，递归：插入到右子树中。
            pNode->right = addNode(pNode->right, key, value);
        } else { // 相等，更新value值
            pNode->value = value;
        }
        return pNode;
    }

    // 移除节点：重点代码，递归删除节点
    TreeNode<K, V> *removeNode(TreeNode<K, V> *pNode, K key) {
        if (pNode->key > key) { // 1.在左子树中递归删除
            pNode->left = removeNode(pNode->left, key);
        } else if (pNode->key < key) { //2. 在右子树中递归删除
            pNode->right = removeNode(pNode->right, key);
        } else { // 3.相等----关键代码
            count--;
            if (pNode->left == NULL && pNode->right == NULL) {
                // 3.1 左右叶子节点都为空，直接删除pNode节点
                delete pNode;
                return NULL; // 父节点的指向变成空。
            } else if (pNode->left == NULL) { // 3.2 左节点为空，有节点不为空
                TreeNode<K, V> *right = pNode->right; // 左边没有，把右边放上去。
                delete (pNode);
                return right;
            } else if (pNode->right == NULL) { // 3.3 右节点为空，左节点不为空
                TreeNode<K, V> *left = pNode->left; // 保存一下
                delete (pNode);
                return left;
            } else {
                // 3.4 左右两子树都不为空，最关键代码。要找一个节点来代替它。
                // 从左边找最大值来替代，或者从右边找最小值. 找前驱或后进。
                TreeNode<K, V> *successor = new TreeNode<K, V>(maximum(pNode->left)); // 左边的最大节点
                successor->left = deleteMax(pNode->left); 
                count++;  // 节点挪上来
                successor->right = pNode->right;
                delete (pNode);
                return successor;
            }
        }
        return pNode;
    }

    TreeNode<K, V> *deleteMax(TreeNode<K, V> *pNode) { // 删除最大值
        if (pNode->right == NULL) {
            TreeNode<K, V> *left = pNode->left;
            delete (pNode);
            count--;
            return left;
        }
        pNode->right = deleteMax(pNode->right);
        return pNode;
    }

    // 查找当前树的最大值(不断地往右边找，直到 右边为空就找到了 最大值) 
    // （最小值怎么找？），不断往左边找，
    TreeNode<K, V> *maximum(TreeNode<K, V> *pNode) {
        // 不断的往右边找，直到找到右子树为空节点
        if (pNode->right == NULL) {
            return pNode; // 找到了
        }
        return maximum(pNode->left); // 递归查找
    }

    // 中序遍历：递归
    void inOrderTraverse(TreeNode<K, V> *pNode, void (*pFunction)(K, V)) {
        if (pNode == NULL) { // 0.递归到底了，递归结束
            return;
        }
        inOrderTraverse(pNode->left, pFunction); // 1.遍历左边
        pFunction(pNode->key, pNode->value);    // 2.访问自身
        inOrderTraverse(pNode->right, pFunction); // 3.遍历右边
    }
};
#endif //NDK_DAY44_BST_H