k叉树的性质_⼆叉树的基本性质
(1)在⼆叉树的第k层上，最多有2k-1(k≥1)个结点；
解释：最多的时候是满⼆叉树，它的第1层有21-1=1个结点；第2层有22-1=2个结点；第3层23-1=4个结点；第4层有24-1=8个结点；……
(2)深度为m的⼆叉树最多有2m-1个结点，最少有m个结点；
(3)对于任意⼀棵⼆叉树，度为0的结点(即叶⼦结点)总是⽐度为2的结点多⼀个；即如果其叶⼦结点数为N0，⽽度数为2的结点总数为N2，则N0=N2+1；(4)具有n个结点的⼆叉树，其深度⾄少为[log2n]+1，其中[log2n]+1表⽰取log2n的整数部分；
(5)给定N个节点，能构成h(N)种不同的⼆叉树；h(N)为的第N项。h(n)=C(n,2*n)/(n+1)。
(6)具有n个结点的完全⼆叉树的深度为[log2n]+1；
(7)设完全⼆叉树共有n个结点。如果从根结点开始，按层序(每⼀层从左到右)⽤⾃然数1，2，….n给结点进⾏编号(k=1,2….n)，有以下结论：①若k=1，则该结点为根结点，它没有⽗结点；若k>1，则该结点的⽗结点编号为INT(k/2)；②若2k≤n，则编号为k的结点的左⼦结点编号为2k；否则该结点⽆左⼦结点(也⽆右⼦结点)；③若2k+1≤n，则编号为k的结点的右⼦结点编号为2k+1；否则该结点⽆右⼦结点。
性质1  在⼆叉树的第i层上⾄多有2i-1个结点(i>=1)。
证明 采⽤归纳法证明此性质。
当i=1时，只有⼀个根结点，2i-1=20=1，命题成⽴。
现在假定对所有的j，1<=j
那么可以证明j＝i时命题也成⽴。由归纳假设可知，第i－1层上⾄多有2i-2个结点。
由于⼆叉树每个结点的度最⼤为2，故在第i层上最⼤结点数为第i－1
层上最⼤结点数的⼆倍， 即2×(2i-2)＝2i-1。
性质2  深度为k的⼆叉树⾄多有2k－1个结点(k>=1)。
证明  第i层的结点数为xi(1≤i≤k)，深度为k的⼆叉树的结点数为M，xi最多为2i-1，则有：
性质3  对于⼀棵⾮空的⼆叉树，如果叶⼦结点数为n0，度数为2的结点数为n2，则有n0＝n2＋1。
证明  设⼆叉树中度为1的结点数为n1，⼆叉树中总结点数为N，因为⼆叉树中所有结点均⼩于或等于2，所以有：
N＝n0＋n1＋n2            (5-1)
再看⼆叉树中的分⽀数，除根结点外，其余结点都有⼀个进⼊分⽀，设B为⼆叉树中的分⽀总数，则有：
N＝B＋1。
由于这些分⽀都是由度为1和2的结点发出的，所以有：
B＝n1+2*n2
N＝B＋1＝n1＋2×n2＋1      (5-2)
由式(5-1)和(5-2)得到：
二叉树的基本性质n0＋n1＋n2 = n1＋2×n2＋1
n0＝n2＋1
性质4  具有n个结点的完全⼆叉树的深度k为。
证明  设所求完全⼆叉树的深度为k，根据完全⼆叉树的定义和性质2可知，k-1层满⼆叉树的结点个数为n时，有
2k－1－1
即                      2k－1≤n<2k
对不等式取对数，有
k－1≤log2n
由于k是整数，所以有k-1＝，k=，结论成⽴。
性质5  如果对⼀棵有n个结点的完全⼆叉树的结点按层序编号(从第1层到第+1层，每层从左到右)，则对任⼀结点i(1<=i<=n)，有：
(1)如果i＝1，则结点i⽆双亲，是⼆叉树的根；如果i>1，则其双亲是结点。
(2)如果2i>n，则结点i为叶⼦结点，⽆左孩⼦；否则，其左孩⼦是结点2i。
(3)如果2i＋1>n，则结点i⽆右孩⼦；否则，其右孩⼦是结点2i＋1。
此外，若对⼆叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i－1)/2，左孩⼦的编号为2i＋1，右孩⼦的编号为2i＋2。
此性质可采⽤数学归纳法证明。证明略。
这个性质是⼀般⼆叉树顺序存储的重要基础。
下⾯介绍两种特殊形态的⼆叉树：满⼆叉树和完全⼆叉树。
⼀棵深度为k且由2k-1个结点的⼆叉树称为满⼆叉树。图5-3(a)就是⼀棵满⼆叉树，对结点进⾏了顺序编号。图5-3(b)图则不是满⼆叉树，因为，虽然其所有结点要么是含有左右⼦树的分⽀结点，要么是叶⼦结点，但由于其叶⼦未在同⼀层上，故不是满⼆叉树。
(a) ⼀棵满⼆叉树                  (b) ⼀棵⾮满⼆叉树
图5-3 满⼆叉树和⾮满⼆叉树⽰意图
⼀棵深度为k，有n个结点的⼆叉树当且仅当其每⼀个结点都与深度为k的满⼆叉树中编号从1⾄n的结点⼀⼀对应时，则这棵⼆叉树称为完全⼆叉树。完全⼆叉树的特点是：叶⼦结点只能出现在最下层和次下层，且最下层的叶⼦结点集中在树的左部。显然，⼀棵满⼆叉树必定是⼀棵完全⼆叉树，⽽完全⼆叉树未必是满⼆叉树。如图5-4(a)所⽰为⼀棵完全⼆叉树，图5-4(b)为⼀棵⾮完全⼆叉树。
(a) ⼀棵完全⼆叉树            (b) ⼀棵⾮完全⼆叉树
图5-4 完全⼆叉树和⾮完全⼆叉树⽰意图
⼆叉树的遍历
(1)前序遍历(DLR)，⾸先访问根结点，然后遍历左⼦树，最后遍历右⼦树；(2)中序遍历(LDR)，⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树；(3)后序遍历(LRD)，⾸先遍历左⼦树，然后遍历右⼦树，最后访问根结点。
完全⼆叉树的定义：深度为k，有n个结点的⼆叉树当且仅当其每⼀个结点都与深度为k的满⼆叉树中编号从1⾄n的结点⼀⼀对应时，称为完全⼆叉树。特点：叶⼦结点只可能在层次最⼤的两层上出现；对任⼀结点，若其右分⽀下⼦孙的最⼤层次为l，则其左分⽀下⼦孙的最⼤层次必为l 或l+1满⼆叉树：⼀棵深度为k，且有2的(k)次⽅－1个节点的⼆叉树特点：每⼀层上的结点数都是最⼤结点数满⼆叉树肯定是完全⼆叉树完全⼆叉树不⼀定是满⼆叉树
满⼆叉树是指除最后⼀层外，每⼀层上的所有结点有两个⼦结点，则k层上有2k-1个结点深度为m的满⼆叉树有2m-1个结点。完全⼆叉树是指除最后⼀层外，每⼀层上的结点数均达到最⼤值，在最后⼀层上只缺少右边的若⼲结点。⼆叉树存储结构采⽤链式存储结构，对于满⼆叉树与完全⼆叉树可以按层序进⾏顺序存储。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。