C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解

二叉排序树习题
1.设计算法构建一棵二叉排序树(又称二叉搜索树BST)
2.查找二叉排序树中结点为x的结点所在的层数
3.删除二叉排序树T中值为x的结点
4.查找二叉排序树中所有小于key的关键字
5.编写算法，将一棵二叉树t分解成两棵二叉排序树t1和t2，使得t1中的所有结点关键字的值都小于x，t2中所有结点关键字的值都大于x
6.已知二叉排序树中每一个结点值为整型，采用二叉链表存储，编写算法删除二叉排序树中所有关键字小于x的结点

1.设计算法构建一棵二叉排序树(又称二叉搜索树BST)

二叉树搜索树的构建就是多个插入操作的重复使用，下面的代码并用二叉树的前序遍历检验插入结果。
二叉排序树，中序序列序列就变成了有序输出

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//二叉排序树的插入操作
void insertKey(BiTree &T,ElemType key)
{//if是根(子树根)节点的操作，else if是左右子树操作 根节点+左右子树的操作=问题的解if(T==NULL){BiTNode * p=(BiTNode *)malloc(sizeof(BiTNode));p->lchild=NULL;p->rchild=NULL;p->data=key;T=p;}else if(key<T->data)//如果key<当前结点{insertKey(T->lchild, key);}else if(key >T->data){insertKey(T->rchild, key);}
}BiTNode * creatBSTree()
{BiTNode *T=NULL;ElemType keyList[]={40,10,45,15};int keyListLength=4;for(int i=0;i<keyListLength;i++){insertKey(T, keyList[i]);}return T;
}void preOreder(BiTree T)
{if(T==NULL) return;printf("%d ",T->data);preOreder(T->lchild);preOreder(T->rchild);
}
int main()
{BiTree T=creatBSTree();preOreder(T);printf("\n");
}

2.查找二叉排序树中结点为x的结点所在的层数

我的思考？在上一节中，我们可以用层序遍历来完成这个事，但是那个是全部二叉树可用，这一次有什么区别
答：之前的二叉树要遍历完全部的结点，才能找到x。需要横着找
这次有序的寻找就不同了，是竖着找

int nodelevel=0;
int getNode(BiTree T,int x)
{if(T!=NULL){nodelevel++;if(x== T->data) return  nodelevel;else if(x<T->data){getNode(T->lchild, x);}else if(x>T->data){getNode(T->rchild, x);}}else nodelevel=0;//表明没有查到x，返回0return  nodelevel;
}

3.删除二叉排序树T中值为x的结点

找到值为x的结点，然后删除该点

我们这里以方法1为例子，右孩子，插入到左孩子的最大结点中
思路提炼：
关于存在两棵子树的时候，
找到左子树的最右子树（最大结点），它肯定没有右孩子，将待删除结点的右孩子变成它的右孩子，删掉待删除结点即可

void deleteopr(BiTree &T)
{//第一种情况，删除结点是根节点，第二种情况，只有一个子树，第三种情况，有两个子树if(T->lchild==NULL&&T->rchild==NULL){T=NULL;}else if(T->lchild!=NULL&&T->rchild!=NULL){BiTNode *pMax=T->lchild;while(pMax->rchild!=NULL){pMax=pMax->rchild;}pMax->rchild=T->rchild;BiTNode *p=T;T=T->lchild;free(p);}else         //只有一边有子树{//如果左边有子树if(T->lchild!=NULL){//记录被抛弃的结点的存储空间，用完它之后就给他free掉BiTNode *p=T;T=T->lchild;free(p);}else{BiTNode *p=T;T=T->rchild;free(p);}}
}
void delete_treeNode(BiTree &T,ElemType x)
{if(T->data==x){//删除这个结点，删除操作开始,否则的话，就继续往左右子树里寻找这个结点deleteopr(T);}else if(x<T->data){delete_treeNode(T->lchild, x);}else if(x>T->data){delete_treeNode(T->rchild, x);}
}

4.查找二叉排序树中所有小于key的关键字

思路:二叉排序树中序遍历是有序的，所以在中序遍历的过程中就能找到全部小于key的结点，中止中序遍历就行。

简单代码已省略

5.编写算法，将一棵二叉树t分解成两棵二叉排序树t1和t2，使得t1中的所有结点关键字的值都小于x，t2中所有结点关键字的值都大于x

思路：

6.已知二叉排序树中每一个结点值为整型，采用二叉链表存储，编写算法删除二叉排序树中所有关键字小于x的结点

错误思路：是以为找到某点小于x，就把它连同它的左子树全部删除，若它存在右子树，就让它右子树代替它。这种思路就漏解了，漏掉了小于结点的右子树中，仍可能存在小于x的结点。

明确使用哪种遍历？-使用前序遍历，因为根节点是划分区间的依据，只有使用前序遍历，我们才能够先拿到根结点。

void deleteFunc(BiTree &T) //删除一整棵树，先删除左子树，再删除右子树，最后删除根节点，就不用保存根节点的信息了
{if(T!=NULL){deleteFunc(T->lchild);deleteFunc(T->rchild);free(T);T = NULL; // 避免悬空指针，直接将T设为NULL，已经释放掉的指针}
}void preOrderTraversing(ElemType x,BiTree &T)
{//如果树不为空if(T!=NULL){if(T->data==x)  //如果当前正正好好，T的左子树小于x，T的右子树大于x，那么删除左子树即可{//deleteFunc(T->lchild);  //删除函数，删除了T的左孩子T->lchild=NULL;}else if(x>T->data) //如果当前x大于该结点，那么该结点的左孩子肯定都比x小，需要删除，右孩子中可能存在着小于x的值，所以右孩子要递归{//递归删除右子树preOrderTraversing(x,T->rchild);//删除左子树和根节点，这里注意删除根节点的时候，它可能存在右孩子，所以要让指针指向他的右孩子，我们保存根节点信息，直接让指针指向其右孩子BiTNode* p=T;T=T->rchild;p->rchild=NULL;   //右子树置空，为什么要把右子树置空，要切断它指针的联系，因为现在的右子树已经是新的根节点了，如果不把老的根节点的右子树置空，删除操作的时候，会把右子树也删除了//deleteFunc(p);  //删除根节点和它的左孩子}else if(x<T->data) //如果当前x小于该结点，那么该结点的右孩子肯定都比x大，左孩子中可能存在着小于x的值，所以左孩子要递归{//右子树不用管，处理它的左子树就行preOrderTraversing(x,T->lchild);}}
}