• 树的应用 —— 二叉树:二叉树的性质


    树的应用 —— 二叉树

    二叉树(Binary Tree)是n (n ≥0)个节点构成的集合,或为空树(n =0),或为非空树。

    对于非空树T ,要满足:

    ①有且仅有一个被称为根的节点;

    ②除了根节点,其余节点分为两个互不相交的子集T1和T2 ,分别被称为T 的左子树和右子树,且T1 和T2 本身都是二叉树。

    二叉树是种特殊的树,它最多有两个子树,分别为左子树和右子树,二者是有序的,不可以互换。也就是说,在二叉树中不存在度大于2的节点。

    【二叉树的总共5种形态】

    在这里插入图片描述

    二叉树的性质

    [性质1:在二叉树的第 i 层上至多有2^(i -1) 个节点。]

    一棵二叉树如下图所示。

    在这里插入图片描述

    由于二叉树的每个节点最多有2个孩子,第1层树根为1个节点,第2层最多为2个节点,第3层最多有4个节点,因为上一层的每个节点最多有2个孩子,因此当前层最多是上一层节点数的两倍。

    数学归纳法证明:

    1. i =1时:只有一个根节点,2^(i -1) =2^0 =1。
    2. i >1时:假设第i -1层有2^(i -2) 个节点,而第i 层节点数最多是第i -1层的两倍,即第i 层节点数最多有2×2^(i -2) =2(i -1) 。

    [性质2:深度为 k 的二叉树至多有2^k - 1个节点。]

    证明:如果深度为k 的二叉树,每一层都达到最大节点数,如下图所示,

    在这里插入图片描述

    则把每一层的节点数加起来就是整棵二叉树的最大节点数。

    [性质3:对于任何一棵二叉树,若叶子数为n0 ,度为2的节点数为n2 ,则n0 =n2 +1。]

    证明:

    二叉树中的节点度数不超过2,因此共有3种节点:度为0、度为1、度为2。设二叉树总的节点数为n ,度为0的节点数为n0 ,度为1的节点数为n1 ,度为2的节点数为n2 ,总节点数等于三种节点数之和,即n =n0 +n1 +n2 。

    而总节点数又等于分支数b +1,即n =b +1。为什么呢?如下图所示,

    在这里插入图片描述

    从下向上看,每一个节点都对应一个分支,只有树根没有对应的分支,因此总的节点数为分支数b +1。

    而分支数b 怎么计算呢?从上向下看,如下图所示,

    在这里插入图片描述

    每个度为2的节点都产生2个分支,度为1的节点产生1个分支,度为0的节点没有分支,因此分支数b =n1 +2n2 ,则n =b +1=n1 +2n2 +1。而前面已经得到n =n0 +n1 +n2 ,两式联合得:n0 =n2 +1。

    [有两种特殊的二叉树:满二叉树 和 完全二叉树]

    满二叉树:一棵深度为k 且有2^k -1个节点的二叉树。满二叉树的每一层都“充满”了节点,达到最大节点数,如下图所示。

    在这里插入图片描述

    完全二叉树:除了最后一层,每一层都是满的(达到最大节点数),最后一层节点是从左向右出现的。深度为k 的完全二叉树,当且仅当其每一个节点都与深度为k 的满二叉树中编号为1~n 的节点一一对应。例如,完全二叉树如下图所示,

    在这里插入图片描述

    它和上图中的满二叉树编号一一对应。完全二叉树除了最后一层,前面每一层都是满的,最后一层必须从左向右排列。也就是说,如果2没有左孩子,就不可以有右孩子,如果2没有右孩子,则3不可以有左孩子。

    [性质4:具有n 个节点的完全二叉树的深度必为⌊log2n ⌋+1。]

    证明:假设完全二叉树的深度为k ,那么除了最后一层,前k -1层都是满的,最后一层最少有一个节点,如下图所示。

    在这里插入图片描述

    最后一层最多也可以充满节点,即2^(k -1) 个节点,如下图所示。

    在这里插入图片描述

    因此,2^(k -1) ≤n ≤2^k -1,右边放大后,2^(k -1) ≤n <2^k ,同时取对数,k -1≤log2n

    例如,一棵完全二叉树有10个节点,那么该完全二叉树的深度为k=⌊log2 10⌋+1=4。

    [性质5:对于完全二叉树,若从上至下、从左至右编号,则编号为i 的节点,其左孩子编号必为2i ,其右孩子编号必为2i +1;其双亲编号必为i /2。]

    完全二叉树的编号如下图所示。

    在这里插入图片描述

    例如,一棵完全二叉树如下图所示。节点2的双亲节点为1,左孩子为4,右孩子为5;节点3的双亲节点为1,左孩子为6,右孩子为7。

    在这里插入图片描述

    【例题】

    1. 一棵完全二叉树有1001个节点,其中叶子节点的个数是多少?

    首先找到最后一个节点1001的双亲节点,其双亲节点编号为1001/2=500,该节点是最后一个拥有孩子的节点,其后面全是叶子,即1001-500=501个叶子。

    在这里插入图片描述

    1. 一棵完全二叉树第6层有8个叶子,则该完全二叉树最少有多少个节点,最多有多少个节点?

    完全二叉树的叶子分布在最后一层或倒数第二层。因此该树有可能为6层或7层。

    节点最少的情况(6层):8个叶子在最后一层(即第6层),前5层是满的,如下图所示。

    在这里插入图片描述

    最少有2^5 -1+8=39个节点。

    节点最多的情况(7层):8个叶子在倒数第2层(即第6层),前6层是满的,第7层最少缺失了8×2个节点,因为第6层的8个叶子如果生成孩子的话,会有16个节点。如下图所示,最多有2^7 -1-16=111个节点。

    在这里插入图片描述

  • 相关阅读:
    1.初识MySQL
    西门子6ES72881ST200AA1
    springboot集成Elasticsearch7.16,使用https方式连接并忽略SSL证书
    java 线索二叉树的构建
    Gurobi使用(一)——操作指南(转自知乎)
    商城检索 DSL
    Mysql基础(一)——Mysql数据库概述
    Doc as Code (4):使用Git做版本管理,而不是使用目录做版本管理
    iOS——单例模式
    【C++】红黑树
  • 原文地址:https://blog.csdn.net/weixin_44226181/article/details/126965534