4.树

树的基本概念

节点、根节点、父节点、子节点、兄弟节点（同层节点不一定是兄弟节点，兄弟节点必须有同一个父节点）

• 空树：没有任何节点

• 子树：2的子树有两个，分别是21，以及 22-221、222、223

• 左子树：2的左子树 21

• 右子树：2的右子树 22-221、222、223

• 节点的度：子树的个数 1的度 = 5，2的度 = 2，3的度 = 1

• 树的度：所有节点度中最大值，上图树的度 = 5

• 叶子节点：度为0的节点，如21、221、31、4

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

• 层数：根节点在第一层，根节点的子节点在第二层，以此类推

• 节点的深度：从根节点到当前节点的唯一路径上的节点数，221到根节点1的路径上一共有三个点，1，2，221，深度为3

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

• 树的深度、树的高度，分别取节点深度、节点高度的最大值，树的深度=树的高度

• 有序树：树中任意节点的子节点之间有顺序关系

• 无序树：树种任意节点的子节点之间没有顺序关系，也叫自由树

• 森林：由一颗或多颗不相交的树组成的集合

二叉树（Binary Tree）

1. 每个节点的度最大为2
2. 左子树和右子树是有顺序的
3. 即便节点只有一棵树，也区分左子树、右子树

真二叉树（Full Binary Tree）：所有的节点的度要么为0要么为2

满二叉树（Perfect Binary Tree）：真二叉树，且所有叶子节点都在最后一层

完全二叉树：叶子节点在最后两层，编号为i的节点与满二叉树中编号为i的节点在二叉树中位置相同。由此得出：度为1的节点数要么为0，要么为1，且一个度的节点为左节点。

完全二叉树的特性

节点相同的二叉树中，完全二叉树高度最小

假设完全二叉树的高度为h(h>1)，那么

最少节点数为：2^h-1=2⁰+2¹+2²+...+2^h-2+1

最大节点数为：2^h-1=2⁰+2¹+2²+...+2^h-1(满二叉树)

总结点数n:

2^h-1≤n<2^h

h-1≤log₂n<h

floor 向下取整函数
ceiling 向上取整函数

根节点为1，第i个编号：父节点=floor(i/2)，左节点=ix2，右节点ix2+1

根节点为0，第i个编号：父节点=floor((i-1)/2)，左节点=ix2+1,右节点ix2+2

将完全二叉树的节点分为三部分，叶子节点为n0,度为2的节点为n1,度为2的节点为n2，那么总结点 n = n0+n1+n2,其中，n0 = n2+1，n1 = 0或者1，由此推出，n = 2*n2+n1