二叉树模型基础知识（5分钟带你认识二叉树）

二叉树模型基础知识（5分钟带你认识二叉树）度为0的结点称为叶子结点。2.2>叶子结点2> 二叉树结点的属性2.1>结点的度结点所拥有的子树的个数称为该结点的度。叶子结点的度为0。

原创： 老表 简说Python

今日问题

""" 介绍二叉树的基础知识 目录 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程序员面试宝典》，书中部分代码有问题，文中已经修改过了，并添加上了丰厚的注释，方便大家学习.

最后，我自己是一名从事了多年开发的Python老程序员，辞职目前在做自己的Python私人定制课程，今年年初我花了一个月整理了一份最适合2019年学习的Python学习干货，可以送给每一位喜欢Python的小伙伴，想要获取的可以关注我的头条号并在后台私信我：01，即可免费获取。