数据结构34:二叉树前序遍历、中序遍历和后序遍历

链式存储结构存储的二叉树,对树中结点进行逐个遍历时,由于是非线性结构,需要找到一种合适的方式遍历树中的每个结点。递归思想遍历二叉树之前讲过,树是由根结点和子树部分构建的,对于每一棵树来说,都可以分为 3 部分:左子树、根结点和右子树。所以,可以采用递归的思想依次遍历每个结点。

根据访问结点时机的不同,分为三种遍历方式:
  • 先访问根结点,再遍历左右子树,称为“先序遍历”;
  • 遍历左子树,之后访问根结点,然后遍历右子树,称为“中序遍历”;
  • 遍历完左右子树,再访问根结点,称为“后序遍历”。

  • 图1 二叉树
    三种方式唯一的不同就是访问结点时机的不同,给出一个二叉树,首先需要搞清楚三种遍历方式下访问结点的顺序。
    图2 二叉树遍历示意图
    图2 中,箭头线条的走势为遍历结点的过程:

    先序遍历是只要线条走到该结点的左方位置时,就操作该结点。所以操作结点的顺序为:1 2 4 5 3 6 7
    中序遍历是当线条越过结点的左子树,到达该结点的正下方时,才操作该结点。所以操作结点的顺序为:4 2 5 1 6 3 7
    后序遍历是线条完全走过结点的左右子树,到达该结点的右方范围时,就开始操作该结点。所以操作结点的顺序为:4 5 2 6 7 3 1三种遍历方式的完整代码实现
    #include <stdio.h>
    #include <string.h>
    #define TElemType int
    //构造结点的结构体
    typedef struct BiTNode
    {   TElemType data;  
    //数据域   struct BiTNode *lchild, *rchild;  //左右孩子指针 }BiTNode, *BiTree;
    //初始化树的函数 void CreateBiTree(BiTree *T)
    {   
    *T = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->data = 1;   (*T)->lchild = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->rchild = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->lchild->data = 2;   (*T)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->lchild->rchild->data = 5;   (*T)->lchild->rchild->lchild = NULL;   (*T)->lchild->rchild->rchild = NULL;   (*T)->rchild->data = 3;   (*T)->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->rchild->lchild->data = 6;   (*T)->rchild->lchild->lchild = NULL;   (*T)->rchild->lchild->rchild = NULL;   (*T)->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));   (*T)->rchild->rchild->data = 7;   (*T)->rchild->rchild->lchild = NULL;   (*T)->rchild->rchild->rchild = NULL;   (*T)->lchild->lchild->data = 4;   (*T)->lchild->lchild->lchild = NULL;   (*T)->lchild->lchild->rchild = NULL; }
    //模拟操作结点元素的函数,输出结点本身的数值 void displayElem(BiTNode* elem)
    {   printf(
    "%d ", elem->data); }
    //先序遍历 void PreOrderTraverse(BiTree T)
    {   
    if (T)
      {     displayElem(T);
    //调用操作结点数据的函数方法     PreOrderTraverse(T->lchild);//访问该结点的左孩子     PreOrderTraverse(T->rchild);//访问该结点的右孩子   }   //如果结点为空,返回上一层   return; }
    //中序遍历 void INOrderTraverse(BiTree T)
    {   
    if (T)
      {     INOrderTraverse(T
    ->lchild);//遍历左孩子     displayElem(T);//调用操作结点数据的函数方法     INOrderTraverse(T->rchild);//遍历右孩子   }   //如果结点为空,返回上一层
      return; }
    //后序遍历 void PostOrderTraverse(BiTree T)
    {   
    if (T)
      {     PostOrderTraverse(T
    ->lchild);  //遍历左孩子     PostOrderTraverse(T->rchild);  //遍历右孩子     displayElem(T);  //调用操作结点数据的函数方法   }
      
    //如果结点为空,返回上一层   return; }
    int main()
    {   BiTree Tree;   CreateBiTree(
    &Tree);   printf("前序遍历: n");   PreOrderTraverse(Tree);   printf("n中序遍历算法: n");   INOrderTraverse(Tree);   printf("n后序遍历: n");   PostOrderTraverse(Tree); }

    运行结果: 前序遍历:
    1 2 4 5 3 6 7 中序遍历算法: 4 2 5 1 6 3 7 后序遍历: 4 5 2 6 7 3 1

     

    总结 由于二叉树就是由根结点和左右子树构成的,所以很容易想到使用递归的思想。而递归算法的低层实现实际上使用的是栈的数据结构,所以二叉树的先序、中序和后序遍历同样可以使用非递归的算法实现。

    非递归算法的具体实现可以查看下一节的内容。

    相关内容推荐