(注释:整篇数据结构与算法文集,部分总结于王争的《数据结构与算法之美》和李明杰的《恋上数据结构与算法》,加上自己的理解,所以出了这个文集,仅做个人笔记记录所用。如你需要,请购买他们的正版资源,支持他们的原创)
二叉树(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 + 2n2,把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 () + 1
针对 h = floor () + 1的含义,因为 h - 1 <= < h ,假设 是4.1,那么h只能为5,这样才能满足 5-1 <= 4.1< 5 ,所以对进行向下取整,就是去除小数位,然后再让取整后的数字加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
网友评论