二叉树

作者: sakura579 | 来源:发表于2020-09-02 09:07 被阅读0次

    线性表是 约束比较轻的逻辑结构
    加一些约束 就得到了 栈 和 队列

    同样 树 也可以看作 约束比较轻 的逻辑结构,
    树中每个结点可以有任意多个孩子结点,
    每个结点的孩子结点是没有次序之分的。

    加上约束 :
    ①每个结点的 孩子结点 最多有两个
    ②对每个结点的孩子结点 规定上次序,一个称之为左孩子,另一个称之为右孩子。





    满二叉树:
    除了最底层结点外,所有的结点都有左右两个孩子。

    完全二叉树:
    简单来说,对于一棵满二叉树,从最底层开始,从右往左,逐渐的删除结点得到的二叉树。


    满二叉树 是特殊的 完全二叉树。

    满二叉树 高度与结点的关系

    高度为h 结点个数为 2^h -1

    “|_ _|” 是 向下取整


    向上取整

    公式

    不是第一种 就是第二种

    完全二叉树中 出现叶子结点的层,要不是倒数第二层,要不是最后一层。

    要结点个数最多的情况,则第六层 为 倒数第二层


    前六层 是 满二叉树,63个。
    1、2、4 则 a1 = 1,q = 2
    Sn = 2^n - 1
    an = a1 * 2^(n-1)
    a6 = 32
    (32 -8)*2 = 48

    48 + 63 = 111

    叶子结点数 = 双分支结点数 + 1

    画出空分支(在没有挂子结点的地方 给它标记出来)


    有些题会问你空分支有 多少个
    可以在空分支处 画上节点 也就是叶子节点
    那么树中原来的节点 都变为 双分支节点

    根据叶子节点 = 双分支节点 + 1


    空分支个数 = 结点总数 + 1


    这种方式 只适合存 完全二叉树,对于一般二叉树是不行的。
    注意起始结点编号 是从0开始还是从1开始 ,会有稍微不同。


    虽然简单 ,但是有局限性,只适用于存储完全二叉树


    每个结点有三个域:
    一个数据域,左边一个指针域,右边一个指针域,分别指向左孩子和右孩子结点。


    二叉链表存储结构:
    貌似这种存储结构是专门存放二叉树的,
    但是这种存储结构可不可以来存储一般的树,
    肯定有同学说 那肯定不行。
    因为树的孩子结点可能有多个,多于两个的情况就存不了了。

    换个角度考虑一下。
    对于一棵树而言,最重要的逻辑关系是 其父节点和孩子节点的关系。
    一定要有 父节点 能找到它的孩子节点。
    但是不必要父节点和孩子节点 都有直接的关系。

    之前那个 树的链式存储 也体现了 这种做法

    相关文章

      网友评论

          本文标题:二叉树

          本文链接:https://www.haomeiwen.com/subject/kegpsktx.html