美文网首页
数据结构之二叉树

数据结构之二叉树

作者: 陈盼同学 | 来源:发表于2021-06-08 09:28 被阅读0次

    (注释:整篇数据结构与算法文集,部分总结于王争的《数据结构与算法之美》和李明杰的《恋上数据结构与算法》,加上自己的理解,所以出了这个文集,仅做个人笔记记录所用。如你需要,请购买他们的正版资源,支持他们的原创)

    二叉树(Binary Tree)

    针对二叉树的讲解,王争和mj对于树的度讲述不同,王争侧重点是利用树的边数,mj是利用节点数。针对度的解读下面用mj的理念进行总结。

    节点、根节点、父节点、子节点、兄弟节点

    节点

    树的每个元素我们叫做“节点”

    根节点

    没有父节点的节点叫做根节点

    父节点、子节点、兄弟节点、叶子节点

    比如下面这幅图,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫做根节点,也就是图中的节点 E。我们把没有子节点的节点叫做叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。


    image.png

    一棵树可以没有任何节点,我们称之为空树
    一个数也可以只有一个节点,也就是只有根节点

    子树、左子树、右子树

    子树、左子树、右子树

    如图,A和F都是E的子节点。但同时,圈A可以算E的子树,圈F也可以算E的子树。所以E的子树有两个。在这个图里,圈A可以算E的左子树,圈F可以算E的右子树。


    1623052317652.jpg

    1623052736975.jpg
    节点的度

    该节点的子树的个数。如上图,1的度数是5;2的度数是2;6的度数是1;61的度数是0

    树的度

    所有节点度中最大的值。如上图所有节点里最大的度的节点就是1,它的度为5,所以这个树的度就是5

    层数

    根节点在第 1 层,根节点的子节点在第 2 层,以此类推(有些教程根节点算作第0层)

    节点的深度

    从根节点到当前节点的唯一路径上的节点总数。如上图,1节点的深度为1;2节点的深度为2;31节点的深度为3

    节点的高度

    从当前节点到最远叶子节点的路径上的节点总数。如上图,2的节点的高度为3;31的节点的深度为1

    树的深度

    所有节点深度中的最大值。如上图,树的深度为4

    树的高度

    所有节点高度中的最大值。如上图,树的高度为4

    一般来说 树的深度 等于 树的高度

    二叉树

    1633919725762.jpg
    二叉树的特点

    1.每个节点的度最大为2

    2.左子树和右子树是有顺序的(意思就是不能交换位置,该节点为左节点就是左节点。即使该节点只有一颗子树,也要区分左右子树)

    3.非空二叉树第i层,最多有2^(i-1)个节点(i>=1)

    4.在高度为h的二叉树上最多有2^h - 1个节点(h >= 1)

    5.对于任何一棵非空二叉树,如果叶子节点个数为 n0,度为 2 的节点个数为 n2,则有: n0 = n2 + 1
    证明:首先,假设该二叉树有N 个节点,那么它会有多少条边呢?答案是N - 1,这是因为除了根节点,其余的每个节点都有且只有一个父节点,那么这N 个节点恰好为树贡献了N - 1 条边。这是从下往上的思考,而从上往下(从树根到叶节点)的思考,容易得到每个节点的度数和 0n0 + 1n1 + 2n2 即为边的个数。
    因此,我们有等式 N - 1 = n1 + 2
    n2,把N 用n0 + n1 + n2 替换,得到n0 + n1 + n2 - 1 = n1 + 2*n2,于是有n0 = n2 + 1。命题得证。

    真二叉树

    含义:所有节点的度都要么为0,要么为2


    1623055951046.jpg
    满二叉树

    含义:所有节点的度都要么为0,要么为2,且所有的叶子节点都在最后一层


    1623055994932.jpg
    完全二叉树

    含义:叶子节点都在最后两层,最后一层的叶子节点都靠左排列(从左往右开始排列),并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫做完全二叉树。


    image.png
    完全二叉树的性质

    满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
    完全二叉树从根节点至倒数第2层是一颗满二叉树。


    1623057263133.jpg

    h = floor (\log_2{n}) + 1

    针对 h = floor (\log_2{n}) + 1的含义,因为 h - 1 <= \log_2{n} < h ,假设 \log_2{n}是4.1,那么h只能为5,这样才能满足 5-1 <= 4.1< 5 ,所以对\log_2{n}进行向下取整,就是去除小数位,然后再让取整后的数字加1,即得到h

    证明: 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(n-1) = 2^n - 1

    S=2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(n-1)
    2S=2^1 + 2^2 + 2^3 + ... + 2^(n-1) + 2^n
    两式相减,
    2S-S=2^n - 2^0
    S=2^n - 1

    完全二叉树性质
    从1编号的完全二叉树特性
    1623057299207.jpg
    从0编号的完全二叉树特性
    1623057337706.jpg

    面试题

    1623115585192.jpg

    相关文章

      网友评论

          本文标题:数据结构之二叉树

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