二叉树的递归遍历操作

二叉树的遍历是指按某种次序依次访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

一、递归先序遍历的操作

如果二叉树为空，什么也不做。否则：

1. 访问根结点；
2. 先序遍历左子树；
3. 先序遍历右子树。

void PreOrder(BiTree T){

if(T!=NULL){

printf(“%c”,T->data) //访问根结点

PreOrder(T->lchild); //递归遍历左子树

PreOrder(T->rchild); //递归遍历右子树

}}

遍历序列： A B D G C E F

二、递归中序遍历的操作

如果二叉树为空，什么也不做。否则：

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

void InOrder(BiTree T){

if(T!=NULL){

InOrder(T->lchild); //递归遍历左子树

printf(“%c”,T->data)； //访问根结点

InOrder(T->rchild); //递归遍历右子树

}}

遍历序列:D G B A E C F

三、递归后序遍历的操作

如果二叉树为空，什么也不做。否则：

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

void PostOrder(BiTree T){

if(T!=NULL){

PostOrder(T->lchild); //递归遍历左子树

PostOrder(T->rchild); //递归遍历右子树

printf(“%c”,T->data)； //访问根结点

}}

遍历序列:G D B E F C A