44. 二叉搜索树
定义：【比它（当前根节点）小的放左边，比它（当前根节点）大的放右边】
- 普通二叉搜索树的中序遍历，就是从小到大的排序 （解决了 数据排序）
能快速找到最大值，最小值，能找到排名第一，第二的数据。搜索快。 - 删除
当左右两节点都不为空的情况下，左和右放上去都不行
从左边找最大值来替代，或者从右边找最小值 - 下次（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
