• 二叉树


    1、树结构常见概念

    :结点拥有的子树的数量被称作结点的度。

    叶子结点:度为零的结点被称作叶子节点,也叫终端结点。

    分支结点:树中除了叶子结点以外的其他结点被称作分支结点,也叫非终端结点。

    根结点:根结点是特殊的分支结点,根结点没有父结点。

    树的度:树内部各结点度的最大值被称作树的度。

    树的高度:树中结点的最大层次被称为树的高度,也叫树的深度。

    有序树:如果将树中结点的子树看作从左到右有序(即不可交换),则称该树是有序树。

    2、二叉树的定义

      二叉树是一种特殊的有序树,树中的结点的度数不大于2,即树中的结点最多只有两棵子树。

    二叉树的5种基本形态

    二叉树的5种基本形态

    3、二叉树的性质

    性质1  二叉树第i层最多有2i-1个结点(i>=1)

      等比数列通项公式:an = aqn-1

    性质2  高度为h的二叉树最多有2h -1个结点(h>=1)

      等比数列求和公式:Sn = a1(1-qn)/(1-q)

    性质3  对任何一棵二叉树,n0 = n2 + 1(n0、n1、n2分别表示树中度为0、1、2的结点的数量

      ①结点总数:

        树的结点总数n = n0 + n1 + n2

       ②分支总数:

        树的分支总数 = n - 1 = n1 + 2n=> n = n1 + 2n2 + 1

       (树中除了根结点,其他所有结点都有一个分支进入,所以树的分支总数等于结点总数减1;又因为所有的分支都是由度为1和度为2的结点射出,所有树的分支总数又等于n1 + 2n2

       由①②得:n0 = n2 + 1

     

    4、特殊二叉树

      满度二叉树和完全二叉树是两种特殊形态的二叉树。

      若二叉树的高度为h,且树的总结点数为2h - 1,则称该二叉树为满二叉树,也称满度二叉树,该树的特点是,每一层的节点数都达到最大值。

      对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

     

  • 相关阅读:
    Linux中配置别名
    Linux下的IO监控与分析
    RHEL6 Systemtap 安装笔记
    记一次多事件绑定中自己给自己设置的坑——click,dblclick,mousedown,mousemove,mouseup
    springboot打jar获取不到static静态资源文件问题
    关于springboot默认日志框架Slf4j+logback,自定义Appender问题
    spring 时间格式问题
    springboot 部署到tomcat,获取根路径问题。空格变为%20
    前后端分离 vue+springboot 跨域 session+cookie失效问题
    springboot 部署到tomcat中,项目总是重新部署
  • 原文地址:https://www.cnblogs.com/XiaoZhengYu/p/11916950.html
一二三 - 开发者的网上家园