二叉树

二叉树这种数据结构每次听到都会觉得很熟悉，但是深入研究又有些懵懂，总觉得就是那么回事。还是大学课本里面的那些知识，不知道当初为什么会觉得数据结构会如此复杂，我觉得有很大一部分原因，可能是编程功底较差，就对导致这些底层数据结构和算法产生一种排斥感。现在想想数据结构无非就是这么几种，数组，链表，栈，队列，树，图等等；如此庞大的计算机学科中，其实数据结构就这么区区几种。

概念

二叉树的概念其实很清晰，就是从一个节点不停向下进行分支，每次分支最多只能有两个节点。所以就出现的根节点，叶子节点，兄弟节点，父节点的概念。

节点高度 = 节点到叶子节点的最长路径。

节点深度 = 根节点到这个节点所经历的边的个数。

节点层数 = 节点深度 + 1。

树的高度 = 根节点的高度。

二叉树中比较常用而又特殊的二叉树有满二叉树，完全二叉树。

满二叉树就是叶子节点全部都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。

完全二叉树就是叶子节点在最底下两层，最后一层的叶子节点全部靠左，除了最后一层，其它层的叶子节点要达到最大。

所以满二叉树就是一种比较特别的完全二叉树

二叉树存储

二叉树的结构包含 数据，左指针，右指针。所以比较适合链式存储法。根节点相当于链表头，左指针指向左孩子，右指针指向右孩子。

完全二叉树的结构适合数组的顺序存储。父节点 i = 层数，子节点 分别是 2*i 和 2*i+1，这里i就是数组的下标，除了第一个下标0没有存储，其它都是连续的。如果对于非完全二叉树来说就会浪费数组中间部分空间。

二叉树遍历

主要有三种遍历方式，前序遍历，中序遍历，后序遍历。

前序遍历：先父节点，再左孩子，最后右孩子。

中序遍历：先左孩子，再父节点，最后右孩子。

后序遍历：先左孩子，再右孩子，最后父节点。