数据结构-二叉树

二叉树是一种特殊的树，描述的是一种非线性数据结构。特殊的地方在于从一个节点出发，最多只能有两个孩子节点，而普通的树是没有限制的。树的构成满足以下几个条件，

1. 有且仅有一个特定的称为根的节点。
2. 除根节点外都可称为子节点，子节点可分为若干个互不相交的有限集合，每个集合又是一棵树。
   二叉树示例.jpg 这是我找的一张二叉树示例图，根据树的表述，我们还能知道，树的高度（深度）就是树的最大层级数，图例中就是 3.

二叉树的表示

通常，用链表表示会更合适点也更容易理解，当然也可以用数组表示。当用数组表示时，需要记住以下公式，

//当根节点从 0 开始时
//left 表示左节点的下标，p 表示父节点下标
left = 2 * p + 1
//right 表示右节点的下标，p 表示父节点下标
right = 2 * p + 2
//如果根节点从 1 开始，那么有点不同
left = 2 * p
right = 2 * p + 1
//根据上述公式也能推导出 p 的下标

二叉树常见类型

满二叉树，满足1. 所有非叶子节点都有左右孩子节点，2.所有叶子节点都在同一层级上。

完全二叉树，对一棵树按层级顺序编号，如果与同样深度的满二叉树的相应节点位置都相同，则就是完全二叉树。这么来看其实满二叉树就是特殊的完全二叉树。

二叉查找树（二叉排序树），满足1.左子树上所有节点值均小于根节点值，2.右子树上所有节点值均大于根节点值，3.左右子树也都是二叉查找树。

二叉树的遍历

二叉树最常见也最基础的操作就是遍历了，分为深度优先遍历和广度优先遍历，其中深度优先遍历又分为前序，中序，后序遍历。