数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历（顺序存储结构、链表存储结构、先序中序后序递归遍历）

设想一下二叉树要用什么样的方式来存储，一种是用数组，一种是用链表。

顺序存储结构

用数组，也就是用顺序存储结构，比较合适的就是用于完全二叉树：

按从上至下，从左到右顺序存储n个节点的完全二叉树。 其中的节点父子关系会满足：

• 非根节点（序号 > 1）的父节点的序号是[i / 2]
• 节点（序号为i）的左孩子节点的序号是[2i],（若2i <= n，否则没有左孩子）
• 节点（序号为i）的右孩子节点的序号是[2i+1]，（若2i+1 <= n，否则没有右孩子）

一般的二叉树也可以采用这种结构，但是会造成空间浪费。

这样简单的一个二叉树要浪费两个空间，再复杂一些的二叉树浪费的空间就会多得多了。 总结：用数组来表示是可行的，但如果一般的二叉树跟对应的完全二叉树相比，缺的节点很多的话，会造成一定的空间浪费。

链表存储结构

链表存储就是用之前的儿子-兄弟表示法，定义两个指针域就可以表示二叉树了。

typedef int ElementType;
typedef struct TreeNode
{
  ElementType data;
  struct TreeNode* Left;
  struct TreeNode* Right;
}TreeNode;

二叉树的递归遍历

先序递归遍历

遍历过程为：

1. 访问根节点
2. 先序遍历其左子树
3. 先序遍历其右子树

先序遍历的序列为：A B D F E C G H I

中序递归遍历

遍历过程为：

1. 中序遍历其左子树
2. 访问根节点
3. 中序遍历其右子树

可以脑子里过一遍，下面再公布正确的中序遍历的序列。

中序遍历的序列为：D B E F A G H C I

后序递归遍历

遍历过程为：

1. 后序遍历其左子树
2. 后序遍历其右子树
3. 访问根节点

同样先自己写出后序遍历的序列，对照后面的正确序列。

后序遍历的序列为：D E F B H G I C A

在先序、中序和后序的遍历过程中，它们经过节点的路线其实是一样的（路线会在之后的非递归遍历中提到）

都是按这个顺序，只是访问各节点的时机不同。

下面就看看各方式遍历下，访问节点的时机分别是怎样的。

首先要清楚，沿着路线，对每个节点都会访问三次：

所谓先序、中序和后序，就是说：先序是在第一次经过节点时就将节点访问、中序是在第二次经过节点时将节点访问、而后序就是在第三次经过节点时将节点访问。

故有了：

先序遍历路线图

中序遍历路线图

后序遍历路线图

end