BST的删除操作删除数据为X的结点(1) 查找数据为X的结点free掉(2) 找顶替该结点的结点使满足BST的特点找替代结点x所在的结点的度为0(叶子结点)直接删除即可free(结点)该位置置空。x所在的结点的度为1(该节点只有一个孩子)找到这个结点并删除让其唯一的一个孩子代替该结点的位置。x所在结点的度为2可以用右子树中在最靠左的结点 或者 左子树中最靠右的结点 来代替该结点的位置同一颗树的删除规则必须统一。代码思路找到该节点把其数据域改为 左子树中最靠右的结点 / 右子树中最靠左的节点对其左子树进行递归删除左子树中最靠右的结点情况1可以看作情况2的特殊情况即认为叶子结点的孩子为NULL让NULL顶替要删除结点的位置所以只需要一份代码即可。总结度为0的情况可以看作度为1的情况递归思路原问题在以root为根的树中删除数据k范围缩小左子树 / 右子树if(root-data k),问题转化为 在以root-left为根的子树中删除数据kif(root-data k),问题转化为 在以root-right为根的子树中删除数据kif(root-data k)root结点就是要删除的结点1. 判断root的度 判断左右孩子存在不存在即可2. 度为2左右孩子都存在root左子树中最靠右的结点p root-data p-data 问题转化为在root-left为根的子树中删除数据p-data3. 度为0/度为1只要左孩子不存在那么就认为右孩子一定存在if(root-left!NULL){chroot-left;//一定是度为1的情况}else{chroot-right//有可能度为1有可能度为0}free(root);returnch;//带return所以就不用去找父亲结点的位置完整代码#includestdio.h#includestdlib.htypedefstructBTNode{intdata;structBTNode*left;structBTNode*right;}BTNode,*BTree;inta[100];//存数据BTreeinitBST(intdata){BTree root(BTNode*)malloc(sizeof(BTNode));if(rootNULL){printf(内存分配失败\n);returnNULL;}root-datadata;root-leftNULL;root-rightNULL;returnroot;}voidinsert(BTree root,intdata){if(rootNULL){printf(树空\n);return;}BTNode*newNode(BTNode*)malloc(sizeof(BTNode));if(newNodeNULL){printf(内存分配失败\n);return;}newNode-datadata;newNode-leftNULL;newNode-rightNULL;BTNode*curroot;BTNode*preNULL;while(cur!NULL){if(cur-datadata){precur;curcur-left;}else{precur;curcur-right;}}if(pre-datadata){pre-leftnewNode;}else{pre-rightnewNode;}}voidinOrdered(BTree root){if(rootNULL)return;if(root-left!NULL)inOrdered(root-left);printf(%d ,root-data);if(root-right!NULL)inOrdered(root-right);}//----------------BST删除-----------------------------//找以root为根节点中最靠右的结点BTNode*find(BTree root){BTNode*proot;while(p-right!NULL){pp-right;}returnp;}//要在以root为根节点的树中删除数据为k的结点BTreedeleteBST(BTree root,intk){if(kroot-data){//在以root-left为根节点的子树中删除数据为k的结点root-leftdeleteBST(root-left,k);}elseif(kroot-data){//在以root-right为根节点的子树中删除数据为k的结点root-rightdeleteBST(root-right,k);}else{//根节点就是要删除的结点if(root-left!NULLroot-right!NULL){//左右孩子都存在BTNode*pfind(root-left);root-datap-data;root-leftdeleteBST(root-left,p-data);}else{//只有一个孩子或孩子为NULLBTNode*chNULL;if(root-left!NULL){chroot-left;}else{chroot-right;}free(root);rootNULL;returnch;}}returnroot;}intmain(){intn;scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);}BTree rootinitBST(a[1]);if(rootNULL){printf(建树失败\n);return0;}for(inti2;in;i){insert(root,a[i]);}printf(中序遍历结果\n);inOrdered(root);printf(\n);printf(删除结点:\n,n);scanf(%d,n);rootdeleteBST(root,n);printf(中序遍历结果\n);inOrdered(root);printf(\n);return0;}questions什么时候返回 root-leftif(kroot-data)root-leftdeleteBST(root-left,k);要删的数 比当前节点小说明在左子树里递归处理左子树把新的左子树头接回 root-left这里返回的就是 新的左子树什么时候返回 root-rightelseif(kroot-data)root-rightdeleteBST(root-right,k);要删的数 比当前节点大说明在右子树里递归处理右子树把新的右子树头接回 root-right这里返回的就是 新的右子树什么时候返回 rootreturnroot;没进入删除分支只是往下递归查找最后把当前节点原样返回让上层继续挂着什么时候返回孩子节点删除成功时free(root);rootNULL;returnch;找到了要删的节点只有一个孩子 / 无孩子直接删掉自己返回孩子给上层上层会自动把这个孩子接在 left 或 right 上限制插入顺序会影响查找速度如果序列本身是升序 / 降序的就会建成斜树起不到优化作用 — 引入AVL树例如按照123的顺序去插入形成一颗斜树n个结点的斜树高度就是n此时查找效率和链表就没有区别了AVL树是一种特殊的BST树BST树是一种特殊的二叉树
数据结构入门详解（十二）：二叉搜索树的删除（C语言实现）
BST的删除操作删除数据为X的结点(1) 查找数据为X的结点free掉(2) 找顶替该结点的结点使满足BST的特点找替代结点x所在的结点的度为0(叶子结点)直接删除即可free(结点)该位置置空。x所在的结点的度为1(该节点只有一个孩子)找到这个结点并删除让其唯一的一个孩子代替该结点的位置。x所在结点的度为2可以用右子树中在最靠左的结点 或者 左子树中最靠右的结点 来代替该结点的位置同一颗树的删除规则必须统一。代码思路找到该节点把其数据域改为 左子树中最靠右的结点 / 右子树中最靠左的节点对其左子树进行递归删除左子树中最靠右的结点情况1可以看作情况2的特殊情况即认为叶子结点的孩子为NULL让NULL顶替要删除结点的位置所以只需要一份代码即可。总结度为0的情况可以看作度为1的情况递归思路原问题在以root为根的树中删除数据k范围缩小左子树 / 右子树if(root-data k),问题转化为 在以root-left为根的子树中删除数据kif(root-data k),问题转化为 在以root-right为根的子树中删除数据kif(root-data k)root结点就是要删除的结点1. 判断root的度 判断左右孩子存在不存在即可2. 度为2左右孩子都存在root左子树中最靠右的结点p root-data p-data 问题转化为在root-left为根的子树中删除数据p-data3. 度为0/度为1只要左孩子不存在那么就认为右孩子一定存在if(root-left!NULL){chroot-left;//一定是度为1的情况}else{chroot-right//有可能度为1有可能度为0}free(root);returnch;//带return所以就不用去找父亲结点的位置完整代码#includestdio.h#includestdlib.htypedefstructBTNode{intdata;structBTNode*left;structBTNode*right;}BTNode,*BTree;inta[100];//存数据BTreeinitBST(intdata){BTree root(BTNode*)malloc(sizeof(BTNode));if(rootNULL){printf(内存分配失败\n);returnNULL;}root-datadata;root-leftNULL;root-rightNULL;returnroot;}voidinsert(BTree root,intdata){if(rootNULL){printf(树空\n);return;}BTNode*newNode(BTNode*)malloc(sizeof(BTNode));if(newNodeNULL){printf(内存分配失败\n);return;}newNode-datadata;newNode-leftNULL;newNode-rightNULL;BTNode*curroot;BTNode*preNULL;while(cur!NULL){if(cur-datadata){precur;curcur-left;}else{precur;curcur-right;}}if(pre-datadata){pre-leftnewNode;}else{pre-rightnewNode;}}voidinOrdered(BTree root){if(rootNULL)return;if(root-left!NULL)inOrdered(root-left);printf(%d ,root-data);if(root-right!NULL)inOrdered(root-right);}//----------------BST删除-----------------------------//找以root为根节点中最靠右的结点BTNode*find(BTree root){BTNode*proot;while(p-right!NULL){pp-right;}returnp;}//要在以root为根节点的树中删除数据为k的结点BTreedeleteBST(BTree root,intk){if(kroot-data){//在以root-left为根节点的子树中删除数据为k的结点root-leftdeleteBST(root-left,k);}elseif(kroot-data){//在以root-right为根节点的子树中删除数据为k的结点root-rightdeleteBST(root-right,k);}else{//根节点就是要删除的结点if(root-left!NULLroot-right!NULL){//左右孩子都存在BTNode*pfind(root-left);root-datap-data;root-leftdeleteBST(root-left,p-data);}else{//只有一个孩子或孩子为NULLBTNode*chNULL;if(root-left!NULL){chroot-left;}else{chroot-right;}free(root);rootNULL;returnch;}}returnroot;}intmain(){intn;scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);}BTree rootinitBST(a[1]);if(rootNULL){printf(建树失败\n);return0;}for(inti2;in;i){insert(root,a[i]);}printf(中序遍历结果\n);inOrdered(root);printf(\n);printf(删除结点:\n,n);scanf(%d,n);rootdeleteBST(root,n);printf(中序遍历结果\n);inOrdered(root);printf(\n);return0;}questions什么时候返回 root-leftif(kroot-data)root-leftdeleteBST(root-left,k);要删的数 比当前节点小说明在左子树里递归处理左子树把新的左子树头接回 root-left这里返回的就是 新的左子树什么时候返回 root-rightelseif(kroot-data)root-rightdeleteBST(root-right,k);要删的数 比当前节点大说明在右子树里递归处理右子树把新的右子树头接回 root-right这里返回的就是 新的右子树什么时候返回 rootreturnroot;没进入删除分支只是往下递归查找最后把当前节点原样返回让上层继续挂着什么时候返回孩子节点删除成功时free(root);rootNULL;returnch;找到了要删的节点只有一个孩子 / 无孩子直接删掉自己返回孩子给上层上层会自动把这个孩子接在 left 或 right 上限制插入顺序会影响查找速度如果序列本身是升序 / 降序的就会建成斜树起不到优化作用 — 引入AVL树例如按照123的顺序去插入形成一颗斜树n个结点的斜树高度就是n此时查找效率和链表就没有区别了AVL树是一种特殊的BST树BST树是一种特殊的二叉树
