树

有句话叫“种下一棵树最好的时候是十年前，其次是现在”

深以为然，下面就来说树

从二叉树开始

五种基本形态

1. null 没有任何元素

2. 0 只有一个根节点

3. 只有根节点和左节点

4. 只有根节点和右节点

5. 根节点和左右节点

特殊的二叉树：

1. 斜二叉树 只有左子树或只有右子树的二叉树皆为斜二叉树

2. 满二叉树 除最后一层节点无任何子节点外，每一层所有节点都有两个子节点

3. 完全二叉树 有n个结点的二叉树，对树中结点按从上之下，从左至右的顺序进行编号，编号为i(1<=i<=n)结点与满二叉树中编号为i结点在二叉树中位置相同

二叉树的性质

节点的度 节点所拥有的子节点的个数

树的度 树中各节点的度的最大值，所以二叉树的度都为2

节点的层数 规定根节点的层数为1，其余节点层数顺序递增

树的深度 树中所有节点的最大层数

在二叉树的第i层上最多有2^(i-1)个节点 （i>=1)

二叉树中如果深度为k，那么最多有2^k-1个节点 (k>=1)

对任何非空二叉树T，若N0表示度数为0的结点，N2表示度数为2的节点，则有N0=N2+1

具有n个节点的完全二叉树的深度为Log2N+1

基本操作

遍历

前序遍历 根 => 左 => 右

中序遍历 左 => 根 => 右

后序遍历 左 => 右 => 根

插入

删除

二叉树的存储结构

顺序存储结构

堆