二叉树的遍历

一、二叉树的遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为一下四种：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

1.前序遍历：

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

二叉树的遍历.png

遍历的顺序为：ABDHIEJCFKG

2.中序遍历：

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

二叉树的遍历.png

遍历的顺序为：HDIBEJAFKCG

3.后序遍历：

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

二叉树的遍历.png

遍历的顺序为：HIDJEBKFGCA

4.层序遍历：

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

二叉树的遍历.png

遍历的顺序为：ABCDEFGHIJK

二、二叉树建立及遍历

建议二叉树并输出每个字符所在的层数。如图要求输出：
A在第一层
B、C在第二层
D、E在第三层

建立二叉树.png

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
CreateBiTree(BiTree *T)
{
    char c;

    scanf("%c", &c);
    if( ' ' == c )
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

// 访问二叉树结点的具体操作
visit(char c, int level)
{
    printf("%c 位于第 %d 层\n", c, level);
}

// 前序遍历二叉树
PreOrderTraverse(BiTree T, int level)
{
    if( T )
    {
        visit(T->data, level);
        PreOrderTraverse(T->lchild, level+1);
        PreOrderTraverse(T->rchild, level+1);
    }
}

int main()
{
    int level = 1;
    BiTree T = NULL;

    CreateBiTree(&T);
    PreOrderTraverse(T, level);

    return 0;
}

程序运行后操作示意：

输入.png