精华内容
下载资源
问答
  • 【折半查找二叉判定树

    千次阅读 2021-04-05 00:51:30
    二叉判定树 又称 二叉排序树,是具有以下性质的二叉树: 若左子树不为空,则左子树上各个节点的值 均小于 其根节点的值 若右子树不为空,则右子树上各个节点的值 均大于或等于 其根节点的值 左、右子树也分别为二叉...

    二叉判定树,具有以下性质:

    1. 若左子树不为空,则左子树上各个节点的值 均小于 其根节点的值
    2. 若右子树不为空,则右子树上各个节点的值 均大于或等于 其根节点的值
    3. 左、右子树也分别具有上面两个特点


    已知一个顺序存储是有序表为(15,26,34,39,45,56,58,63,74,76),试画出对应的二叉判定树,求其平均查找长度。


    折半查找二叉判定树画法

    【1】确定二叉判定树的深度(即:多少层)

    1. 序列总长度n = 10,而一棵深度为 h 的二叉树,节点数最多为(2^h) - 1

    2. n > (2^3) - 1,所以该二叉判定树有4层,前面3层为满二叉树结构,剩余3个节点在第4层。
      cd

    【2】确定二叉判定树的根节点

    1. 根节点下标:rootIndex = (startIndex + endIndex) / 2,在前面序列中有10个元素,所以startIndex = 0,endIndex = 9

    2. (0 + 9) / 2 = 4,所以根节点下标为4,根节点的值为45
      cd

    【3】确认根节点左右子树

    1. 45左侧元素 作为根节点的左子树

    2. 45右侧元素 作为根节点的右子树
      cd

    【4】确定左子树部分的排序

    1. 45左侧元素,也就是15,26,34,39作为根节点的左子树部分

    2. 继续【2】中的父节点判断方式,(0 + 3) / 2 = 1,所以26是45的左孩子。15作为26的左孩子,34作为26的右孩子。剩下的39作为34的右孩子(注:为什么不是作为34的左孩子呢? 因为二叉判定树的左孩子<父节点,右孩子>父节点,而39>34,所以39作为34的右孩子,而不是左孩子)
      cd

    【5】确定右子树部分的排序

    1. 45右侧元素,也就是56,58,63,74,76作为根节点的右子树部分

    2. 右子树的排序方式 和 左子树是一样的,所以这里省略了…
      cd

    【6】该二叉判定树的整体结构:

    cd


    二叉判定树平均查找长度

    cd




    https://zhidao.baidu.com/question/273190366.html

    展开全文
  • 【数据结构】折半查找及其二叉判定树画法

    万次阅读 多人点赞 2019-09-25 23:55:40
    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。 其特点有以下几个: 只能对有序的顺序表进行查找。 是一种静态查找。 查找的平均时间复杂度为o(log...折半查找和二叉排序查找的平均查找长度均取决...

    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。

    其特点有以下几个:

    1. 只能对有序的顺序表进行查找。
    2. 是一种静态查找。
    3. 查找的平均时间复杂度为o(log2n)。
    4. 成功平均查找长度ASL约log2(n+1)-1。

    这里要注意折半查找和二叉排序树查找的区别。折半查找和二叉排序树查找的平均查找长度均取决于树高h(或折半查找判定树的高h),折半查找的判定树的高只与序列长度n相关(必为平衡二叉树AVL树),而二叉排序树查找构建二叉排序树时树的高度还取决于序列顺序。所以折半判定树树高始终为log2(n+1)向上取整,而在最优情况下二叉排序树树高最低为log2(n+1)向上取整,最坏情况下(序列有序)树高h为n;因此折半查找最多比较次数为log2(n+1)向上取整,而二叉排序树最优情况下与此相等,最坏情况下为n次。

    以下给出一个折半查找的C++代码:

    
     
    1. #define MaxSize 50;
    2. using namespace std;
    3. struct SeqList{
    4. Elemtype elem[MaxSize];
    5. int Length;
    6. };
    7. int Binary_Search(SeqList L,Elemtype x)
    8. {
    9. int low= 0,high=L.Length -1,mid;
    10. while(low<=high)
    11. {
    12. mid=(low+high)/ 2;
    13. if(x==L.elem[mid])
    14. return mid;
    15. else if(x<L.elem[mid])
    16. high=mid -1;
    17. else
    18. low=mid+ 1;
    19. }
    20. return -1;
    21. }

     可以看出折半查找的代码相对非常简单。在实际的考题中,往往会出现对具体个数的序列的折半查找等概率下的成功查找长度和失败查找长度,解决这类问题需要画出对应的二叉判定树。有时甚至会出现直接对于某二叉判定树的问题(如某具体序列中查找某元素的比较顺序或某序列的最大比较次数等问题)。

    以下给出我在学习中总结的一种比较简便的构造折半二叉判定树的思路以及方法:

    思路分析:

    在计算mid值时,使用的时mid=(low+high)/2  。这里由于mid为int类型,自动默认为向下取整,因此对于一个长度为n序列进行划分之后的序列为 (0,1,2,……,mid-1)mid(mid+1,mid+2,……n-1),此时出现两种情况:

    • 左子序列长==右子序列长      (n=2k+1    k=0,1,2,……)
    • 左子序列长==右子序列长-1   (n=2k        k=1,2,3,……)

    因此可以得知,折半查找的二叉判定树对于所有结点,左子树结点个数<=右子树结点个数。即:

    1. 若某序列总长n为奇数,左右子树结点个数相等;
    2. 若某序列总长n为偶数,左字数结点个数=右子树结点个数-1.

    由此给定某个序列,构建折半查找判定树方法如下三步:

    1. 按照二叉树每层最大结点数为2^(h-1)依次由上至下构建满二叉树至最底层不够形成满二叉树为止。
    2. 将剩余结点按照上述粉字的规律依次填入最底层即为二叉判定树的树形。
    3. 按照中序遍历顺序将各结点值填入结点即可。

    具体如下面的例子:

     

    例:画出(2,5,7,10,14,15,18,23,35,41,52)的折半查找判定树。

    1.序列总长度为n=11>2^3-1=7     即二叉判定树为4层,第4层不满。

    2.

    1)剩余四个结点。当第四层一个叶结点时,结点总数n=8为偶数,因此对于a来说,应加在a的右子树,即c的子树中;对于c来说,结点总数n=4为偶数,应加在c的右子树中,即g的子树中;对于g来说,结点总数n=2为偶数,应加在g的右子树,即

    2)在第四层加入第二个结点时,结点总数n=9为奇数,因此对于a来说,应加在a的左子树使左右子树结点个数相等,即加在b的子树中;对于b来说,结点总数n=4为偶数,应加在b的右子树,即e的子树中;对于e来说,结点总数n=2为偶数,应加在e的右子树,即

    3)同理分析,第三个结点应加在a的右孩子的左孩子的右子树,即

    4)第四个结点加在a的左孩子的左孩子的右子树,即

    得到最终的树形如上图。

    3.该二叉树的中序遍历顺序为dkbeiafjcgh,因此将序列一一对应填入树中,即

    该树即为此序列的二叉判定树。

     

    做题过程中熟练使用此方法比通过算法模拟来推断二叉判定树的速度要快许多倍。

    在平时做题过程中,涉及到需要具体画出二叉判定树的题目,往往结点个数(序列长度)不超过2^4-1=15个,即一般为高度不超过4的树,因此可以在练习时将结点个数8-14的所有树形画几遍,就可以很熟练的掌握这个方法。

    二叉判定树画出之后便可以对其他具体题目进行分别的计算,如求成功或失败的查找长度、求比较顺序、比较次数等。

    展开全文
  • 以下给出我在学习中总结的一种比较简便的构造折半二叉判定树的思路以及方法: 思路分析: 在计算mid值时,使用的时mid=(low+high)/2 。这里由于mid为int类型,自动默认为向下取整,因此对于一个长度为n序列进行...

    以下给出我在学习中总结的一种比较简便的构造折半二叉判定树的思路以及方法:

    思路分析:

    在计算mid值时,使用的时mid=(low+high)/2  。这里由于mid为int类型,自动默认为向下取整,因此对于一个长度为n序列进行划分之后的序列为 (0,1,2,……,mid-1)mid(mid+1,mid+2,……n-1),此时出现两种情况:

    • 左子序列长==右子序列长      (n=2k+1    k=0,1,2,……)
    • 左子序列长==右子序列长-1   (n=2k        k=1,2,3,……)

    因此可以得知,折半查找的二叉判定树对于所有结点,左子树结点个数<=右子树结点个数。即:

    1. 若某序列总长n为奇数,左右子树结点个数相等;
    2. 若某序列总长n为偶数,左字数结点个数=右子树结点个数-1.

    换句话说,对判定树中所有结点都有:

    (左子树结点数-右子树结点数==-1)||(左子树结点数-右子树结点数==0)

    由此给定某个序列,构建折半查找判定树方法如下三步:

    1. 按照结点总数先画出最大的满二叉树结构,并计算剩余几个结点。
    2. 将剩余结点按照上述的规律依次填入最底层即为二叉判定树的树形。
    3. 将给定序列依次按照中序遍历顺序填入各个结点。

    具体如下面的例子:

     

    例:画出(2,5,7,10,14,15,18,23,35,41,52)的折半查找判定树。

    1.序列总长度为n=11>2^3-1     即二叉判定树为4层,前三层为满二叉树结构,剩余4个结点。

    先画出前三层结构。

    2.

    1)第一个结点。a的左右子树结点个数相等,所以新的结点应加入a的右子树;再看a的右子树,c的左右子树结点个数相等,所以新结点应加入c的右子树;再看c的右子树,g的左右子树结点个数相等,所以新结点应加入g的右子树;如图

    2)第二个结点。a的左子树结点数-右子树结点数=-1,所以新结点应加入a的左子树(若加入右子树,对于a来说左右子树结点之差=-2,不符合规律);再看a的左子树,b的左右子树结点个数相等,所以新结点应加入b的右子树;再看b的右子树,e的左右子树结点个数相等,所以新结点应加入e的右子树。如图

    3)同理分析,第三个结点应加在如图位置。

    4)第四个结点加在如图位置。

    得到最终的树形如上图。(字母编号不唯一,但后面中序遍历结果会不同)

    3.该二叉树的中序遍历顺序为dkbeiafjcgh,分别对应2,5,7,10,14,15,18,23,35,41,52。因此将序列一一对应填入树中,即

    该树即为此序列的二叉判定树。

     

    做题过程中熟练使用此方法比通过算法模拟来推断二叉判定树的速度要快许多倍。

    在平时做题过程中,涉及到需要具体画出二叉判定树的题目,往往结点个数(序列长度)不超过2^4-1=15个,即一般为高度不超过4的树,因此可以在练习时将结点个数8-14的所有树形画几遍,就可以很熟练的掌握这个方法。

    二叉判定树画出之后便可以对其他具体题目进行分别的计算,如求成功或失败的查找长度、求比较顺序、比较次数等。

    展开全文
  • 满二叉树是一颗深度为h,最大层数为k,且深度与最大层数相同,即k=h; 它的叶子数是: 2^(h-1) 第k层的结点数是: 2^(k-1) 总结点数是: 2^k-1 (2的k次方减一) 总节点数一定是奇数。   2、完全二叉树   如上图

    1、满二叉树

    定义:除最后一层的结点外,每一层的所有结点都有两个子结点。

    另外一个定义:深度为k且有2^k-1个结点的二叉树。

     

    满二叉树是一颗树深度为h,最大层数为k,且深度与最大层数相同,即k=h;
    它的叶子数是: 2^(h-1)
    第k层的结点数是: 2^(k-1)
    总结点数是: 2^k-1 (2的k次方减一)
    总节点数一定是奇数。
     
    2、完全二叉树
     
    如上图,完全二叉树只比满二叉树少了最后几个结点,所以满二叉树是一种特殊的完全二叉树。
     
     
    完全二叉树是效率很高的数据结构,堆是一种完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。
     
    3、最优二叉树(赫夫曼树)
     
     首先,介绍树的带权路径长度,
    树的带权路径长度为树中所有叶子结点的带权路径长度之和。
     
    带权路径长度最小的二叉树称作最优二叉树赫夫曼树
     
     4、二叉排序树
    二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;
     
    简单的准则:值的大小,左<根<右
     
     
    5、二叉判定树
      
       描述折半查找过程的二叉树为判定树。
    判定树首先是一个二叉排序树,具有n个结点的判定树具有与具有n个结点的完全二叉树的深度完全相同,其深度为:
     
     
      
    在折半查找时,查找成功不成功,和给定值比较的次数最多为
     
     

     

    展开全文
  • 判定树 和选择树差不多,就是用到了树的结构: 八枚硬币,有一个是假的,比较三次确定哪个是假币以及假币和真币相比质量如何? 特点: 判定树整体是该问题的所有可能解; 每一个从根到叶子都是一种可能解 每一个非...
  • 一、什么是二叉搜索 二叉搜索本质还是二叉树,但它在不空时添加节点,它左子树上所有的元素都小于根节点的元素,而根节点右子上所有的元素都大于根节点的元素。 通过以上方法建的的中序遍历是从小到大的序列...
  • 二叉排序树(vs折半查找判定树

    千次阅读 2020-06-21 11:40:35
    二叉排序
  • 二叉排序判定.cpp

    2019-06-16 14:14:49
    二叉排序判定,广义表表示法创建二叉树,C语言指针的相关应用。
  • 主要介绍了C语言判定一棵二叉树是否为二叉搜索的方法,结合实例形式综合对比分析了C语言针对二叉搜索树判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下
  • 文章目录二叉搜索/二叉排序/二叉查找.1 定义.2 性质二叉搜索创建二叉搜索查找.1 查找步骤.2 查找性能分析二叉树插入与删除 二叉搜索/二叉排序/二叉查找 .1 定义 二叉排序(Binary Sort Tree)...
  • 二叉排序判定

    2019-01-07 16:27:13
    二叉排序判定,可以判定是否为二叉排序,这是我在读大学学习的时候写的
  • 今天再来为大家介绍java中二分查找判定树的方法,并且通过举例来详细地解析。首先我们需要了解的是,二分查找过程可用二叉树来描述,也就是把当前查找区间的中间位置上的结点作为根,左子表和右子表中的结点分别作为...
  • 1.二叉排序的定义 二叉排序: 1)或者是一棵空。 2)或者是具有下列性质的二叉树: [1]若它的左子树不空,则左子树上所有的结点的值都小于它的根节点的值; [2]若它的右子不空,则右子上所有的结点的...
  • 二叉树和二叉搜索之间的区别

    千次阅读 2020-06-28 14:47:18
    任何人都可以用一个例子解释二叉树和二叉搜索之间的区别吗?
  • 二叉查找与平衡二叉树

    万次阅读 多人点赞 2018-08-29 14:47:46
    二叉查找  二叉查找,也称二叉搜索,或二叉排序。其定义也比较简单,要么是一颗空,要么就是具有如下性质的二叉树: (1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2...
  • 二叉平衡二叉搜索的一种拓展,比较典型的是 红-黑 。因为二叉搜索有可能因为插入的节点大部分都大于、或者大部分都小于根节点,使得二叉树节点增加严重向左/右某一边倾斜,从而导致搜索性能大打折扣,所以...
  • 但二分查找判定树唯一,而二叉排序树的查找不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树。 维护表的有序性。二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作,二分查找的对象是...
  • 二叉排序 二叉排序(Binary Sort Tree),又称二叉查找(Binary Search Tree),亦称二叉搜索。 中文名 二叉排序 外文名 Binary Sort Tree 别 称 二叉查找二叉搜索 别称外文名 Binary ...
  • 知识梳理:二叉查找树 一、查找 二叉排序树:简称BST也叫二叉搜索树 二叉排序树可以是空树。 二叉查找树中每个节点: 左子树中每个节点的值都不大于该节点值...2.折半查找的判定树就是一棵二叉排序树。 二、插入 1.插入
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...
  • 二叉搜索树判定

    2020-02-09 13:00:16
       给定一个二叉树,判断其是否是一个有效的二叉搜索。假设一个二叉搜索具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子只包含大于当前节点的数。 所有左子树和右子自身必须也是二叉...
  • 二叉排序树的搜索(SearchBST) 二叉排序树的插入(InsertBST) 二叉排序树的删除(Delete) 中序遍历(inorder) 先序遍历(preorder) 什么是二叉排序树 ...二叉排序树的结构类似于二分查找的判定树。.
  • 网上定义太死板,其实左大于根大于右这种也是可以的!(考研数据结构的加油????)
  • 二叉搜索判定

    2020-02-14 11:43:24
    给定一个二叉树,判断其是否是一个有效的二叉搜索。 假设一个二叉搜索具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子只包含大于当前节点的数。 所有左子树和右子自身必须也是二叉搜索...
  • 二叉排序 1、引言 当表插入、删除操作频繁时,为维护表的有序性,需要移动表中很多记录。 改用动态查找表————几种特殊的 表结构在查找过程中动态生成 对于给定值key,若表中存在,则成功返回; 否则,插入...
  • 判断二叉树是否为二叉排序

    千次阅读 2018-04-14 21:19:54
    1.二叉排序定义 二叉排序(BinarySortTree)定义如下:二叉排序或者是一棵空,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;(2)若右子不空,则...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,611
精华内容 3,444
关键字:

二叉判定树