二叉树概念.md

满二叉树

如果二叉树的所有叶子节点都在==最后一层==，并且排满最后一层所有位置，即树的节点总数为$2^n-1$，n为层数，则我们称为满二叉树

完全二叉树

如果二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层在右边连续（即第二层是满的），我们称为完全二叉树

==大顶堆和小顶堆就是完全二叉树，不过是有排序要求的完全二叉树，即所有父节点都大于或等于子节点（大顶堆）或 所有父节点都小于等于子节点（小顶堆）==

二叉树遍历说明

前序遍历： 先输出父节点，再遍历左子树和遍历右子树

中序遍历：先遍历左子树，再输出父节点，再遍历右子树

后序遍历：先遍历左子树，再遍历右子树，再输出父节点

==注意看 父节点的输出位置，决定了它是什么遍历==

顺序存储二叉树的概念

特点：

1. 顺序二叉树通常是完全二叉树
2. 第n个元素的左子节点为2*n + 1
3. 第n个元素的右子节点为2*n + 2
4. 第n个元素的父节点为(n - 1) / 2
5. 该树的非叶子节点个数为arr.length/2-1