考研笔记-计算机之数据结构:层次结构-树(二叉树遍历)

——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。

二叉树的遍历：深度优先遍历，包括先序（根）遍历、中序（根）遍历和后序（根）遍历（先序、中序和后序是根相对于左右子树而言，且先左后右。只有二叉树才同时有先序、中序和后序遍历，一般的树无中序遍历）；广度优先遍历，包括层次遍历（所有的树都可进行层次遍历）。中序遍历的过程实质上是一个结点（根）进栈和出栈的过程。

二叉树深度优先遍历的递归实现

只有深度优先遍历可用递归实现，广度优先遍历无法用递归实现。在先、中和后序遍历中，均将当前结点作为根结点看待，以根结点为中心实现递归。

先序遍历递归算法

若二叉树非空，则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。

voidPreOrderTraverse(BiTree r, void (*visit)(BiTree)){ if (r != NULL) {  visit(r);  PreOrderTraverse(r->lchild, visit);  PreOrderTraverse(r->rchild, visit); }}

中序遍历递归算法

若二叉树非空，则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。

voidMidOrderTraverse(BiTree r, void (*visit)(BiTree)){ if (r != NULL) {  MidOrderTraverse(r->lchild, visit);  visit(r);  MidOrderTraverse(r->rchild, visit); }}

后序遍历递归算法

若二叉树非空，则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。

voidPostOrderTraverse(BiTree r, void (*visit)(BiTree)){ if (r != NULL) {  PostOrderTraverse(r->lchild, visit);  PostOrderTraverse(r->rchild, visit);  visit(r); }}

对于深度优先遍历的递归实现而言，不管按哪种次序遍历，对含n个结点的二叉树，其时间复杂度均为，所需辅助空间为遍历过程中栈的最大容量，即树的深度（因为栈中存放的是根且这些根从栈底到栈顶，任意相邻的两个根均为父子（非左即右）关系），最坏情况下为n，故空间复杂度也为。

二叉树遍历的非递归实现

先序遍历序列和中序遍历序列或后序遍历序列和中序遍历序列均可唯一确定一棵二叉树（依据先序或后序序列确定二叉树的根和各任意子树的根；依据中序序列划分左右子树。具体过程为：因先序遍历是先访问根结点D，其次遍历左子树L，最后遍历右子树R，则在先序序列中，第一个结点必是根D；因中序遍历是先遍历左子树L，然后访问根D，最后遍历右子树R，则根结点D将中序序列分割成两部分，在D之前是左子树结点的中序序列，在D之后是右子树结点的中序序列，反过来，根据左子树的中序序列中结点个数，又可将前序序列除根以外分成左子树的前序序列和右子树的前序序列两部分，以此类推，便可递归得到整棵二叉树。）。

用二叉树表示表达式的递归定义如下：若表达式为数或简单变量，则相应的二叉树中仅有一个根结点，其数据域存放该表达式信息；若表达式=<第一操作数><运算符><第二操作数>，则相应二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空）。操作数本身又为表达式。

对算数表达式的二叉树进行先序遍历、中序遍历和后序遍历，可分别得到表达式的前缀表示（波兰式）、中缀表示（与算数表达式的区别是仅不含括号而已）和后缀表示（逆波兰式）。