• 【数据结构】一篇深入理解二叉树计算

    目录

    I.树的概念及结构

    树的概念

    树的结构

    树的专有名词

    树的表示

    树在实际中的运用

    II.二叉树的概念及结构

    二叉树的概念

            特殊的二叉树

    二叉树的性质

            完全二叉树小知识

    III.例题巩固

    I.树的概念及结构

    树的概念

         树是一种非线性的数据结构，它是由 n（n >= 0）个有限节点组成的一个具有层次关系的集合。

        那么为什么叫 "树" 呢？

        我们之所以把它成为 "树"，是因为它很像我们现实生活中的树。只是它是倒过来的，根朝上叶子朝下。

    树的结构

    特点：

    1. 有一个特殊的结点，称为根结点，根节点没有前驱结点
    2. 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
    3. 因此，树是递归定义的。

    注意：

    1. 树形结构中，子树之间不能有交集，否则就不是树形结构。
    2. 除了根结点外，每个结点有且仅有一个父结点。
    3. 一颗N个结点的树由N-1条边。

    树的专有名词

    • 专有名词：
    1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
    2. 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
    3.  非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
    4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
    5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
    6. 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
    7. 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
    8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
    9. 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
    10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
    11. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
    12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
    13. 森林：由m（m>0）棵互不相交的树的集合称为森林；
    14. 最近公共祖先：距离某些结点最近的祖先，比如P和Q的最近公共祖先为J，K和F的最近公共祖先为F。结点本身也可以成为自己的祖先
       

       树的表示

    以前学单链表时只有一个指针，双链表两个指针，但是树有多少个指针是不确定的，因为树没有规定一个节点最多有多少个孩子。那我们该如何定义结构呢？

    如若知道树的度，那就很好定义了:

    1. //假设指定树的度，可以直接定义
    2. #define N 5
    3. struct TreeNode
    4. {
    5. 	int data;
    6. 	struct TreeNode* subs[N]; //指针数组，每个结点存5个
    7. };

     但是又有一个缺陷，既然树的度为5，但是你这样设定只会导致每个结点的度均为5，可实际上只要保证每个结点的度<=5即可，由此可见，此法开辟造成空间浪费。此外，如果不知道树的度，那么用上述方法定义就比较困难了

    问题点：

    ① 可能会存在不少的空间浪费。 

    ② 万一没有限定树的度为多少呢？这个方式就废了。

    树的表示最佳方法：孩子兄弟表示法

    1. typedef int DataType;
    2.  
    3. struct Node {
    4.     struct Node* _firstChind1;   // 永远指向第一个孩子
    5.     struct Node* _pNextBrother;  // 指向孩子右边的兄弟
    6.     DataType _data;
    7. };

    既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

    假设我们要表示如下的树就可以如下图注意理解

    物理结构如下：

    原理：

    由上图代码图画演示及树的样子得知，根结点A是有B和C两个孩子的，永远让A的leftchild指向第一个孩子B，A的其它孩子C让B的兄弟指针去指向，C没有兄弟了，直接指向NULL。同理，B有3个孩子，让leftchild指针指向第一个孩子D，再让D的兄弟指针指向下一个E，以此类推……
     

    解读：

    无论你有多少个孩子，它都只存两个指针。一个指针永远指向第一个孩子，另一个指针指向孩子右边的兄弟（亲兄弟）。这个树的度无论为多少，也不需要用顺序表存，但是你任何一个节点有多少个孩子都能给你表示出来，通过第一个孩子把所有孩子都找出来。不复杂也没有浪费，只用两个指针就把链接关系都表示出来了
     

    树在实际中的运用

    文件系统的目录树结构、网络拓扑，最短路径问题，搜索引擎、思维导图等

    II.二叉树的概念及结构

    二叉树的概念

    二叉树：度为2的树，一棵二叉树是结点的一个有限集合，该集合:

    1. 或者为空
    2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

     从上图可以看出：

    1. 二叉树不存在度大于2的结点
    2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

    注意：对于任意的二叉树都是由以下几种情况复合而成的：

     

      特殊的二叉树

    • 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k -1 ，则它就是满二叉树。
    • 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

    简单来说，满二叉树的每个结点的度均为2，满二叉树是完全二叉树的特殊情况。当深度为K时，完全二叉树就是在【1，k-1】层的区间内均为满二叉树，只有最后一层第K层不满，但是最后一层是从左往右连续的。图示：

    二叉树的性质

    性质1：若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

    性质2：若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1 .

    性质3：对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1

    性质4：若规定根节点的层数为1，具有N个结点的满二叉树的深度，h= log2(N+1) . 

    性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

    1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    2. 若2i+1=n否则无左孩子
    3. 若2i+2=n否则无右孩子
       

    满二叉树计算公式：

    • 已知层数求总数：N = 2^h-1
    • 已知总数求层数： h = log_2(N+1)

    完全二叉树小知识：

    •  完全二叉树中，度为 1 的最多只有 1 个。
    •  高度为 h 的完全二叉树节点范围是   [ 2^{h-1} - 1 + 1, 2^{h} - 1 ]  

    对于性质5计算左右孩子：

    假设 parent 是父节点在数组中的下标，此公式仅适用于完全二叉树：

    ① 求左孩子： leftChild = parent * 2 + 1

    ② 求右孩子：rightChild = parent*2+2

    ③ 求父亲（假设不关注是左孩子还是右孩子）： 

                          parent = \frac{child-1}{2}   

    ④  判断是否有左孩子：  2*parent+1\geq n  

    ⑤  判断是否由右孩子：  2*parent+2 \geq n   

    解析：

    由图中不难发现，所有左孩子的下标均为奇数，而右孩子下标均为偶数，所以不难得出左右孩子的表达式。相反可以推出父亲的表达式。

    • 但是父亲的式子中，只是(child - 1) / 2，并没有区分左右孩子，这是为什么呢？

    这里我们假设leftchild和rightchild的下标均为3，算出来的parent下标不难发现均为1，同理左右孩子下标均为4时，父亲的下标算出来都是1，由此规律可得知直接用child下标表示父亲即可，无需区分左右孩子。
     

    III.例题巩固

    1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

         A.  不存在这样的二叉树

         B.  200

         C.  198

         D.  199

    解：

    由性质可知n0总是比n2度为2的结点多1，所以n0=200，选B

    2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

         A.  n

         B.  n+1

         C.  n-1

         D.  n/2

    解：

    设度为i的节点个数为ni，那么结点总个数就是这些结点的总和，即n=n0+n1+n2+n3+……+n(i-1)+n(i)

    所以总节点数2n=n0+n1+n2

    由性质n0-1=n2，则式子变为n0-1+n1+n0=2n

    又因为是完全二叉树，n不可能出现小数，所以n1=1

    综上，n0=n，选A

    3.  一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

         A.  11

         B.  10

         C.  8

         D.  12

    解：

     已知层数求总数：N = 2^h-1

    1024=2^10;

    512=2^9;

    易知h大于9层不足10层，选B

    5.  一个具有767个节点的完全二叉树，其叶子节点个数为（）

         A.  383

         B.  384

         C.  385

         D.  386

    解：

    n=n0+n1+n2

    n0-1=n2

    因完全二叉树，n1只能为0或1，又要确保结果是整数,所以n1=0

    选B


    6.  在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个,则叶子结点有（）个

           A.  4

           B.  5

           C.  6

           D.  7

    解：

    由结点总数和边数的关系：结点总数是n，那么边数就是n-1；

    设度为i的节点个数为ni，那么结点总个数就是这些结点的总和，即n=n0+n1+n2+n3+……+n(i-1)+n(i)

    因为是度为3的数:n=n0+n1+n2+n3

    总边数与度之间的关系为n-1=0*n0+1*n1+2*n2+3*n3

    根据题意：n3=2，n2=1，n1=2

    联立两个方程求解,可以得到n0 = n2 + 2n3 + 1, n0=6

    所以选C


    拿下拿下

  • 相关阅读:
    手撕ThreadLocal源码
    数据结构之图（关键路径）
    web前端课程设计——重庆旅游7页 HTML+CSS+JavaScript
    大厂经典指针笔试题
    【Buildroot】记一次编译出错gzip: popt-1.16.tar.gz: not in gzip format--更改br里面的默认下载地址
    正则表达式基础
    redis的详解和项目应用之SESSION共享
    谷歌云的利润增长才刚刚开始
    代码随想录算法训练营第六十天| LeetCode84.柱状图中最大的矩形
    解决eclipse导入svn项目报 403Forbidden
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/125888383