二叉树

二叉树的特点

1.每个节点的度最大为2（最多拥有2颗子树）
2.左子树和右子树是有顺序的
3.即使某节点只有一颗树，也要区分左右子树

二叉树的性质

1.非空二叉树的第i层，最多有2的(i-1)次方个节点(i>=1)
2.高度为h的二叉树上最多有2的h次方-1个节点(h>=1)
3.对于任何一颗非空二叉树，如果叶子节点的个数为n0，度为2的节点数为n2，则有：n0 = n2 +1
4.假设度为1的节点个数为n1，那么二叉树的节点总数 n = n1 + n2 + n0
5.二叉树的边数 T = n1 + 2*n2 = n -1 = n0 + n1 +n2 -1

真二叉树

所有节点的度要么为0，要么为2

真二叉树@2x.png

满二叉树

所有节点的度都要么为0，要么为2，且所有的叶子节点都在最后一层，在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多，满二叉树一定是真二叉树，真二叉树不一定是满二叉树

假设满二叉树的高度为h(h >=1)，那么第i层的节点数量：2的(i-1)次方，叶子节点的数量：2的h次方-1，总数为n,

完全二叉树

叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐
1.假设完全二叉树的高度为h(h>=1)，那么完全二叉树至少有2的(h-1)次方个节点，最多有2的h次方-1个节点(满二叉树)。
2.假设完全二叉树有n个节点，那个完全二叉树的高度h = log2n +1

wqecs@2x.png

一颗有n个节点的完全二叉树(n >0)，从上到下，从左到右对节点从1开始进行编号，对任意第i个节点
1.如果i = 1，它是根节点
2.如果i >1，他的父节点的编号为floor(i/2)
3.如果2i <= n，那么它的左子节点编号为2i
4.如果2i+1 <=n，它的右子节点编号为2i+1，
5.如果2i +1 >n，那么它无右子节点

总节点数量为n，那么它的叶子节点的数量n0是
n0 = (n +1) >>1

前驱节点

中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点

1.如果node.left != null ，predecessor = node.left.right.right.right....，终止条件：right为null
2.如果node.left == null && node.parent != null，predecessor = node.parent.parent.parent.parent.....，终止条件：node在parent的右子树中
3.如果node.left = null & node.parent == null，那就没有前驱节点