完全二叉树的定义
winra-三峡大坝的利与弊
2023年2月23日发(作者：丁俊发)k叉树的性质_⼆叉树的⼀些性质
树的介绍
1.树的定义
树是⼀种数据结构，它是由n(n>=1)个有限节点组成⼀个具有层次关系的集合。
把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：
(01)每个节点有零个或多个⼦节点；
(02)没有⽗节点的节点称为根节点；
(03)每⼀个⾮根节点有且只有⼀个⽗节点；
(04)除了根节点外，每个⼦节点可以分为多个不相交的⼦树。
2.树的基本术语
若⼀个结点有⼦树，那么该结点称为⼦树根的"双亲"，⼦树的根是该结点的"孩⼦"。有相同双亲的结点互为"兄弟"。⼀个结点的所有⼦树上的
任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度：结点拥有的⼦树的数⽬。
叶⼦：度为零的结点。
分⽀结点：度不为零的结点。
树的度：树中结点的最⼤的度。
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。
树的⾼度：树中结点的最⼤层次。
⽆序树：如果树中结点的各⼦树之间的次序是不重要的，可以交换位置。
有序树：如果树中结点的各⼦树之间的次序是重要的,不可以交换位置。
森林：0个或多个不相交的树组成。对森林加上⼀个根，森林即成为树；删去根，树即成为森林。
⼆叉树的介绍
1.⼆叉树的定义
⼆叉树是每个节点最多有两个⼦树的树结构。它有五种基本形态：⼆叉树可以是空集；根可以有空的左⼦树或右⼦树；或者左、右⼦树皆为
空。
2.⼆叉树的性质
⼆叉树有以下⼏个性质：TODO(上标和下标)
性质1：⼆叉树第i层上的结点数⽬最多为2{i-1}(i≥1)。
性质2：深度为k的⼆叉树⾄多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的⼆叉树的⾼度⾄少为log2(n+1)。
性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
2.1性质1：⼆叉树第i层上的结点数⽬最多为2{i-1}(i≥1)
证明：下⾯⽤"数学归纳法"进⾏证明。
(01)当i=1时，第i层的节点数⽬为2{i-1}=2{0}=1。因为第1层上只有⼀个根结点，所以命题成⽴。
(02)假设当i>1，第i层的节点数⽬为2{i-1}。这个是根据(01)推断出来的！
下⾯根据这个假设，推断出"第(i+1)层的节点数⽬为2{i}"即可。
由于⼆叉树的每个结点⾄多有两个孩⼦，故"第(i+1)层上的结点数⽬"最多是"第i层的结点数⽬的2倍"。即，第(i+1)层上的结点数⽬最⼤值
=2×2{i-1}=2{i}。
故假设成⽴，原命题得证！
2.2性质2：深度为k的⼆叉树⾄多有2{k}-1个结点(k≥1)
证明：在具有相同深度的⼆叉树中，当每⼀层都含有最⼤结点数时，其树中结点数最多。利⽤"性质1"可知，深度为k的⼆叉树的结点数⾄多
为：
20+21+…+2k-1=2k-1
故原命题得证！
2.3性质3：包含n个结点的⼆叉树的⾼度⾄少为log2(n+1)
证明：根据"性质2"可知，⾼度为h的⼆叉树最多有2{h}–1个结点。反之，对于包含n个节点的⼆叉树的⾼度⾄少为log2(n+1)。
2.4性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
证明：因为⼆叉树中所有结点的度数均不⼤于2，所以结点总数(记为n)="0度结点数(n0)"+"1度结点数(n1)"+"2度结点数(n2)"。由此，
得到等式⼀。
(等式⼀)n=n0+n1+n2
另⼀⽅⾯，0度结点没有孩⼦，1度结点有⼀个孩⼦，2度结点有两个孩⼦，故⼆叉树中孩⼦结点总数是：n1+2n2。此外，只有根不是任何
结点的孩⼦。故⼆叉树中的结点总数⼜可表⽰为等式⼆。
(等式⼆)n=n1+2n2+1
由(等式⼀)和(等式⼆)计算得到：n0=n2+1。原命题得证！
3.满⼆叉树，完全⼆叉树和⼆叉查找树
3.1满⼆叉树
定义：⾼度为h，并且由2{h}–1个结点的⼆叉树，被称为满⼆叉树。
3.2完全⼆叉树
定义：⼀棵⼆叉树中，只有最下⾯两层结点的度可以⼩于2，并且最下⼀层的叶结点集中在靠左的若⼲位置上。这样的⼆叉树称为完全⼆叉
树。
特点：叶⼦结点只能出现在最下层和次下层，且最下层的叶⼦结点集中在树的左部。显然，⼀棵满⼆叉树必定是⼀棵完全⼆叉树，⽽完全⼆
叉树未必是满⼆叉树。
3.3⼆叉查找树
定义：⼆叉查找树(BinarySearchTree)，⼜被称为⼆叉搜索树。设x为⼆叉查找树中的⼀个结点，x节点包含关键字key，节点x的key值记
为key[x]。如果y是x的左⼦树中的⼀个结点，则key[y]=key[x]。
在⼆叉查找树中：
(01)若任意节点的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；
(02)任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；
(03)任意节点的左、右⼦树也分别为⼆叉查找树。
(04)没有键值相等的节点(noduplicatenodes)。