数据结构之二叉树
(注释：整篇数据结构与算法文集，部分总结于王争的《数据结构与算法之美》和李明杰的《恋上数据结构与算法》，加上自己的理解，所以出了这个文集，仅做个人笔记记录所用。如你需要，请购买他们的正版资源，支持他们的原创)
二叉树（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
完全二叉树性质
从1编号的完全二叉树特性
1623057299207.jpg
从0编号的完全二叉树特性
1623057337706.jpg
面试题
1623115585192.jpg
