树

在数据结构中，树的定义：

树是n(n>=0)个节点的有限集。当n=0时，称为空树，在任意一个非空树中，有如下特点

根节点之外没有子节点的叫叶子节点

有孩子的叫父节点

由同一个父节点衍生出来的叫兄弟节点

根的最大层级树，被称为树的高度，下面的树高度为4

比较典型的树

二叉，顾名思义，每个节点最多有两个子节点。

二叉树有许多特殊形式，每一种都有自己的作用，但是最主要的应用还是进行查找操作和维持相对顺序

一个二叉树的所有非叶子节点都存在左右孩子节点，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

每一个分支都是满的

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号从1到n。

如果这个树所有节点和同样深度的满二叉树的编号从1到n节点位置相同，则这个二叉树为完全二叉树。

节点位置和对应的满二叉树完全相同如下：

完全二叉树的条件没有满二叉树那么苛刻：

满二叉树要求所有分支都是满的，而完全二叉树只需要保证最后一个节点之前的节点是满的即可。

二叉树是逻辑存储。

物理存储可用：

链式存储是二叉树最直观的存储方式，每一个链表节点拥有data变量和左右节点指针

按照二叉树的顺序填充，有空缺就空出来

这样可以方便的在数组中定位二叉树的孩子节点和父节点

假设父下标是parent，那么他的左子节点的下标就是2*parent+1，右子节点的下标就是2*parent+2

反过来假设一个做子节点的下标是leftChild，那么他的父节点下标就是(leftChild-1)/2

但是对于稀疏的二叉树来说，用数组表示浪费空间，二叉堆才适用于数组表示。