树

一、树

什么是树？

N个结点构成的有限集合。 树中有一个称为”根(Root)”的特殊结点，其余结点可分为若干个互不相交的树，称为原来结点的”子树”。

二、常用概念

高度：从叶结点开始自底向上逐层累加的。

深度：从根节点开始自上向下逐层累加的。

层数：

完全二叉树

定义：如果一个树，除去最后一层为满二叉树，而且最后一层节点依次从左至右分布，则为完全二叉树
特性：对于一个完全二叉树从左至右按层次编号为1至n，有以下特性

1. 对于 i > 1 ，它的父节点为 i / 2；
2. 如果 2 * i > n，那么i肯定没有左节点，否则左节点应该是 2 * i
3. 如果 2*i+1 > n，那么i肯定没有右节点

例子：堆排序算法