最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 二叉树

    1 重点概念

    1.1 结点概念

    结点是数据结构中的基础,是构成复杂数据结构的基本组成单位。

    1.2 树结点声明

    本系列文章中提及的结点专指树的结点。例如:结点A在图中表示为:

    2 树

    2.1 定义

    树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:
    1)有且仅有一个特定的称为根(Root)的结点;
    2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tn,其中每一个集合本身又是一棵树,并且称为根的子树。

    此外,树的定义还需要强调以下两点:
    1)n>0时根结点是唯一的,不可能存在多个根结点,数据结构中的树只能有一个根结点。
    2)m>0时,子树的个数没有限制,但它们一定是互不相交的。
    示例树:
    图2.1为一棵普通的树:

    图2.1 普通树

    由树的定义可以看出,树的定义使用了递归的方式。递归在树的学习过程中起着重要作用,如果对于递归不是十分了解,建议先看看递归算法

    2.2 结点的度

    结点拥有的子树数目称为结点的
    图2.2中标注了图2.1所示树的各个结点的度。

    图2.2 度示意图

     

    2.3 结点关系

    结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点
    图2.2中,A为B的双亲结点,B为A的孩子结点。
    同一个双亲结点的孩子结点之间互称兄弟结点
    图2.2中,结点B与结点C互为兄弟结点。

    2.4 结点层次

    从根开始定义起,根为第一层,根的孩子为第二层,以此类推。
    图2.3表示了图2.1所示树的层次关系

    图2.3 层示意图
    2.5 树的深度

    树中结点的最大层次数称为树的深度或高度。图2.1所示树的深度为4。

     

    3. 二叉查找树

    二叉查找树就是以二分法思想为指导,设计出来的一种快速查找树,二叉查找树保证以下特性:

    • 每一个节点关键字只会在树中出现一次。
    • 任何一个节点,如果它有子节点,那么左侧的关键字一定比较小,右侧的关键字一定比较大。

    基于这种结构,搜索时每次从根节点开始查找,就算找到叶子结点,也只进行了log2n次比较,效率明显高于顺序/倒序遍历。

    4. 平衡二叉树(AVL树)

    极端情况下的二叉查找树可能只有左子树,进而退化为链表结构。为应对这种情况,引入了平衡二叉树:

    • 它是一个空树或二叉查找树
    • 左右两个子树的高度差的绝对值不超过1
    • 左右两个子树都是一颗平衡二叉树

    平衡二叉树的查找时间复杂度不会超过O(log2n),平衡二叉树在做插入或删除的时候,需要通过一系列的旋转(左旋、右旋)操作(自平衡),让其始终满足平衡二叉树的条件。

    5.2-3树

    一颗2-3树或为一颗空树,或有以下节点组成:

    2-节点,含有一个元素和两个子树(左右子树),左子树所有元素的值均小于它父节点,右子树所有元素的值均大于它父节点;

    3-节点,还有两个元素和三个子树(左中右子树),左子树所有元素的值均小于它父节点,中子树所有元素的值都位于父节点两个元素之间,右子树所有元素的值均大于它父节点;

    子树也是空树、2-节点或者3-节点;

    没有元素相等的节点。

    2-3树能够保证在插入元素之后,树依然保持平衡状态,它的最坏情况下所有子节点都是2-节点,树的高度为lgN,相比于我们普通的二叉查找树,最坏的情况下树的高度为N,确实保证了最坏情况下的时间复杂度,但是2-3树实现起来过于复杂,所以我们经常使用一种使用2-3树思想进行简单实现的红黑树来替代。

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 二叉树

    发表评论

    • 52会员总数(位)
    • 307资源总数(个)
    • 40本周发布(个)
    • 1 今日发布(个)
    • 329稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情