遍历二叉树

二叉树是由3个基本单元组成：根结点、左子树、右子树

1.先序遍历（先打印结点数据）

（1）打印结点（根结点和其他结点）的数据内容
（2）先序遍历左子树
（3）先序遍历右子树

void PreOrderTraverse(BiTree T){
	if(T){	//当前结点的数据域非空
		cout << T->data;	//打印结点（根结点和其他结点）数据
		PreOrderTraverse(T->lchild);	//递归前序遍历左子树，T->lchild 得到当前的结点左孩子结点
		PreOrderTraverse(T->rchild);	//递归前序遍历右子树，T->lchild 得到当前的结点右孩子结点
	}
}

根据上图二叉树给出程序运行过程：
(点击图片即可放大，该图片原版PDF见本人博客资源)

故先序遍历序列为：ABDGHCEIF

2.中序遍历（中间打印结点数据）

（1）中序遍历左子树
（2）打印结点（根结点和其他结点）的数据内容
（3）中序遍历右子树

void InOrderTraverse(BiTree T){
	if(T){	//当前结点的数据域非空
		InOrderTraverse(T->lchild);	//递归中序遍历左子树，T->lchild 得到当前的结点左孩子结点
		cout << T->data;	//打印结点（根结点和其他结点）数据
		InOrderTraverse(T->rchild);	//递归中序遍历右子树，T->lchild 得到当前的结点右孩子结点
	}
}

根据上图二叉树给出程序运行过程：
(点击图片即可放大，该图片原版PDF见本人博客资源)

故中序遍历序列为：GDHBAEICF

3.后序遍历（后打印结点数据）

（1）后序遍历左子树
（2）后序遍历右子树
（3）打印结点（根结点和其他结点）的数据内容

void PostOrderTraverse(BiTree T){
	if(T){	//当前结点的数据域非空
		PostOrderTraverse(T->lchild);	//递归后序遍历左子树，T->lchild 得到当前的结点左孩子结点
		PostOrderTraverse(T->rchild);	//递归后序遍历右子树，T->lchild 得到当前的结点右孩子结点
		cout << T->data;	//打印结点（根结点和其他结点）数据
	}
}