搜索二叉树
搜索二叉树
搜索二叉树：节点的左子树比自己小，右子树比自己大
搜索一个值：如果比自己小就去左子树上找，如果比自己大就去右子树上找
如何建立搜索二叉树：先询问，比根节点小就往左子树上找，比根节点大就往右子树上找，找到不能再找就说明找到正确位置，找到正确位置之后往上挂
最复杂的是删除操作， (替换函数)：以下替代节点就用newnode代替,被替代的节点就用node代替 一个节点（newnode）彻底代替另一个节点(node)，若要替的节点没有父节点说明该节点为根节点，直接让要替代的节点为根节点就行,如果node不为根节点，node为node父节点的左孩子，则让node的父节点的左孩子指向newnode，node为node父节点的右孩子，则让node的父节点的右孩子指向newnode，再将newnode的父指针指向node的父指针，返回newnode.
- 若删除的节点没有左孩子，删除节点后让右孩子占据我原本的位置即可，即用替换函数让我的右孩子替换我，如果没有右孩子，删除节点后让左孩子占据我的位置即可，用替换函数让我的左孩子要替换我
- 若删除的节点即有左孩子又有右孩子，找到我的后继节点（即我的右子树上最左的节点同时也是我的右子树上最小的节点也就是最接近我的节点）来替我，而且我右子树上最左的节点一定是没有左子树，可能有右子树的，newnode原本没有左子树，替代我之后，直接把我的左子树挂到newnode的左子树上，如果newnode有右子树则将newnode的右子树挂到newnode的父节点的左子树（即原本newnode的位置），替代我之后的newnode的右子树就挂上我的右子树 具体过程:让我的后继节点newnode出来，让newnode的右孩子占据newnod的位置，newnode出来
- 若我的后继节点就是我的右孩子，为了不错乱，直接让右孩子代替我的位置 具体过程：让我的右孩子的右孩子替换我的右孩子，右孩子出来在接替我
两个具体过程的最后：彻底接管我的环境，将原本我的左右孩子的父节点指向newnode
有一种简单的替换的操作是找到我的后继节点之后直接将我的值和我后继节点的值互换，这样一来我的环境没有动，只需要将我的后继节点的环境改一下，省了一步改变删除我后转移我的环境的操作，如果newnode有右孩子，只需将newnode的右孩子挂到Newnode的父节点的左孩子上即可。下面的演示代码采用这种形式
#include<iostream>
#include<stdlib.h>
#include"assert.h"
using namespace std;
typedef int DataType;
typedef struct BSTreeNode
{
struct BSTreeNode *_left;
struct BSTreeNode *_right;
DataType _data;
}BSTreeNode;
//树节点的创建
BSTreeNode *BuyTreeNode(DataType x) //创建节点
{
BSTreeNode *node = (BSTreeNode*)malloc(sizeof(BSTreeNode));
assert(node); // 申请内存失败则退出
node->_data = x; //初始化节点
node->_left = NULL;
node->_right = NULL;
return node;
}
//二叉树的插入操作，非递归代码，插入成功返回0，失败返回-1
int BSTreeNodeInsert(BSTreeNode *pptree,DataType x) //搜索树的插入
{
BSTreeNode *parent = NULL;
BSTreeNode *cur = pptree;
if (pptree == NULL)
{
pptree = BuyTreeNode(x); //为空则创建为根节点
return 0;
}
while (cur) //寻找该插入的位置
{
parent = cur;
if (cur->_data > x)
cur = cur->_left; //要插入的小往左找
else if (cur->_data < x) //要插入的大往右找
cur = cur->_right;
else //已存在,插入失败
return -1;
}
//已找到要插入的位置
if (parent->_data > x)
parent->_left = BuyTreeNode(x); //创建节点并插入
else
parent->_right = BuyTreeNode(x);
return 0;
}
//二叉树的插入递归代码
/*int BSTreeNodeInsertR(BSTreeNode **tree,DataType x) //搜索树的插入
{
if(*tree == NULL)
{
*tree = BuyTreeNode(x);
return 0;
}
if ((*tree)->_data > x)
return BSTreeNodeInsertR(&(*tree)->_left,x);
else if ((*tree)->_data < x)
return BSTreeNodeInsertR(&(*tree)->_right,x);
else
return -1;
}*/
//二叉树的查找操作非递归 找到返回地址，找不到返回0
BSTreeNode *BSTreeNodeFind(BSTreeNode *tree,DataType x) //查找
{
while (tree)
{
if (tree->_data == x) //返回地址
return tree;
else if (tree->_data < x) //大了往右找
tree = tree->_right;
else
tree = tree->_left; //小了往左找
}
return NULL;
}
//二叉树的查找递归
/*BSTreeNode *BSTreeNodeFindR(BSTreeNode *tree,DataType x) //查找
{
if (!tree)
return NULL;
if (tree->_data > x)
BSTreeNodeFindR(tree->_left,x);
else if (tree->_data < x)
BSTreeNodeFindR(tree->_right,x);
else
return tree;
}*/
//二叉树的删除操作
int BSTreeNodeDel(BSTreeNode *tree,DataType x) //删除
{
BSTreeNode *cur = tree;
BSTreeNode *parent = tree;
BSTreeNode *del = NULL;
while (cur) //此循环寻找要删除值所在的节点，cur代表要删除的节点，parent代表cur的父节点
{
if (cur->_data > x)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_data < x)
{
parent = cur;
cur = cur->_right;
}
else //此时代表已找到要删除的节点
{
del = cur;
if (cur->_left == NULL) //1、左孩子为空
{
if (parent->_left == cur) //cur为父节点的左孩子
parent->_left = cur->_right; //cur的父节点的左孩子直接指向cur的右孩子
else if (parent->_right == cur)//cur为父节点的右孩子
parent->_right = cur->_right;//cur的父节点的右孩子直接指向cur的右孩子
else if (parent == cur) //没有父亲节点时，即cur为根节点
tree = parent->_right;//cur的右节点根节点指向cur的右孩子
}
else if (cur->_right == NULL) //2、右孩子为空
{
if (parent->_left == cur)//cur为父节点的左孩子
parent->_left = cur->_left;//cur的父节点的左孩子直接指向cur的左孩子
else if (parent->_right == cur)//cur为父节点的右孩子
parent->_right = cur->_left;//cur的父节点的右孩子直接指向cur的左孩子
else if (parent == cur) ////没有父亲节点时，即cur为根节点
tree = parent->_left;//cur的右节点根节点指向cur的左孩子
}
else//3、左右孩子都不为空
{
BSTreeNode *sub = cur->_right;
while (sub->_left) //此循环找cur的后继节点
{
parent = sub;//parent表示newnode 的父节点
sub = sub->_left; sub表示newnode
}
del = sub;
cur->_data = sub->_data; //直接互换值
if (parent->_left == sub) //sub为parent的左孩子
parent->_left = sub->_right;//sub的右孩子连到parent的左孩子上
else //sub为parent的右孩子
parent->_right = sub->_right;//sub的右孩子连到parent的右孩子上
}
free(del); //释放del指针
del = NULL;
return 0;
}
}
return -1;
}
//中序打印二叉树
void print(BSTreeNode *root){
if (root == NULL){
return;
}
if(root){
print(root->_left);
cout<<root->_data<<endl;
print(root->_right);
}
}
int main(){
BSTreeNode *root = BuyTreeNode(10);
BSTreeNodeInsert(root,5);
BSTreeNodeInsert(root,6);
BSTreeNodeInsert(root,3);
BSTreeNodeInsert(root,15);
BSTreeNodeInsert(root,17);
BSTreeNodeInsert(root,8);
BSTreeNodeInsert(root,12);
BSTreeNodeInsert(root,30);
BSTreeNodeFind(root,17);
print(root);
cout<<BSTreeNodeDel(root,17)<<endl;
BSTreeNodeFind(root,17);
cout<<"=============="<<endl;
print(root);
}
