二叉树遍历的概念

（1）遍历

二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。

（2）遍历的三个子问题及三种访问方式

访问根结点，遍历左子树、遍历右子树先左后右，即先遍历左子树，再遍历右子树，并以根结点访问的次序划分先序、中序、后序先序遍历：先访问根结点，然后遍历左子树，再遍历右子树中序遍历：先遍历左子树，然后访问根结点，最后遍历右子树后序遍历：先遍历左子树，然后遍历右子树，最后访问根结点先序遍历算法

void Preorder(struct BTreeNode* BT)

	{	if(BT!=NULL) {	printf("%c",BT->data); /*访问根结点*/	Preorder(BT->left); /*先序遍历左子树*/	Preorder(BT->right); /*先序遍历右子树*/	}	}

	void Inorder(struct BTreeNode* BT)	{	if(BT!=NULL) {	Inorder(BT->left); /*中序遍历左子树*/	printf("%c",BT->data); /*访问根结点*/	Inorder(BT->right); /*中序遍历右子树*/	}	}

	void Postorder(struct BTreeNode* BT)	{	if(BT!=NULL) {	Postorder(BT->left); /*后序遍历左子树*/	Postorder(BT->right); /*后序遍历右子树*/	printf("%c ",BT->data); /*访问根结点*/	}	}

在这三种遍历算法中，访问根结点进行何种操作可视具体应用情况而定，这里暂以打印根结点的值代之。当然若结点的值为用户定义的记录类型，则还必须依次输出结点值对象中的每个域的值。

递归遍历算法的执行过程

下面以中序递归遍历算法为例，结合图6-9的二叉树，分析其执行过程。

二叉树递归遍历举例

当从其他函数调用（此次称为第0次递归调用）中序遍历算法时，需要以指向树根A结点的指针Ap作为实参，把它传递给算法中的值参BT，调用递归算法时系统自动建立的工作栈应包括BT域和返回地址r域，假定进行第0次递归调用后的返回地址为r 0 ，中序遍历左子树后的返回地址（即printf语句的开始地址）为r 1 ，中序遍历右子树后的返回地址（即算法结束的地址）为r 2 ，并假定指向每个结点的指针用该结点的值后缀小写字母p表示，如指向B结点的指针就用Bp表示，则每次进行递归调用时工作栈中的数据变化情况如图6-10所示。

二叉树中序递归遍历时工作栈的变化情况

由上述分析中序递归遍历算法的执行过程可知，结点的访问序列为：

C，B，D，A，E，G，F

类似地，若按照先序递归遍历算法和后序递归遍历算法遍历图6-9所示的二叉树，则结点的访问序列分别为：

A，B，C，D，E，F，G和C，D，B，G，F，E，A

递归遍历算法的时空复杂度分析

在二叉树的三种递归遍历算法中，都访问到了每个结点的每一个域，并且每个结点的每一个域仅被访问一次。所以三种递归遍历算法的时间复杂度均为O(n)，n表示二叉树中结点的个数。另外在执行每个递归遍历算法时，系统都要使用一个栈，栈的最大深度等于二叉树的深度加1，而二叉树的深度视其具体形态决定，若二叉树为理想二叉树或接近理想二叉树，则二叉树的深度大致为log2n，所以其空间复杂度为O(log2n)，若二叉树退化为一棵单支树（即最差的情况），则空间复杂度为O(n)，n同样为二叉树中的结点数。