| 二叉排序树习题 |
|---|
| 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，返回0
return 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);
}
}
}
