树

节点 , 根节点 , 父节点 , 子节点 , 兄弟节点
一棵树可以没有任何节点,称为 空树
一棵树可以只有一个节点,也就是只有根节点

子树, 左子树 , 右子树
节点的度(degree) : 子树的个数
树的度: 所有节点度中的最大值
叶子节点(leaf): 度为0的节点
非叶子节点: 度不是0的节点
层数(level): 根节点在第一层 , 根节点的子节点在第2层, 以此类推
节点的深度(depth): 从根节点到当前节点的唯一路径上的节点总数
节点的高度(height): 从当前节点到最远叶子节点的路径上的节点总数
树的深度: 所有节点深度中的最大值
树的高度: 所有节点高度中最大的值
一般来说: 树的深度 等于 树的高度

有序树: 树中任意节点的子节点之间有顺序关系
无序树(自由树): 树中任意节点的子节点之间没有顺序关系

森林: 由 m(m > 0) 课互不相交的树组成的集合

二叉树 (Binary Tree)
每个节点的度最大为2
左子树和右子树是有顺序的
即使某节点只有一颗子树, 也要区分左右子树
非空二叉树的第i层,最多有个节点(i >= 1)
在高度为h的二叉树上最多有-1个节点(h >= 1)
对于任何一颗非空二叉树, 如果叶子节点个数为n0,度为2的节点个数为n2,则有: n0 = n2 + 1;
假设度为1的节点个数为n1 , 那么二叉树的节点总数 n = n0 + n1 + n2;
二叉树的边数 T = n1 + 2* n2 = n -1 = n0 + n1 + n2 —> 换算得 n2 = n0 -1 则 n0 = n2 + 1;

真二叉树( Proper Binary Tree)
所有节点的度都要么为0 , 要么为2

满二叉树(Full Binary Tree)
所有节点的度都要么为0 , 要么为2 ,且所有的叶子节点都在最后一层
在同样高度的二叉树中,满二叉树的叶子节点数量最多,总结点数量最多
满二叉树一定是真二叉树,真二叉树不一定是满二叉树.
假设满二叉树的高度为h (h >= 1),那么
第i层的节点数量:
叶子节点的数量:
总节点数量
树的高度

完全二叉树(Complete Binary Tree)
叶子节点只会出现最后2层,且最后1层的叶子节点都靠左对其
完全二叉树从根节点至倒数第二层是一颗满二叉树
满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树.
度为1的节点只有左子树.
度为1的节点要么是1个,要么是0个.
同样节点数量的二叉树,完全二叉树的高度是最小的
假设完全二叉树的高度为h(h>=1),那么
至少有个节点
最多有个节点
总结点数量为n 则 —> —>
floor 向下取整 , celing 向上取整
一颗有n个节点的完全二叉树(n>0),从上到下,从左到右对节点从0开始编号,对任意第i个节点
如果i = 0 ,它是根节点
如果i > 1 , 它的父节点编号为floor((i-1)/2)
如果2i + 1 <= n-1 ,它的左子节点编号为2i+1
如果2i + 1 > n+1 , 它是没有左子节点
如果2i + 2 <= n-1 ,它的右子节点编号为2i+2

总节点数量n :
如果n是偶数 叶子节点数量n0 = n / 2;
如果n是奇数 叶子节点数量n0 = (n + 1) /2
则: n0 = floor((n + 1) /2) java中: int n0 = (n + 1) >> 1