二叉搜索树（来学包会） C++经验+1

目录

什么是二叉搜索树

解二叉搜索树

二叉搜索树的操作

二叉搜索树的插入（三步走）

二叉搜索树的搜索

二叉搜索树的删除

1.删除的节点是叶子节点 

2.删除的节点只有一边的子树

3.删除的节点左子树和右子树都有

详细完整代码

---

什么是二叉搜索树

二叉树都知道，二叉搜索树就是：每个节点的左子树的值全都小于当前节点的值，右子树的值全都大于当前节点的值。

要这个树有什么用？

1.二叉搜索树的中序遍历是有序的。

2.顾名思义就是为了搜索，线性遍历搜索一个值是全部走一遍，而对于二叉搜索树而言，每走一次就能排除一半的结果。所以就是快。当然也会出现一些特例，如下图所示

如果一开始插入的数比后面的数都大，那就变成了一串的。如果这样来搜索，和线性遍历也没区别了，所以后面开发出了AVL树和红黑树解决。

注意：二叉搜索树的值是不能被更改的！！！！（因为更改就会破坏当前的结构），比如本来2的节点你改为10，那结构就被破坏了。

解二叉搜索树

二叉搜索树是怎么插入的。插入节点后，节点的位置就不会改变了，新来的节点往下延升。

和二叉树一样就是一个递归的过程：

1.递归时判断当前节点的数值和新加入节点的数值。比较后决定向那边递归，直到找到一个空位置，这时节点就和前一个节点连接即可。

2.二叉搜索树的中序遍历是有序的。1 2 3 4 5 6 7 8 9

二叉搜索树的操作

二叉搜索树的插入（三步走）

void insert(int key)
{//定义一个临时指针 用于移动Node* temp = root;//方便移动 以及 跳出循环Node* prev = NULL;//定位到待插入位置的前一个结点//循环的比较直到空为止while (temp != NULL){prev = temp;if (key < temp->data){temp = temp->left;}else if(key > temp->data){temp = temp->right;}else{return;}}//这一步创造节点，并且将节点与前一个节点连接。if (key < prev->data){prev->left = (Node*)malloc(sizeof(Node));prev->left->data = key;prev->left->left = NULL;prev->left->right = NULL;}else{prev->right = (Node*)malloc(sizeof(Node));prev->right->data = key;prev->right->left = NULL;prev->right->right = NULL;}
}

 第一步：定义变量，变量tmp 用来找位置 变量prev 用来记录前面一个节点（方便新节点）

 第二步：循环（递归）找位置，个子高的和个子矮的要分边站才整齐。

 第三步：根据传入的值创造新节点并与前一个节点连接。

二叉搜索树的搜索

/*查找元素key*/
bool search(Node* root, int key)
{while (root != NULL){if (key == root->data)return true;else if (key < root->data)root = root->left;elseroot = root->right;}return false;
}

代码很简单，判断大小，循环向下，找到位置 

描述一遍找1 的过程。

我们进来先看到的5，然后1 比 5小，所以走左边，1比4小，走左边，1比2小，走左边。

完了，完全没难度的。 

总结一下：虽然这里和线性遍历相比只是少走了一次3.但是这只是在这么短的一棵树上，如果这个树特别深，每次少走一个分支，就等于少走了一半。

二叉搜索树的删除

这里分三种情况：1.删除的节点是叶子节点 2.删除的节点只有一边 3.删除的节点左右都有

1.删除的节点是叶子节点 

这个没啥好说的，直接删除就行了。单身的结果

2.删除的节点只有一边的子树

 这种情况如果你是父节点的右子树，你的子节点一定都是大于你的父节点的。此时只有一边的子树。直接让子节点把你换掉即可，因为你的子树已经保证了，它是遵循二叉搜索树规则的。所以你走掉后，子节点顶替上就好了。

3.删除的节点左子树和右子树都有

前面说二叉搜索树的中序遍历是有序的。那我们删除一个节点后是不能影响其有序性的。

如图我们要删除节点5，我们此时的顺序是  

如果要在不影响有序的前提下，5的位置，可以给4 或者 给6.此时就可以得出结论了。可以让4作为根节点或者让6作为根节点。（这个选择可以根据自己喜好来设计）

怎么得到能找到4 和 6其中一个呢？

很简单，我们的4 节点其实就是左子树中最大的（左子树的最右节点）。6节点就是右子树中最小的（右子树的最左节点）。

接下来就是遍历的过程了：如果要找左子树最大的，我们就从左孩子开始，而不是从本节点开始，（因为我们是要找左子树中最大的节点）然后就一直遍历右子树知道为空，为空说明上次遍历的节点就是左子树中最大的

int delete_node(Node* node, int key)
{if (node == NULL){return -1;}else{if (node->data == key){//当我执行删除操作 需要先定位到删除结点的前一个结点（父节点）Node* tempNode = prev_node(root, node, key);Node* temp = NULL;//如果右子树为空，只需要重新连接结点（包含叶子结点），直接删除if (node->right == NULL){temp = node;node = node->left;/*判断待删除结点是前一个结点的左边还是右边*/if (tempNode->left->data == temp->data){Node* free_node = temp;tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;tempNode->right = node;free(free_node);free_node = NULL;}}else if (node->left == NULL){temp = node;node = node->right;if (tempNode->left->data == temp->data){Node* free_node = temp;tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;/tempNode->right = node;free(free_node);free_node = NULL;}}else//左右子树都不为空{temp = node;/*往左子树 找最大值*/Node* left_max = node;//找最大值的临时指针left_max = left_max->left;//先到左孩子结点while (left_max->right != NULL) {temp = left_max;left_max = left_max->right;}node->data = left_max->data;if (temp != node){temp->right = left_max->left;free(left_max);left_max = NULL;}else{temp->left = left_max->left;free(left_max);left_max = NULL;}}}else if(key < node->data){delete_node(node->left, key);}else if (key > node->data){delete_node(node->right, key);}}
}

 代码解析：

1.如果这棵树是存在的，我们先递归查找要删除的节点（比大小）。

2.找到节点后判断是上述3种的那种情况。根据情况写出代码。

 总结：单身汉没人继承，只有一个孩子独生子继承，有两个孩子找最亲近的继承。

详细完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct SortTree {int data;//存放数据的数据域struct SortTree* left;//指针域 左指针struct SortTree* right;//指针域 右指针
}Node;
/*全局变量*/
Node* root;//根节点void Init(int);//初始化操作
void insert(int);//插入操作
void show(Node*);
int delete_node(Node*, int);
Node* prev_node(Node*, Node*, int);
bool search(Node* root, int key);
int main()
{Init(8);insert(4);insert(2);insert(5);insert(10);insert(9);insert(13);show(root);delete_node(root, 8);delete_node(root, 13);printf("\n");show(root);
}/*初始化根节点
int key : 根节点的值
*/
void Init(int key)
{root = (Node*)malloc(sizeof(Node));root->data = key;root->left = NULL;root->right = NULL;
}void insert(int key)
{//定义一个临时指针 用于移动Node* temp = root;//方便移动 以及 跳出循环Node* prev = NULL;//定位到待插入位置的前一个结点while (temp != NULL){prev = temp;if (key < temp->data){temp = temp->left;}else if(key > temp->data){temp = temp->right;}else{return;}}if (key < prev->data){prev->left = (Node*)malloc(sizeof(Node));prev->left->data = key;prev->left->left = NULL;prev->left->right = NULL;}else{prev->right = (Node*)malloc(sizeof(Node));prev->right->data = key;prev->right->left = NULL;prev->right->right = NULL;}
}void show(Node* root)
{if (root == NULL){return;}show(root->left);printf("%d ", root->data);show(root->right);
}
/*查找元素key*/
bool search(Node* root, int key)
{while (root != NULL){if (key == root->data)return true;else if (key < root->data)root = root->left;elseroot = root->right;}return false;
}
int delete_node(Node* node, int key)
{if (node == NULL){return -1;}else{if (node->data == key){//当我执行删除操作 需要先定位到前一个结点Node* tempNode = prev_node(root, node, key);Node* temp = NULL;/*如果右子树为空 只需要重新连接结点叶子的情况也包含进去了 直接删除*/if (node->right == NULL){temp = node;node = node->left;/*为了判断 待删除结点是前一个结点的左边还是右边*/if (tempNode->left->data == temp->data){Node* free_node = temp;//释放用的指针tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;//释放用的指针tempNode->right = node;free(free_node);free_node = NULL;}}else if (node->left == NULL){temp = node;node = node->right;if (tempNode->left->data == temp->data){Node* free_node = temp;//释放用的指针tempNode->left = node;free(free_node);free_node = NULL;}else{Node* free_node = temp;//释放用的指针tempNode->right = node;free(free_node);free_node = NULL;}}else//左右子树都不为空{temp = node;/*往左子树 找最大值*/Node* left_max = node;//找最大值的临时指针left_max = left_max->left;//先到左孩子结点while (left_max->right != NULL) {temp = left_max;left_max = left_max->right;}node->data = left_max->data;if (temp != node){temp->right = left_max->left;free(left_max);left_max = NULL;}else{temp->left = left_max->left;free(left_max);left_max = NULL;}}}else if(key < node->data){delete_node(node->left, key);}else if (key > node->data){delete_node(node->right, key);}}
}
/*定位到待删除节点的前一个结点
Node* root 从根节点开始
Node* node 待删除的结点
int key 待删除数据
*/
Node* prev_node(Node* root, Node* node, int key)
{if (root == NULL || node == root){return node;}else{if (root->left != NULL && root->left->data == key){return root;}else if(root->right != NULL && root->right->data == key){return root;}else if (key < root->data){return prev_node(root->left, node, key);}else{return prev_node(root->right, node, key);}}
}