遍历二叉树

二叉树是一种非线性的数据结构。所谓的遍历二叉树就是按某种顺序访问二叉树中的每个节点，要求每个节点被访问一次且仅一次。

遍历操作实际上是将非线性结构线性化过程，其结果为线性序列。

二叉树的操作

（1）先序遍历---结束的条件是二叉树是否为空 TLR

先访问根节点；

再先序访问左子树；

再先序访问右子树。

（2）中序遍历---结束的条件是二叉树是否为空  LTR

先中序遍历左子树；

再访问根节点；

再中序遍历右子树。

（3）后序遍历---结束的条件是二叉树是否为空  LRT

先后序遍历左子树；

再后序遍历右子树；

再后序访问根节点。

（4）已知两种遍历序列求原始二叉树

1.    如果已知先序和中序、中序和后序，可以推出原始二叉树的。

2.    如果已知先序和后序，是无法求出原始二叉树的。

步骤：

先找到根节点；

在根据根节点，确定左子树和右子树。

示例一：

先序：ABCDEFGH

中序：BDCEAFHG

求后序？

后序：DECBHGFA

示例二：

先序：ABDGHCEFI

中序：GDHBAECIF

求后序?

后序：GHDBEIFCA

示例三：

中序：BDCEAFHG

后序:  DECBHGFA

先序：ABCDEFGH

数据结构学习笔记（四）---遍历二叉树