做交友网站网站外包
二叉树是一种特殊的树型结构，它的特点是:
- 每个结点至多只有2棵子树(即二叉树中不存在度大于2的结点)
- 并且二叉树的子树有左右之分，其次序不能任意颠倒，因此是一颗有序树
以A结点为例，左边的B是它的左孩子，右边的C是它的右孩子，以左孩子为根的这棵树称为左指树，以右孩子为根的这棵树称为右子树，把BDEH单独拉出来看就是一个二叉树，B是它的根结点，D H是左子树，E是右子树，同理，C这个右子树也是把CFGI单独拿出来看，C是他的根结点，FI是左子树，G是右子树，因此二叉树可以抽象为右边这个等式
- 二叉树也是通过递归定义的结构
满二叉树:
在一棵二叉树中，所有非叶结点都存在左右孩子，所有叶子结点都在同一层，那么这棵树就是满二叉树
性质:
- 高度为h的满二叉树，结点个数为2h-1
- 结点个数为n的满二叉树，树高h=log以2为底n+1
- 如果将满二叉树按照层序遍历的过程编号:从根节点开始，由1开始编号:
- 结点i左孩子的编号为2xi
- 结点i右孩子的编号为2xi+1结点i双亲的编号为i/2
- 这个性质可以帮助我们存储二叉树
完全二叉树
如果一棵树所有结点和同样深度的满二叉树，按照层序遍历编号的位置-一对应，则这棵二叉树为完全二叉树。（这个定义很抽象，我们可以记住相当于在满二叉树的基础上，从后往前依次删掉一些结点就变成了完全二叉树 ）
