二叉树

树的概念：

节点，根结点，父节点，子节点，兄弟节点

子树，左子树，右子树

节点的度：子树的个数

叶子节点：度为0的节点

非叶子节点：度不为0的节点

节点的深度：从根结点到当前节点的唯一路径上的节点总数

节点的高度：从当前节点到最远的叶子节点的路径上的节点总数

树的深度：所有节点深度中的最大值

树的高度：所有节点高度中的最大值

树的深度=树的高度

没有任何节点称为空数

二叉树：

每个节点的度最大为2（最多有2棵字数）

左子树和右子树是有顺序的

非空二叉树的第i层，最多有2^(i-1)个节点

在高度为h的二叉树上最多有2^h-1个节点

对于任何一棵非空二叉树，如果叶子节点个数为n0,度为2的节点个数为n2,则n0=n2+1

真二叉树：所有节点的度要么为0，要么为2

满二叉树：所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层

满二叉树一定是真二叉树，真二叉树不一定是满二叉树

满二叉树第i层的节点数量为2^(i-1)，叶子节点数量为2^(h-1)

满二叉树的总结点数量为n=2^h-1

完全二叉树：叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐

满二叉树一定是一棵完全二叉树，完全二叉树不一定是满二叉树

度为1的节点只有左子树，度为1的节点要么是1个，要么是0个

同样节点数量的二叉树，完全二叉树的高度最小

假设完全二叉树的高度为h(h>=1),那么至少有2^(h-1)个节点，最多有2^h-1个节点

总节点数量为n

h=log2n向下取整+1,向下取整是floor,向上取整是ceiling

h=floor(log2n)+1

一棵有n个节点的完全二叉树,对任意第i个节点

如果i=1,它是根结点

如果i>1,它的父节点的编号为floor(i/2)

如果2i<=n,它的左子节点编号为2i

如果2i>n,它无左子节点

如果2i+1<=n,它的右子节点编号为2i+1

如果2i+1>n,它无右子节点

如果完全二叉树的n1（有一个子节点）为0，叶子节点个数n0=n/2

如果n1为1，叶子节点个数为n0=(n+1)/2

因为程序会自动向下取整  n0=(n+1) >> 1