二叉树的定义及其主要特征

二叉树的定义及其主要特征

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两颗子树，并且二叉树的子树有左右之分，次序不能颠倒。

二叉树是n(n≥0)个结点的有限集合：其或者为空二叉树(n=0)，或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分是左子树还是右子树。其有五种基本形态如下：

二叉树与度为2的有序树的区别：

（1）度为2的树至少有3个结点（根结点），而二叉树可以为空；

（2）度为2的有序树的孩子结点的左右次序是相对于另一孩子结点而言的，若某个结点只有一个孩子结点，则这个孩子结点无需分左右。但二叉树左右孩子是确定的。

几个特殊的二叉树

1.满二叉树

一棵高度为h，且含有2^h-1个结点的二叉树称为满二叉树，即树中的每层都含最多结点。自上而下，自左至右对满二叉树编号，对于编号为i的结点，若有双亲，其双亲为i/2，若有左孩子，则左孩子为2i；若有右孩子，则右孩子为2i+1。

2.完全二叉树

设一个高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

其具有如下特点：

（1）若i≤n/2，则结点i为分支结点，否则为叶子结点；

（2）叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上；

（3）若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子；

（4）按层序编号后，一旦出现某结点（编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点；

（5）若n为奇数，则每个分支节点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子。

课后习题

【2018年真题】设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2 个子结点。若 T有 k个叶结点，则T的结点总数是（）。

A . 2k-1 B. 2k C. k2 D. 2k-1

参考答案：A

【2011年真题】若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）

A．257

B．258

C．384

D．385

解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1（总结点数为偶数），故而即2n=768。

【2009年真题】已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是（）。

A． 39 B．52 C．111 D．119

参考答案：C

答案解析：考查完全二叉树的特点。

完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7，显然树高为 7时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 8×2＝16 个叶结点，故完全二叉树的结点个数最多为 2^7-1-16=111 个结点。

【2016年真题】如果一颗非空k（k>=2）叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。请回答下列问题并给出推导过程。

（1）若T有m个非叶结点，则T中的叶结点有多少个？

（2）若T的高度为h（单结点的树h=1），则T的结点数最多为多少个？最少为多少个？

参考答案：

（1）根据定义，正则k叉树中仅含有两类结点：叶结点（个数记为n0）和度为k的分支结点（个数记为nk）。树T中的结点总数n=n0+nk=n0+m。树中所含的边数e=n-1，这些边均为m个度为k的结点发出的，即e=mk。整理得：n0+m=mk+1，故n0=(k-1)*m+1。

（2）高度为h的正则k叉树T中，含最多结点的树形为：除第h层外，第1到第h-1层的结点都是度为k的分支结点，而第h层均为叶结点，即树是“满”树。此时第j（1<=j<=h）层结点数为k^(j-1)，结点总数M1为：

M1 = 1 + k + k^2 + ... + k^(h-1) = (k^h - 1) / (k - 1)

含最少结点的正则k叉树的树形为：第1层只有根结点，第2到第h-1层仅含1个分支结点和k-1个叶结点，第h层有k个叶结点。即除根外第2到第h层中每层的结点数均为k，故T中所含结点总数M2位：

M2 = 1 + (h-1) * k