数据结构 - 树的遍历

一、二叉树的遍历

对于二叉树，常用的遍历方式包括：先序遍历、中序遍历、后序遍历和层次遍历 。

1、先序遍历（PreOrder）

先序遍历的操作过程如下：

若二叉树为空，则什么也不做；否则，

（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

void PreOrder(BiTree T){   //先序遍历if(T!=NULL){visit(T);              //访问根结点PreOrder(T->lchild);   //递归遍历左子树PreOrder(T->rchild);   //递归遍历右子树}
}

2、中序遍历（InOrder）

中序遍历（InOrder）的操作过程如下：

若二叉树为空，则什么也不做；否则，

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

void InOrder(BiTree T){    //中序遍历if(T!=NULL){InOrder(T->lchild);   //递归遍历左子树visit(T);               //访问根结点InOrder(T->rchild);   //递归遍历右子树}
}

3、后序遍历（PostOrder）

后序遍历（PostOrder）的操作过程如下：

若二叉树为空，则什么也不做；否则，

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

 

void PostOrder(BiTree T){    //后序遍历伪代码if(T!=NULL){PostOrder(T->lchild);   //递归遍历PostOrder(T->rchild);   //递归遍历右子树visit(T);              //访问根结点}
}

4、层次遍历（LevelOrder）

层次遍历（LevelOrder）的操作过程如下：

（1）首先借助一个队列，先将二叉树根结点入队，然后出队，访问出队结点；

（2） 若它有左子树，则将左子树根结点入队；

（3） 若它有右子树，则将右子树根结点入队；

（4） 然后出队，访问出队结点。如此反复，直到队列为空[1,5]。

void LevelOrder(BiTree T){    //层次遍历InitQueue(Q);               //初始化辅助队列BiTree P;EnQueue(Q,T);              //将根结点入队while(!IsEmpty(Q)){       //队列不空则循环DeQueue(Q,P);            //队头结点出队visit(p);                 //访问出队结点if(p->lchild!=NULL)EnQueue(Q,p->lchild); //左子树不空，则左子树根结点入队if(p->rchild!=NULL)EnQueue(Q,p->rchild); //右子树不空，则右子树根结点入队}
}

5、遍历示例

存在如下图所示二叉树：

二叉树示例

其先序遍历为ABDECF（根-左-右）

其中序遍历为DBEAFC（左-根-右）（仅二叉树有中序遍历）

其后序遍历为DEBFCA（左-右-根）

其层次遍历为ABCDEF

二、一般树的遍历

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有三种方式：

1.先根遍历：若树非空，先访问树的根结点，然后依次先根遍历根结点的每棵子树。其遍历序列与其转换为二叉树的先序序列相同。

2.后根遍历：若树非空，先依次后根遍历根结点的每棵子树，然后访问树的根结点。其遍历序列与其转换为二叉树的后序序列相同。

3.层次遍历：与二叉树的层次遍历思想基本相同，即按层序依次访问各结点。

例如：如下图所示：

其先根遍历为ABEFGCDHI

其后根遍历为EFGBCHIDA

其层次遍历为ABCDEFGHI