存储结构详见详谈二叉树1

1. 遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树遍历操作的结果就是将非线性结构线性化。

2.遍历方法

二叉树的遍历方法主要有以下四种：

1.前序遍历:根结点–>左子树–>右子树

若二叉树为空，则空操作返回；否则：

1. 访问根节点；
2. 前序遍历根结点的左子树;
3. 前序遍历根结点的右子树;

例子：
前序遍历上图为：A B D G C E F

前序遍历——递归算法

2.中序遍历:左子树–>根结点–>右子树

若二叉树为空，则空操作返回；否则：

1. 中序遍历根结点的左子树;
2. 访问根结点
3. 中序遍历根结点的右子树;

中序遍历上图为D G B A E C F

中序遍历——递归算法

3.后序遍历:左子树–>右子树–>根结点

若二叉树为空，则空操作返回；否则：

1. 后序遍历根结点的左子树;
2. 后序遍历根结点的右子树;
3. 访问根结点

后序遍历上图为G D B E F C A

后序遍历——递归算法

3.层序遍历:

二叉树的层序遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，则按从左到右的顺序对结点逐个访问。

层序遍历上图为A B C D E F G

**层序遍历伪代码：**以队列的方式进行

1.队列Q初始化；
2.如果二叉树为空，将根指针入队；
3.循环直至队列Q为空

• 3.1 q=队列Q的队头元素出队；
• 3.2 访问结点q的数据域；
• 3.3若结点q存在左孩子，则将左孩子指针入队；
• 3.4若结点q存在右孩子，则将右孩子指针入队；

3.创建

如何用一种遍历序列生成二叉树?

为了建立一棵二叉树，将二叉树中每个结点的空值针引出一个虚结点,其值为一特定值如‘#’，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。

可以用前序遍历的方法建立二叉树，其原理也是用了递归的原理
设二叉树的结点均为一个一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：

首先输入根结点，若输入的是#字符，则表明该二叉树为空树，即root=null;否则输入的字符应该赋给root->data,之后依次递归建立它的左子树与右子树。