二叉树
6.2.1 二叉树的概念
二叉树(Binary Tree)是结点的有限集合，这个集合或者为空，或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树,且子树有左右之分,次序不能颠倒。
二叉树是一种重要的树型结构,但二叉树不是树的特例。二叉树的5种形态分别为:空二叉树、只有根结点的二叉树、根结点和左子树、根结点和右子树、根结点和左右子树。
二叉树与树的区别:二叉树中每个结点的孩子至多不超过两个,而树对结点的孩子数无限制;另外,二叉树中结点的子树有左右之分,而树的子树没有次序。思考一棵度为2的树与一棵二叉树有什么区别?
【例6.2】树与二叉树有什么区别?
区别有两点:
(1)二叉树的一个结点至多有两个子树,树则不然;
(2)二叉树的一个结点的子树有左右之分,而树的子树没有次序。
【例6.3】分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。
如图6.11(a)所示,具有3个结点的树有两种不同形态。
如图6.11(b)所示,具有3个结点的二叉树有以下5种不同态。
6.2.2 二叉树的性质
性质1: 二叉树第i层上的结点数目最多为2^i-1(i>=1)
数学归纳法证明。
证明:
归纳基础: i=1时，有2^i-1=2^0=1，因为第1层上只有一个根结点，所以命题成立。
归纳假设: 假设对所有的j(1<=j
归纳步骤: 根据归纳假设，第i-1层上至多有2^i-2个结点。由于二叉树的每一个结点至多有两个孩子，故第i层上的结点数，至多是第i-1层上的最大结点数的2倍，即j=i时，该层上至多有2x2^i-2=2^i-1个结点，故命题成立。
性质2: 深度为k的二叉树至多有2k-1个结点(k>=1)
证明: 在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此，利用性质1可得，深度为k 的二叉树的结点数至多为: 2^0+2^1+...+2^k-1=2^k-1 故命题成立。
性质3: 任意二叉树中，若叶结点的个数为n0, 度为2的结点数为n2，则n0=n2+1。
证明: 设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2，,所以其结点总数:
n=n0+n1+n2 (式7.1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点的总效是n1+2*n2, 但树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为:
n=n1+2*n2+1 (式7.2)
由式7.1和式7.2得 n0=n2+1
两种特殊形态的二叉树: 满二叉树和完全二叉树，如图6.12所示。
深度为k且有2^k-1个结点的二叉树称为满二叉树。
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
根据定义:
(1) 满二叉树是完全二叉树，反之不成立;
(2) 对于完全二叉树，若某结点无左孩子，则必无右孩子，该结点为叶结点。
性质4: 具有n个结点的完全二叉树的深度为[log2n]+1 ([log2n]表示该值的最大整数)
证明: 设深度为k, 则根据性质2和完全二叉树的定义有
2^(k-1)-1< n <= 2^k-1即2^(k-1)<=n<2^k
于是 k-1<=log2n
所以 k-1=[log2n]，
即 k=[1og2n]+1
性质5: 如果对一棵有n个结点的完全二叉树的结点按层次编号(即自上而下，自左至右)，则对任一结点i(1<=i<=n),有
(1) 如果i=1，则结点i是二叉树的根，无双亲; 如果i>1,则其双亲是编号为[i/2」的结点。
(2) 如果2*i>n, 则结点i无左孩子; 否则其左孩子是编号为2*i的结点。
(3) 如果2*i+1>n, 则结点i无右孩子; 否则其右孩子是编号为2*i+1的结点。
(4) 若i为奇数且不为1, 则结点i的左兄弟的编号是i-1; 否则，结点i无左兄弟。
(5) 若i为偶数且小于n, 则结点i的右兄弟的编号是i+1; 否则，结点i无右兄弟。
6.2.3 二叉树的存储结构
1. 二叉树的顺序存储结构
对于完全二叉树可以采用顺序存储结构(即一维数组)进行存储，按照性质5对结点进行编号，编号为i的结点存放在数组第i个元素所分配的存储单元中，完全二叉树结点之间的逻辑关系通过数组元素的下标体现。图6.13 是图的顺序存储结构。
对于非完全二叉树，通过补设一些“虚结点”，使得二叉树的结点的编号与完全二叉树相同，再进行顺序存储。
每个“虚结点”都将占据一个数组元素存储单元。
非完全二叉树采用顺序存储结构会造成存储空间的浪费。
2.二叉树的链式存储结构
二叉树除了可以采用顺序存储结构实现存储外，还可以采用链式存储结构进行存储，与采用顺序存储结构相比，采用链式存储结构实现二叉树的存储显得更自然。二叉树最常用的链式存储结构是二叉链，每个结点包含三个域，分别是数据元素域data、左孩子链域lChild和右孩子链域rChild, 结点结构如图6.14 所示。
与单链表带头结点和不带头结点的两种情况相似，二叉链存储结构的二叉树也有带头结点和不带头结点两种。对于图6.13(a)所示的二叉树，带头结点和不带头结点的二叉链存储结构的二叉树如图6.15(a)和6.15(b)所示。
6.2.4 二叉树的遍历
1.二叉树遍历的概念
二叉树的遍历是指沿某条搜索路径访问二叉树，对二叉树中的每个结点访问一次且仅一次。这里的“访问”实际上是指对结点进行某种操作。二叉树的遍历方式有:前序遍历、中序遍历、后序遍历，这些遍历又有先左后右和先右后左之分，如图6.16 所示。
2.前序遍历二叉树
前序遍历算法: 若二叉树非空，先访问根结点，再前序遍历左子树，最后前序遍历右子树。如图6.17 所示为二叉树的搜索路线。遍历图6.17 所示的二叉树时，得到的先序序列为: A, B，D，C，E，F。
3.中序遍历二叉树
中序遍历算法: 若二叉树非空，先中序遍历左子树，再访问根节点，最后中序遍历右子树。
遍历图6.17 所示的二叉树时，得到的中序序列为: D，B, A, E，C，F。
4.后序遍历二叉树
后序遍历算法: 若二叉树非空，先后序遍历左子树，再后续遍历右子树，最后访问根节点。
后序遍历图6.17 所示的二叉树时，得到的后序序列为: D，B，E，F, C, A。
在遍历的过程中，需要注意:
(1) 在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历; 若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。
(2) 上述3 种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲) 结点和后继(即孩子) 结点的概念，对上述3 种线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。
图6.17 所示的二叉树中的结点C,其前序前趋结点是D,前序后继结点是E; 中序前趋结点是E，中序后继结点是F; 后序前趋结点是F,后序后继结点是A。但是就该树的逻辑结构而言，C 的前趋结点是A，后继结点是E 和F。
5.二叉树遍历算法的实现
二叉树的遍历采用递归算法比较简单，在定义二叉树二叉链存储结构后，先手工创建图6.17 所示的无头结点的二叉链树，再调用3 种遍历算法来输出遍历结果，具体代码如下:
运行结果
感谢大家阅读由大数据教程分享的“让你更好的理解什么是二叉树?”希望对大家有所帮助，更多精彩内容请关注大数据培训机构官网
