简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第三章第一小节：什么是二叉树。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Python数据结构：链表合集（12+7），复现几遍，包你学会
Python数据结构：栈队列哈希合集（10+1），复现几遍，包你学会
今日问题
""" 介绍二叉树的基础知识 目录 1> 什么是二叉树？ 2> 二叉树结点的属性 2.1>结点的度 2.2>叶子结点 2.3>分支结点 2.4>左孩子、右孩子、双亲结点 2.5>路径、路径长度 2.6>祖先、子孙 2.7>结点的层数 3> 树的属性 3.1>树的深度 3.1>树的度 4> 什么是满二叉树？ 5> 什么是完全二叉树？ 6> 二叉树的基本性质 7> 实战 """
1> 什么是二叉树？
二叉树（Binary Tree），他是n（n>=0）个有限元素的集合，该集合或者为空（n=0）, 或者有一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树 组成，当集合为空（n=0）时，称为空二叉树。
2> 二叉树结点的属性
2.1>结点的度
结点所拥有的子树的个数称为该结点的度。叶子结点的度为0。
2.2>叶子结点
度为0的结点称为叶子结点。
2.3>分支结点
度不为0的结点称为分支结点，或称为非终端结点，一棵树除了叶子结点，其他的 结点都是分支结点。
2.4>左孩子、右孩子、双亲结点
一个结点的子树的根结点称为该结点的孩子，该结点称为双亲结点，该结点的左子 树的根结点称为该结点的左孩子，该结点的右子树的根结点称为该结点的右孩子。
2.5>路径、路径长度
如果一颗树的一串结点n1,n2,n3...nk，有如下关系，结点ni是n(i+1)的双亲结点 （1<=i
2.6>祖先、子孙
在树中，如果有一条路径从结点M到结点N，那么结点M称为结点N的祖先，而结点N称 为结点M的子孙。
2.7>结点的层数
规定根结点的层数为1，其余结点层数等与其双亲结点的层数加1。
3> 树的属性
3.1>树的深度
树中所有结点的最大层数称为树的深度。
3.1>树的度
树中各结点的度的最大值称为该树的度。
4> 什么是满二叉树？
在一颗二叉树中，如果所有的分支结点都有左子树和右子树，并且所有叶子结点都在同一层，这样的 一颗二叉树称为满二叉树。如下所示：
A / \ B C
5> 什么是完全二叉树？
一颗深度为k的有n个结点的二叉树，对树中的结点按从上到下，从左到右的顺序进行编号，如果编号为i(1<=i<=n) 的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则该树为完全二叉树。特点：完全二叉树的叶子结点只能出现在最下层和最次层，而且最下层叶子结点集中在左边。
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。如下图所示：
A / \ B C / \ E F
6> 二叉树的基本性质
6.1> 一颗非空二叉树的第i层上最多有2^(i-1)个结点（i>=1）。
证明：
一个结点最多有两个子树，故 第1层1个结点（2^(1-1)）， 第2层最多2个结点（2^(2-1)）， 第3层最多4个结点（2^(3-1)） 依次类推：第i层最多有2^(i-1)个结点。
6.2> 一颗深度为k的二叉树中，最多有2^k - 1个结点，最少有k个结点。
证明：
由6.1，可知一颗深度为k的二叉树最多的结点树S = 2^0 + 2^1 + 2^2 + ... + 2^k 由等比数列计算前n项和公式可以计算出：S = 2^k - 1 每一层至少有一个结点，故深度为k的二叉树最少有k个结点。
6.3> 对于一颗非空二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个，如果叶子结点个数为n0，度数为2的结点为n2，则有 n0 = n2 + 1。
证明：
假设度数为1的结点数为n1，则二叉树的结点总数S = n0 + n1 + n2，再根据结点度数的性质，度数为 0的结点没有子结点，度数为1的结点有一个子结点，度数为2的结点有两个子结点，所以二叉树的结点总数还可 以表示为S = n00 + n11 + n22 +1 = n1 + 2n2 + 1，所以n0 + n1 + n2 = n1 + 2*n2 + 1,整理 得：n0 = n2 + 1。
6.4>具有n个结点的完全二叉树的深度为「log2 n」 + 1
证明：
假设该完全二叉树的深度为k，则该完全二叉树的总结点数应该是在深度为k和深度为k-1的满二叉树之间， 深度为k-1的满二叉树结点总数为：2^(k-1) - 1，想要变成深度为k的完全二叉树，则至少在原二叉树基础上 加一个结点，故深度为k的完全二叉树的结点总数 n >= 2^(k-1) - 1 + 1 即： 2^(k-1) <= n <= 2^k - 1 < 2^k 解得：log2 n <= k < log2 n + 1 由于k为整数，故 k = 「log2 (n+1)」 + 1 注：「」 表示向下取整，如：「3.5」 = 3
6.5> 对于具有n个结点的完全二叉树，如果按照从上到下，从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对任意的序号为i的结点有：
（1）如果i > 1，则序号为i的结点的双亲结点的编号为i/2（/ 表示取商的整数部分）；如果i = 1，则序号为i 的结点为根结点，无双亲结点。 （2）如果 2i <= n，则序号为i的结点的左孩子结点的序号为2i；如果2i > n，则序号为i的结点无左孩子。 （3）如果 2i+1 <= n，则序号为i的结点的右孩子结点的序号为2i+1；如果2i+1 > n，则序号为i的结点无右孩子。
注：若从0开始编号，则对应的i号结点的双亲结点的编号为：(i-1)/2；左孩子的编号为：2i+1，右孩子的编号为：2i+2。
7> 实战
S：表示二叉树的结点总数 n0：表示叶子结点个数 n1：表示度数为1的结点个数 n2：表示度数为2的结点个数
>7.1 一颗完全二叉树上有1001个结点，求叶子结点的个数？
解：S = n1 + 2*n2 + 1 在完全二叉树中度数为1的结点个数最多为1，最少为0（满二叉树） 当n1 = 1 时，有：1001 = 1 + 2*n2 + 1 解得：n2 = 999/2，不满足题意，舍； 当n1 = 0 时，有：1001 = 0 + 2*n2 + 1 解得：n2 = 500， 又n0 = n1 + 1 , --- 性质3 故 n0 = 501，即叶子结点个数为501。
>7.2 如果根的层次为1，具有61个结点的完全二叉树的高度为多少？
解：这里的高度也就是深度， 由完全二叉树的深度 k = 「log2 n」 + 1 得 --- 性质4 该完全二叉树的高度为：「log2 61」 + 1 = 6。
>7.3 在具有100个结点的二叉树中，其边的数目是多少？
解：在二叉树中，除开根结点，每个结点都有一条入边，故100个结点的二叉树中有99条边。
>7.4 写出下面这颗树的基本属性值：
A / \ B C / \ / \ D E F G / \ H I 这是一颗完全二叉树 结点总数：9 度数为0的(叶子)结点数：5 度数为1的结点数：0 度数为2的结点数：4 树的深度：假设根结点为第一层，则树的深度为 4 树的度：2 结点B的双亲结点：A 结点B的左孩子：D 结点B的右孩子：E 结点D的祖先：A 从结点A到结点H为一条路径，路径长度为：3
本文代码思路来自书籍《Python程序员面试宝典》，书中部分代码有问题，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。希望大家多多支持。
大家好，我是老表 觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python 关注后回复：1024，可以领取精选编程学习电子书籍。
