二叉树

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

特点是与每个结点关联的子结点至多有两个（可为0，1，2），即一个结点至多有两棵子树。
二叉树的两棵子树分别称作它的左子树和右子树，即：子树有左右之分（因此二叉树与树有不同结构，不是树的特殊情况）。

完全二叉树

对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
也就是说除了叶子层，其他层都堆满了，并且叶子层具有的节点都是从左填充到右的。

完全二叉树

完全二叉树最重要的性质：如果n个节点的完全二叉树的节点按照层次并按从左到右的顺序从0开始编号，对于任一个节点都有：

• 序号为0的节点是根节点；
• 对于i>0，其父节点的编号为(i-1)/2。
• 若2·i+1<n，其左子节点的序号为2·i+1，否则没有左子节点。
• 若2·i+2<n，其右子节点的序号为2·i+2，否则没有右子节点。

满二叉树

树中每个分支结点（非叶结点）都有两棵非空子树，除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
也就是说叶子节点也堆满了节点的树。

满二叉树

平衡二叉树

平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注意两点：空树也是平衡二叉树；绝对值不超过1。

二茶树的高度和深度

二叉树的深度：从根数到叶子，层数即深度。只有一个根节点的深度为1。深度是从根节点数到它的叶节点。
二叉树的高度：从叶子数到根，层数即高度。只有一个根节点的高度为1。高度是从叶节点数到它的根节点。
所以往往深度 == 高度

二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。

示例图

某节点的深度是指从根节点到该节点的最长简单路径边的条数，
而高度是指从该节点到叶子节点的最长简单路径边的条数。

B和C节点深度都为1，因为从根节点到到该节点的边数为1，自顶向下累加；B的高度为2，而C的高度为1，自底向上累加。

当然树的深度是3高度也是3。树的高度和深度是相等的。

二叉树的遍历

image

每棵二叉树都有唯一的根节点，可以将其看做这棵二叉树的唯一标识，是基于树结构的处理入口。

深度优先遍历：按照一条路径尽可能的向前探索， 直至检查完一个叶节点。
遍历左子树、遍历右子树和访问根节点。
根据这三项工作的不同执行顺序，就可以得到三种常见遍历顺序（因为要先处理左子树，所以不是6种而是3种）

1.先根序遍历：先访问根节点，而后以同样的方式顺序遍历左子树和右子树。
结果：A -> B -> D -> H -> E -> I -> C -> F -> J -> K ->G

2.后根序遍历：先以同样的方式遍历左右子树，最后遍历根节点。
结果：H -> D -> I -> E -> B -> J -> K -> F -> G -> C -> A

3.中根序遍历：先以同样的方式遍历左子树，然后访问根节点，最后以同样的方式遍历右子树。
结果： D -> H ->B -> E -> I -> A -> J -> F -> K -> C -> G

根据给定的二叉树唯一确定它的先根序列、后根序列和中根序列，但是给定任意一棵树的任意一种遍历序列都无法唯一确定相应的二叉树。

宽度优先遍历：在所有路径上齐头并进。宽度优先遍历是按照路径长度由近到远访问节点。也就是说按照二叉树的层数逐层访问树中的节点。