查找 - 树上的查找 - 二叉排序树（三）
( )二叉排序树的删除
从二叉排序树中删除一个结点 不能把以该结点为根的子树都删去 并且还要保证删除后所得的二叉树仍然满足BST性质
①删除操作的一般步骤
( ) 进行查找
查找时 令p指向当前访问到的结点 parent指向其双亲(其初值为NULL) 若树中找不到被删结点则返回 否则被删结点是*p
( ) 删去*p
删*p时 应将*p的子树(若有)仍连接在树上且保持BST性质不变 按*p的孩子数目分三种情况进行处理
②删除*p结点的三种情况
( )*p是叶子(即它的孩子数为 )
无须连接*p的子树 只需将*p的双亲*parent中指向*p的指针域置空即可
( )*p只有一个孩子*child
只需将*child和*p的双亲直接连接后 即可删去*p
注意
*p既可能是*parent的左孩子也可能是其右孩子 而*child可能是*p的左孩子或右孩子 故共有 种状态
( )*p有两个孩子
先令q=p 将被删结点的地址保存在q中;然后找*q的中序后继*p 并在查找过程中仍用parent记住*p的双亲位置 *q的中序后继
*p一定是*q的右子树中最左下的结点 它无左子树 因此 可以将删去*q的操作转换为删去的*p的操作 即在释放结点*p之前将其
数据复制到*q中 就相当于删去了*q 具体【 参见动画演示 】
③二叉排序树删除算法
分析
上述三种情况都能统一到情况( ) 算法中只需针对情况( )处理即可
注意边界条件 若parent为空 被删结点*p是根 故删去*p后 应将child置为根
算法
void DelBSTNode(BSTree *Tptr KeyType key)
{//在二叉排序树*Tptr中删去关键字为key的结点
BSTNode *parent=NUll *p=*Tptr *q *child;
while(p){ //从根开始查找关键字为key的待删结点
if(p >key==key) break;//已找到 跳出查找循环
parent=p; //parent指向*p的双亲
p=(key key)?p >lchild p >rchild; //在关p的左或右子树中继续找
}
if(!p) return; //找不到被删结点则返回
q=p; //q记住被删结点*p
if(q >lchild&&q >rchild) //*q的两个孩子均非空 故找*q的中序后继*p
for(parent=q p=q >rchild; p >lchild; parent=p p=p= >lchild);
//现在情况( )已被转换为情况( ) 而情况( )相当于是情况( )中child=NULL的状况
child=(p >lchild)?p >lchild p >rchild;//若是情况( ) 则child非空;否则child为空
if(!parent) //*p的双亲为空 说明*p为根 删*p后应修改根指针
*Tptr=child; //若是情况( ) 则删去*p后 树为空;否则child变为根
else{ //*p不是根 将*p的孩子和*p的双亲进行连接 *p从树上被摘下
if(p==parent >lchild) //*p是双亲的左孩子
parent >lchild=child; //*child作为*parent的左孩子
else parent >rchild=child; //*child作为 parent的右孩子
if(p!=q) //是情况( ) 需将*p的数据复制到*q
q >key=p >key; //若还有其它数据域亦需复制
} //endif
free(p); /释放*p占用的空间
lishixinzhi/Article/program/sjjg/201311/23824
轩琼天晴： #include #include #define INFMT ＂%d＂#define OUTFMT ＂%d ＂/* #define NULL 0L */#define BOOL int#define TRUE 1#define FALSE 0#define LEN 10000 typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *...
米脂县17599981773： 【数据结构】几种重要的查找算法.几种重要的查找算法.(如顺序查找、折半(二分)查找、二叉排序树上的查找) - ？
轩琼天晴：[答案] 恩你是要问什么?顺序查找就是按顺序查找,复杂度O(n)二分查找的前提是数据是有序的 一次复杂度O(logn)例如在数组 A: 1 3 5 7 8 10 12 中如果要找 10我们先看中间的数是 7, 10比7大,那么继续在右侧二分寻找,这是一个递...
米脂县17599981773： C语言编程 二叉排序树查找 _ ？
轩琼天晴： #include<stdio.h> #include<malloc.h> #define NULL 0 typedef struct node {int data;node *left;node *right; }node;node *CreateTree(node* root,int *p,int n) {int i=n;node *q,*r;while(i!=0){if(root==NULL){root=(node *)malloc(sizeof(node *)); ...
米脂县17599981773： 二叉排序树的创建和查找 _ ？
轩琼天晴： 首先你需要做的是怎么比较电话号码关键字,只有能比较大小后才能根据关键字建立二叉排序树 然后就是二叉排序树的知识了,我在这里面放了二叉排序树的主要操作的介绍及实现,你可以看一下(二叉查找树就是二叉排序树) http://blog.csdn.net/sb55154634/archive/2010/07/22/5755201.aspx
米脂县17599981773： 二叉排序树的构造和查找方法 - ？
轩琼天晴： 二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义. 插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中; 当非空时,...
米脂县17599981773： 用C语言实现二叉排序树的查找、插入和删除 - ？
轩琼天晴： #include <stdio.h>#include <conio.h> #include <stdlib.h> typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode,*BiTree; void CreateBiTree(BiTree &); //生成一个二叉树 void FirstOrder(BiTree); //先序递归遍历二叉树 void ...
米脂县17599981773： 数据结构(java):二叉排序树上查找键值为K的算法函数 - ？
轩琼天晴： 结点结构 左指针、右指针 数据域typedef struct Node{DataType data; //数据域Node *right,*left; //结点的左右子树指针 }BTNode;//函数体BTNode *FindBTree(BTNode* root, DataType item) {if(root==NULL) return NULL;if(root->data==item...
米脂县17599981773： 用C语言实现二叉排序树的查找、插入和删除 - ？
轩琼天晴： #include<stdio.h>//二分查找法或折半查找法void main(){ int a[10]={1,3,5,9,13,16,17,26,38},count=0;//记录查找了多少次 //必须是有次的数组 int key,mid;//要查找的数字和折半后的下标 int pos=-1;//查找到的位置 int i=0,j=8; printf(＂请输入要查...
米脂县17599981773： 遍历查找二叉查找树 - ？
轩琼天晴： 二叉查找树是排序的.左孩子总比父结点小,右孩子总比父结点大.用java简单写了下. public static void findkey(node root, int key, LinkedListlist) { if root == null return; if root.value == key { list.add(root); if root.left.value == key return findkey(root....
