程序员必备算法

1、什么是树？

  什么是树？就是又数据组成的一种数据结构，按照平面展示出来就像一颗倒过来的树。

2、树的基本概念

  1、树的节点称呼：节点、根节点(只有一个，就是第一个)、父节点、子节点、兄弟节点(兄弟节点只能是从同一个父节点的才能称之为兄弟节点)。

  2、一颗树可以没有任何节点，称之为空树。

  3、一棵树可以只有一个节点，那就是根节点。

  3、子树、左子树、右边子树。顾名思义，就是在上面的树中，随便划一块出来，就是子树了。按照子树根在根父节点的左边和右边，就叫左子树和右子树了。

  4、节点的度：度→就是子树的个数。比如上图中，节点1的度就是5，有5棵子树；节点2的度为2，有两颗子树；节点6的度为1，有一颗子树；节点21的度为0，没有子树。

  5、树的度：就是从整颗树中找到度最大的节点，那么这个节点的度就是整颗树的度。比如上图中度最大的节点是1这个节点，度为5，因此整颗书的度就是5。

  6、叶子节点：度为0的节点。

  7、非叶子节点：度不为0的节点。

  8、层数：就是有多少层嘛，上图中层数为4。

  9、节点的深度：从根节点到当前节点的唯一一条路径上的节点总数。深度：从上到下数

  10、节点的高度：从当前节点到最远叶子节点的路径上的节点总数。  高度：从下往上数

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

  12、树的高度：所有节点中的高度最大值。树的深度和高度相等

3、二叉树

  1、非空二叉树的第i层最多有2^i-1个节点（i >=i）

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

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

  4、完全二叉树：叶子节点只会出现在最后2层，且所有节点都是从上到下从左到右排列。满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。