6.3树的存储结构( 四 ) _结点

3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树
二叉树具有五种基本形态:
1.空二叉树。
2.只有一个根结点。
3.根结点只有左子树。
4.根结点只有右子树。
5.根结点既有左子树又有右子树。
5个结点的树有5中二叉树的形态
6.4.2 特殊二叉树 1.斜树
顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树
上面的树2就是左斜树，树5就是右斜树
其实线性表结构就可以理解为是树的一种极其特殊的表现形式
2.满二叉树
人有悲欢离合，月有阴晴圆缺，此事古难全
理想是完美的，不完美才是人生
完美的二叉树就叫满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：
(1)叶子只能出现在最下一-层。出现在其他层就不可能达成平衡。
(2)非叶子结点的度一-定是2 。否则就是“缺胳膊少腿”了。
(3)在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
3.完全二叉树
对一棵具有n个结点的二叉树按层序编号,如果编号为i (1≤i≤n)的结点与同
样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树
满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树
只能最后一层右边缺，其他地方缺都必须是连续的，不连续就不是完全二叉树
如下图所示
完全二叉树的特点：
1.叶子结点只能出现在最下两层
2.最下层的叶子一定集中在左部连续位置
3.倒数二层，若有叶子结点，一定都在右部连续位置。
4.如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
5.同样结点数的二叉树，完全二叉树的深度最小
6.5 二叉树的性质 6.5.1二叉树性质
性质1:在二叉树的第i层上至多有2^（i-1）个结点(i≥1) 。(带入即可理解)
性质2:深度为k的二叉树至多有2^k - 1个结点(k>1) 。
如果有一层，至多有1 = 2 的 0次方 - 1 个结点
如果有二层，至多有1 + 2 = 3 = 2 的平方 - 1 个结点
…
性质3:对任何一棵二叉树T,如果其终端结点数为No,度为2的结点数为n2,则No = N2 + 1
性质4:具有n个结点的完全二叉树的深度为[log2n]+1 (Lx]表示不大于x的最大整数) 。
这个其实就是性质二的倒数，反过来求k的值的
性质5:如果对一棵有n个结点的完全二叉树(其深度为log2n]+1) 的结点按层序编号(从第1层到第log2n]+1层，每层从左到右)，对任一结点i (1≤i≤n)
有:
1.如果i=1，则结点i是二叉树的根，无双亲;如果i>1,则其双亲是结点li/2」。
2.如果2i>n，则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i 。
3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1 。
如下图
对于第一条来说是很显然的，i=1 时就是根结点。i>1 时，比如结点7,它的双亲就是l7/2]=3,结点9,它的双亲就是[9/2]=4
第二条，比如结点6,因为2X6=12超过了结点总数10,所以结点6无左孩子，它是叶子结点。同样，而结点5,因为2X5=10正好是结点总数10,所以它的左孩子是结点10
第三条，比如结点5,因为2X5+1=11,大于结点总数10,所以它无右孩子。而结点3，因为2X3+1=7小于10,所以它的右孩子是结点7
6.6 二叉树的存储结构 6.6.1二叉树的顺序存储
如果有一颗深度为k的右斜树，它有k个结点，却要分配2的k次方减1个存储单元，他会很浪费如下图，所以顺序存储结构一般用于完全二叉树