二叉排序树 订阅
二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。 展开全文
二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。
信息
别    称
二叉查找树、二叉搜索树
别称外文名
Binary Search Tree
中文名
二叉排序树
外文名
Binary Sort Tree
二叉排序树定义
一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;(4)没有键值相等的结点。
收起全文
精华内容
下载资源
问答
  • 二叉排序树

    2018-06-11 13:15:48
    二叉树基本操作,包括实现二叉排序树的查找、插入、构造和删除等算法,使用二叉排序树
  • 二叉排序树二叉排序树二叉排序树二叉排序树
  • 二叉排序树也称二叉查找树。是一种特殊的二叉树。特点二叉排序树中,如果其左子树非空,那么左子树上所有结点的值都小于根结点的值;二叉排序树中,如果其右子树非空,那么右子树上所有结点的值都大于根结点的值;...

    二叉排序树也称二叉查找树。是一种特殊的二叉树。

    特点

    • 二叉排序树中,如果其左子树非空,那么左子树上所有结点的值都小于根结点的值;

    • 二叉排序树中,如果其右子树非空,那么右子树上所有结点的值都大于根结点的值;

    • 二叉排序树的左右子树也要求都是二叉排序树。

    构建一颗二叉排序树,主要不是为了排序,而是为了提高查找和删除操作的速度。

    定义二叉排序树的结构

    typedef struct BSTNode{  TreeElem data;  struct BSTNode* Lchild, * Rchild;  //左右孩子指针}BSTNode, * BSTree;

    查找操作

    1. 若二叉排序树为空,则返回false;

    2. 若二叉排序树不空,则判断给定值是否与结点数据值相等:

      • 若相等,则记录此结点(定义一个指针p记录),并返回true;

      • 若keydata,则继续调用函数比较左子树

      • 若key>T->data,   则继续调用函数比较右子树

        查找代码

    bool SearchBST(BSTree T, TreeElem key,BSTree f,BSTree *p){  if (T == NULL)  {    *p = f;    return false;  }  else if (key == T->data)  {    *p = T;    return true;  }  else if (key < T->data)    return SearchBST(T->Lchild, key, T, p);  else    return SearchBST(T->Rchild, key, T, p);}

    二叉树的遍历操作

    二叉树的遍历方式有三种:前序、中序和后序,利用递归。
    //前序遍历void preordertraverse(BiTree t){  if (t == NULL)    return;  printf("%c", t->data);  preordertraverse(t->Lchild);  preordertraverse(t->Rchild);}//中序遍历void inordertraverse(BiTree t){  if (t == NULL)    return;  inordertraverse(t->Lchild);  printf("%c ", t->Lchild);  inordertraverse(t->Rchild);}//后序遍历void outordertraverse(BiTree t){  if (t == NULL)    return;  outordertraverse(t->Lchild);  outordertraverse(t->Rchild);  printf("%c ", t->data);}

    二叉排序树的插入操作

    进行插入操作时,可以通过调用查找函数判断要插入的元素是否已经存在,如果不存在则继续插入。注意:插入结点一定是叶子结点
    //插入操作--插入结点一定是叶子结点bool InsertBST(BSTree* T, int key){  BSTree p,s;  if (SearchBST(*T, key, NULL, &p))  //如果查找成功    return false;  else  //如果查找不成功,插入的结点是此时p指向结点的子结点  {    s = (BSTree)malloc(sizeof(BSTNode));    if (s == NULL) return false;    s->data = key;    s->Lchild =s->Rchild=NULL;    if (p == NULL)      *T = s;  //此时s为根节点    else if (key < p->data)      p->Lchild = s;    else if (key > p->data)      p->Rchild = s;    return true;  }}
    有了插入操作,就可以利用插入函数创建一个二叉排序树。全部代码(没写删除函数)
    #include #include #define TreeElem int//定义结构体typedef struct BSTNode{  TreeElem data;  struct BSTNode* Lchild, * Rchild;}BSTNode, * BSTree;//查找操作//f指向T的双亲,其初始值为NULL/*p是二重指针,若查找成功,p指向该数据所在的结点,若查找失败,则指向查找路径上访问的最后一个结点*/bool SearchBST(BSTree T, TreeElem key,BSTree f,BSTree *p){  if (T == NULL)  {    *p = f;  //说明f是此条路径上的最后一个元素,当然f也可能为NULL    return false;  }  else if (key == T->data)  {    *p = T;    return true;  }  else if (key < T->data)    return SearchBST(T->Lchild, key, T, p);  else    return SearchBST(T->Rchild, key, T, p);}//插入操作--插入结点一定是叶子结点bool InsertBST(BSTree* T, int key){  BSTree p,s;  if (SearchBST(*T, key, NULL, &p))  //如果查找成功    return false;  else  //如果查找不成功,插入的结点是此时p指向结点的子结点  {    s = (BSTree)malloc(sizeof(BSTNode));    if (s == NULL) return false;    s->data = key;    s->Lchild = NULL; s->Rchild = NULL;    if (p == NULL)      *T = s;  //此时s为根节点    else if (key < p->data)      p->Lchild = s;    else if (key > p->data)      p->Rchild = s;    return true;  }}//中序遍历void preordertraverse(BSTree T){  if (T == NULL)return;  preordertraverse(T->Lchild);  printf("%d\n", T->data);  preordertraverse(T->Rchild);}int main(void){  BSTree t = NULL;  //利用插入操作创建二叉排序树  int a[10] = { 62,88,58,47,35,73,51,99,37,93 };  int i;  for (i = 0; i < 10; i++)  {    InsertBST(&t, a[i]);  }  preordertraverse(t);  return 0;}
    展开全文
  • //算法7.4 二叉排序树的递归查找 //算法7.5 二叉排序树的插入 //算法7.6 二叉排序树的创建 //算法 7.7 二叉排序树的删除 #include<stdio.h> #include<stdlib.h> #define ENDFLAG '#' //char a[10]={...

    此代码可以正常运行,下附有运行区

    //算法7.4 二叉排序树的递归查找
    //算法7.5 二叉排序树的插入
    //算法7.6 二叉排序树的创建
    //算法 7.7 二叉排序树的删除
    #include<stdio.h>
    #include<stdlib.h>
    #define ENDFLAG '#'
    //char a[10]={'5','6','7','2','1','9','8','10','3','4','#'};//全局变量
    typedef struct ElemType{	
    	char key;
    }ElemType;
    
    typedef struct BSTNode{
    	ElemType data;	//结点数据域
    	BSTNode *lchild,*rchild;	//左右孩子指针
    }BSTNode,*BSTree;
    
    
    //算法7.4 二叉排序树的递归查找
    BSTree SearchBST(BSTree T,char key) {
      //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
      //若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
      if((!T)|| key==T->data.key) return T;       	            	//查找结束
      else if (key<T->data.key)  return SearchBST(T->lchild,key);	//在左子树中继续查找
      else return SearchBST(T->rchild,key);    		   			//在右子树中继续查找
    } // SearchBST
    
    
    
    //算法7.5 二叉排序树的插入
    void InsertBST(BSTree &T,ElemType e ) {
      //当二叉排序树T中不存在关键字等于e.key的数据元素时,则插入该元素
      if(!T) {                				//找到插入位置,递归结束
    		 BSTree S = new BSTNode;            		//生成新结点*S
             S->data = e;                  		//新结点*S的数据域置为e   
             S->lchild = S->rchild = NULL;	//新结点*S作为叶子结点
             T =S;            				//把新结点*S链接到已找到的插入位置
      }
      else if (e.key< T->data.key) 
          InsertBST(T->lchild, e );			//将*S插入左子树
      else if (e.key> T->data.key) 
          InsertBST(T->rchild, e);			//将*S插入右子树
    }// InsertBST
    
    
    
    //算法7.6 二叉排序树的创建
    void CreateBST(BSTree &T ) {
      //依次读入一个关键字为key的结点,将此结点插入二叉排序树T中
      T=NULL;
      ElemType e;
      scanf("%c",&e.key);       
      while(e.key!=ENDFLAG){   	//ENDFLAG为自定义常量,作为输入结束标志
        InsertBST(T, e);          	//将此结点插入二叉排序树T中
        scanf("%c",&e.key);			
      }//while            
    }//CreatBST
    
    void DeleteBST(BSTree &T,char key) {
      //从二叉排序树T中删除关键字等于key的结点
      BSTree p=T;BSTree f=NULL;                     			//初始化
      BSTree q;
      BSTree s;
      /*------------下面的while循环从根开始查找关键字等于key的结点*p-------------*/
      while(p){                  
       if (p->data.key == key) break;  	      	//找到关键字等于key的结点*p,结束循环
       f=p;                                			//*f为*p的双亲结点
       if (p->data.key> key)  p=p->lchild;     	//在*p的左子树中继续查找
       else p=p->rchild;  	                  		//在*p的右子树中继续查找
      }//while
    if(!p) return;                         		//找不到被删结点则返回
    
    /*―考虑三种情况实现p所指子树内部的处理:*p左右子树均不空、无右子树、无左子树―*/
    if ((p->lchild)&& (p->rchild)) {     		//被删结点*p左右子树均不空
         q = p;
    	 s = p->lchild;
         while (s->rchild)                			//在*p的左子树中继续查找其前驱结点,即最右下结点
           {q = s; s = s->rchild;}	         		//向右到尽头
         p->data = s->data;               			//s指向被删结点的“前驱”
         if(q!=p){
    		 q->rchild = s->lchild;     	//重接*q的右子树
    	 }
         else q->lchild = s->lchild;        		//重接*q的左子树
         delete s;
      }//if
    else{
    	if(!p->rchild) {               		//被删结点*p无右子树,只需重接其左子树
    		  q = p; p = p->lchild; 
    	  }//else if
    	else if(!p->lchild) {               		//被删结点*p无左子树,只需重接其右子树
    		 q = p; p = p->rchild;
    	  }//else if
    	/*――――――――――将p所指的子树挂接到其双亲结点*f相应的位置――――――――*/
    	  if(!f) T=p;                       			//被删结点为根结点
    	  else if (q==f->lchild) f->lchild = p;   	//挂接到*f的左子树位置
    	  else f->rchild = p;                 		//挂接到*f的右子树位置
    	  delete q;
    	}
    }//DeleteBST
    
    //算法 7.7 二叉排序树的删除
    
    //中序遍历
    void InOrderTraverse(BSTree &T)
    {
    	if(T)
    	{
    	InOrderTraverse(T->lchild);
    	printf("%c",T->data.key);
    	InOrderTraverse(T->rchild);
    	}
    }
    
    void main()
    {
    	BSTree T;
    	printf("请输入若干字符,用回车区分,以#结束输入\n");
    	CreateBST(T);
    	printf("当前有序二叉树中序遍历结果为\n");
    	InOrderTraverse(T);
    	printf("\n");
    	char key;//待查找或待删除内容
    	printf("请输入待查找字符\n");
    	getchar();
    	scanf("%c",&key);
    	BSTree result=SearchBST(T,key);
    	if(result)
    	{printf("找到字符:%c\n",key);}
    	else
    	{printf("未找到%c\n",key);}
    	printf("请输入待删除的字符\n");
    	getchar();
    	scanf("%c",&key);
    	DeleteBST(T,key);
    	printf("当前有序二叉树中序遍历结果为\n");
    	InOrderTraverse(T);
    	printf("\n");
    }
    
    
    

    在这里插入图片描述

    展开全文
  • 《数据结构》实验报告班级:姓名:学号:E-mail:日期:◎实验题目: 建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。 ◎实验目的:熟悉并掌握二叉排序树的建立及遍历输出以及非递归查找。◎实验内容:输入一...

    《数据结构》实验报告

    班级:姓名:学号:E-mail:日期:

    ◎实验题目: 建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。 ◎实验目的:熟悉并掌握二叉排序树的建立及遍历输出以及非递归查找。

    ◎实验内容:输入一组数据,建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。

    一、需求分析

    1、本程序中,输入一组数据,然后建立一棵二叉排序树存储这些元素,再中序遍历输出检验树建立是否正确,中序遍历输出的次序应为从小到大排列,然后输入一个关键字查找,输出查找成功与否。

    2、演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入相应数据。

    3、程序所能达到的功能:建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。

    4、测试数据:

    输入待排序的数据:10 15 20 5 10 30 9 7 13 45 2 -1(-1是输入结束标志) 中序遍历二叉树输出为:2 5 7 9 10 10 13 15 20 30 45

    输入要查找的元素:7

    输出:查找成功

    二 概要设计

    为了实现上述操作,应以二叉链表为存储结构,中序非递归遍历时以栈为中间存储结构。 该程序有四个函数分别为:主函数,插入函数,输出函数,查找函数。主函数通过调用其他三个函数实现上述功能。

    三 详细设计

    1、定义节点类型

    typedef struct node

    {

    int data;

    struct node *lc;

    struct node *rc;

    }BiTNode,*BiTree;

    2、主函数

    定义二叉排序树根节点bt,以及整形变量,x待插入数据变量,k查找关键字变量。二叉排序树 建立读取输入的数据存入x中,如果不是结束标志-1就调用插入函数将x插入到二叉排序树中,否则就执行后续操作。然后调用输出函数中序输出二叉排序树。二叉排序树 建立输出待查找的数据存入k中。调用查找函数进行查找。根据返回的指针判断查找成功与否。

    3、插入函数

    定义指向待插入节点指针q以及指向当前节点指针p,以及整形变量i用于判断插入成功与否。

    q指向新申请节点,并将待插入数据存入数据项中。当树为空时,直接将节点插入到根节点。否则待插入节点与根节点进行比较:如果小于根节点,沿左孩子链进行比较,否则沿右孩子链进行比较。直到终端插入该节点。

    4、中序遍历函数

    当前结点等于根结点.

    初始化栈。

    当栈不空或者当前结点不空时while循环:

    当p不空时进栈,然后沿左孩子路径访问,直至p为空;

    此时让p等于栈顶指针,输出p的数据域的值;

    当输出了父结点后沿右孩子路径访问。

    5、查找函数

    定义指向当前节点指针p,并使p指向根节点。当p不空且还未查找到关键字与根节点进行比较。若大于根节点沿右孩子链查找,否则沿左孩子链进行查找。返回指针p。

    四 使用说明、测试分析及结果

    1、测试结果

    输入待排序的数据:10 15 20 5 10 30 9 7 13 45 2 -1(-1是输入结束标志) 中序遍历二叉树输出为:2 5 7 9 10 10 13 15 20 30 45

    输入要查找的元素:7

    输出:查找成功

    符合预期设想

    3.运行界面

    五、实验总结

    在进行这次试验前,我首先写了实验预习报告,用了大概半小时时间写出了解决此问题的大体算法,并且用了半小时时间把具体的设计写了出来,要用了一个小时进行了调试。在进行测试的时候,发现查找的元素不在二叉树中出来的结果是查找成功,最后检查发现时判断条件的时候把等于打成了赋值。做了这么多实验我的细心程度还是达不到期望值。这是我以后实验中特别要注意的地方。 教师评语:

    实验成绩:

    指导教师签名:

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/jisuanjixue/article-25005-1.html

    展开全文
  • 前几节介绍的都是有关静态查找表的相关知识,从本节开始介绍另外一种查找表——动态查找表。动态查找表中做查找操作时,若查找成功可以对其进行...二叉排序树要么是空二叉树,要么具有如下特点:二叉排序树中,如...

    前几节介绍的都是有关静态查找表的相关知识,从本节开始介绍另外一种查找表——动态查找表动态查找表中做查找操作时,若查找成功可以对其进行删除;如果查找失败,即表中无该关键字,可以将该关键字插入到表中。动态查找表的表示方式有多种,本节介绍一种使用树结构表示动态查找表的实现方法——二叉排序树(又称为“二叉查找树”)。

    什么是二叉排序树?

    二叉排序树要么是空二叉树,要么具有如下特点:

    • 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点的值;

    • 二叉排序树中,如果其根结点有右子树,那么右子树上所有结点的值都大小根结点的值;

    • 二叉排序树的左右子树也要求都是二叉排序树;

    例如,图 1 就是一个二叉排序树:

    02f951b25cb39022946fcd58acfd9d1b.png图 1 二叉排序树

    使用二叉排序树查找关键字

    二叉排序树中查找某关键字时,查找过程类似于次优二叉树,在二叉排序树不为空树的前提下,首先将被查找值同树的根结点进行比较,会有 3 种不同的结果:

    • 如果相等,查找成功;

    • 如果比较结果为根结点的关键字值较大,则说明该关键字可能存在其左子树中;

    • 如果比较结果为根结点的关键字值较小,则说明该关键字可能存在其右子树中;

    实现函数为:(运用递归的方法)

    BiTree SearchBST(BiTree T,KeyType key){    //如果递归过程中 T 为空,则查找结果,返回NULL;或者查找成功,返回指向该关键字的指针    if (!T || key==T->data) {        return T;    }else if(keydata){        //递归遍历其左孩子        return SearchBST(T->lchild, key);    }else{        //递归遍历其右孩子        return SearchBST(T->rchild, key);    }}

    二叉排序树中插入关键字

    二叉排序树本身是动态查找表的一种表示形式,有时会在查找过程中插入或者删除表中元素,当因为查找失败而需要插入数据元素时,该数据元素的插入位置一定位于二叉排序树的叶子结点,并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。

    例如,在图 1 的二叉排序树中做查找关键字 1 的操作,当查找到关键字 3 所在的叶子结点时,判断出表中没有该关键字,此时关键字 1 的插入位置为关键字 3 的左孩子。

    所以,二叉排序树表示动态查找表做插入操作,只需要稍微更改一下上面的代码就可以实现,具体实现代码为:

    BOOL SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){    //如果 T 指针为空,说明查找失败,令 p 指针指向查找过程中最后一个叶子结点,并返回查找失败的信息    if (!T){        *p=f;        return false;    }    //如果相等,令 p 指针指向该关键字,并返回查找成功信息    else if(key==T->data){        *p=T;        return true;    }    //如果 key 值比 T 根结点的值小,则查找其左子树;反之,查找其右子树    else if(keydata){        return SearchBST(T->lchild,key,T,p);    }else{        return SearchBST(T->rchild,key,T,p);    }}//插入函数BOOL InsertBST(BiTree T,ElemType e){    BiTree p=NULL;    //如果查找不成功,需做插入操作    if (!SearchBST(T, e,NULL,&p)) {        //初始化插入结点        BiTree s=(BiTree)malloc(sizeof(BiTree));        s->data=e;        s->lchild=s->rchild=NULL;        //如果 p 为NULL,说明该二叉排序树为空树,此时插入的结点为整棵树的根结点        if (!p) {            T=s;        }        //如果 p 不为 NULL,则 p 指向的为查找失败的最后一个叶子结点,只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子        else if(edata){            p->lchild=s;        }else{            p->rchild=s;        }        return true;    }    //如果查找成功,不需要做插入操作,插入失败    return false;}

    通过使用二叉排序树对动态查找表做查找和插入的操作,同时在中序遍历二叉排序树时,可以得到有关所有关键字的一个有序的序列。

    例如,假设原二叉排序树为空树,在对动态查找表 {3,5,7,2,1} 做查找以及插入操作时,可以构建出一个含有表中所有关键字的二叉排序树,过程如图 2 所示:

    59c1a0ae473e53e71b78df5ddf0b757d.png图 2 二叉排序树插入过程

    通过不断的查找和插入操作,最终构建的二叉排序树如图 2(5) 所示。当使用中序遍历算法遍历二叉排序树时,得到的序列为:1 2 3 5 7 ,为有序序列。

    一个无序序列可以通过构建一棵二叉排序树,从而变成一个有序序列。

    二叉排序树中删除关键字

    在查找过程中,如果在使用二叉排序树表示的动态查找表中删除某个数据元素时,需要在成功删除该结点的同时,依旧使这棵树为二叉排序树。假设要删除的为结点 p,则对于二叉排序树来说,需要根据结点 p 所在不同的位置作不同的操作,有以下 3 种可能:1、结点 p 为叶子结点,此时只需要删除该结点,并修改其双亲结点的指针即可;2、结点 p 只有左子树或者只有右子树,如果 p 是其双亲节点的左孩子,则直接将 p 节点的左子树或右子树作为其双亲节点的左子树;反之也是如此,如果 p 是其双亲节点的右孩子,则直接将 p 节点的左子树或右子树作为其双亲节点的右子树;3、结点 p 左右子树都有,此时有两种处理方式:

    1)令结点 p 的左子树为其双亲结点的左子树;结点 p 的右子树为其自身直接前驱结点的右子树,如图 3 所示;

    cd52f7477e9b9c6967f63674a16d8411.png图 3 二叉排序树中删除结点(1)

    2)用结点 p 的直接前驱(或直接后继)来代替结点 p,同时在二叉排序树中对其直接前驱(或直接后继)做删除操作。如图 4 为使用直接前驱代替结点 p:

    e9af96f33adc31aa9da00cf66991a14d.png图 4 二叉排序树中删除结点(2)

    图 4 中,在对左图进行中序遍历时,得到的结点 p 的直接前驱结点为结点 s,所以直接用结点 s 覆盖结点 p,由于结点 s 还有左孩子,根据第 2 条规则,直接将其变为双亲结点的右孩子。

    具体实现代码:(可运行)

    #include#include#define TRUE 1#define FALSE 0#define ElemType int#define  KeyType int/* 二叉排序树的节点结构定义 */typedef struct BiTNode{    int data;    struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;//二叉排序树查找算法int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p) {    //如果 T 指针为空,说明查找失败,令 p 指针指向查找过程中最后一个叶子结点,并返回查找失败的信息    if (!T) {        *p = f;        return FALSE;    }    //如果相等,令 p 指针指向该关键字,并返回查找成功信息    else if (key == T->data) {        *p = T;        return TRUE;    }    //如果 key 值比 T 根结点的值小,则查找其左子树;反之,查找其右子树    else if (key < T->data) {        return SearchBST(T->lchild, key, T, p);    }    else {        return SearchBST(T->rchild, key, T, p);    }}int InsertBST(BiTree *T, ElemType e) {    BiTree p = NULL;    //如果查找不成功,需做插入操作    if (!SearchBST((*T), e, NULL, &p)) {        //初始化插入结点        BiTree s = (BiTree)malloc(sizeof(BiTNode));        s->data = e;        s->lchild = s->rchild = NULL;        //如果 p 为NULL,说明该二叉排序树为空树,此时插入的结点为整棵树的根结点        if (!p) {            *T = s;        }        //如果 p 不为 NULL,则 p 指向的为查找失败的最后一个叶子结点,只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子        else if (e < p->data) {            p->lchild = s;        }        else {            p->rchild = s;        }        return TRUE;    }    //如果查找成功,不需要做插入操作,插入失败    return FALSE;}//删除函数int Delete(BiTree *p){    BiTree q, s;    //情况 1,结点 p 本身为叶子结点,直接删除即可    if (!(*p)->lchild && !(*p)->rchild) {        *p = NULL;    }    else if (!(*p)->lchild) { //左子树为空,只需用结点 p 的右子树根结点代替结点 p 即可;        q = *p;        *p = (*p)->rchild;        free(q);    }    else if (!(*p)->rchild) {//右子树为空,只需用结点 p 的左子树根结点代替结点 p 即可;        q = *p;        *p = (*p)->lchild;//这里不是指针 *p 指向左子树,而是将左子树存储的结点的地址赋值给指针变量 p        free(q);    }    else {//左右子树均不为空,采用第 2 种方式        q = *p;        s = (*p)->lchild;        //遍历,找到结点 p 的直接前驱        while (s->rchild)        {            q = s;            s = s->rchild;        }        //直接改变结点 p 的值        (*p)->data = s->data;        //判断结点 p 的左子树 s 是否有右子树,分为两种情况讨论        if (q != *p) {            q->rchild = s->lchild;//若有,则在删除直接前驱结点的同时,令前驱的左孩子结点改为 q 指向结点的孩子结点        }        else {            q->lchild = s->lchild;//否则,直接将左子树上移即可        }        free(s);    }    return TRUE;}int DeleteBST(BiTree *T, int key){    if (!(*T)) {//不存在关键字等于key的数据元素        return FALSE;    }    else    {        if (key == (*T)->data) {            Delete(T);            return TRUE;        }        else if (key < (*T)->data) {            //使用递归的方式            return DeleteBST(&(*T)->lchild, key);        }        else {            return DeleteBST(&(*T)->rchild, key);        }    }}void order(BiTree t)//中序输出{    if (t == NULL) {        return;    }    order(t->lchild);    printf("%d ", t->data);    order(t->rchild);}int main(){    int i;    int a[5] = { 3,4,2,5,9 };    BiTree T = NULL;    for (i = 0; i < 5; i++) {        InsertBST(&T, a[i]);    }    printf("中序遍历二叉排序树:\n");    order(T);    printf("\n");    printf("删除3后,中序遍历二叉排序树:\n");    DeleteBST(&T, 3);    order(T);}

    运行结果:

    中序遍历二叉排序树:
    2 3 4 5 9
    删除3后,中序遍历二叉排序树:
    2 4 5 9

    总结

    使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同,但是不同的排列顺序,构建出的二叉排序树大不相同。例如:查找表 {45,24,53,12,37,93} 和表 {12,24,37,45,53,93} 各自构建的二叉排序树图下图所示:

    7ba6913ef37720ede72ca4497d93fedd.png图 5 不同构造的二叉排序树

    使用二叉排序树实现动态查找操作的过程,实际上就是从二叉排序树的根结点到查找元素结点的过程,所以时间复杂度同被查找元素所在的树的深度(层次数)有关。为了弥补二叉排序树构造时产生如图 5 右侧所示的影响算法效率的因素,需要对二叉排序树做“平衡化”处理,使其成为一棵平衡二叉树。

    平衡二叉树是动态查找表的另一种实现方式,下一节做重点介绍。

    c6094feee1d0fea11ce4749fa50c0228.png

    展开全文
  • 各位考研小伙伴们大家好呀,本篇文章将会为大家讲解下二叉排序树删除的内容,删除虽然不是常考点,但也需要掌握其原理,下面就开始我们的讲解吧!一、重要知识点(1)中序遍历二叉排序树可得到关键字的有序序列;(2)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,992
精华内容 7,996
关键字:

二叉排序树