栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构与算法之二叉树的先序、中序以及后序遍历

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构与算法之二叉树的先序、中序以及后序遍历

什么是遍历
  1. 遍历:按照某种次序把所有结点 都访问一遍

  2. 层次遍历:基于树的层次特性确定的次序规则

    1. 先/中/后序遍历:基于树的递归特性确定的次序规则

二叉树的遍历

二叉树的递归特性:

  1. 要么就是个空二叉树
  2. 要么就是有“根节点+左子树+右子树”组成的二叉树
遍历方式
  1. 先序遍历:根左右(NLR)
  2. 中序遍历:左根右(LNR)
  3. 后序遍历:左右根(LRN)

下面是一些遍历方式例图

先序遍历

操作过程:

  1. 若二叉树,则什么都不做;

  2. 若二叉树非空:

    1. 访问根节点
    2. 先序遍历左子树
    3. 先序遍历右子树
void preOrder(BiTree biTree) {
    //递归结束
    if (biTree == NULL) {
        return;
    }
    printf("%dt", biTree->data);
    //左子树,因为子树和根都是一样的数据结构所以可以直接递归
    preOrder(biTree->lChild);
    //右子树,因为子树和根都是一样的数据结构所以可以直接递归
    preOrder(biTree->rChild);
}

流程展示(下面中序遍历和后序遍历类似)

中序遍历

操作过程:

  1. 若二叉树,则什么都不做;

  2. 若二叉树非空:

    1. 先序遍历左子树
    2. 访问根节点
    3. 先序遍历右子树
void midOrder(BiTree biTree) {
    //递归结束
    if (biTree == NULL) {
        return;
    }
    //左子树,因为子树和根都是一样的数据结构所以可以直接递归
    midOrder(biTree->lChild);
    //根节点data打印
    printf("%dt", biTree->data);
    //右子树,因为子树和根都是一样的数据结构所以可以直接递归
    midOrder(biTree->rChild);
}

后序遍历

操作过程:

  1. 若二叉树,则什么都不做;

  2. 若二叉树非空:

    1. 先序遍历左子树
    2. 先序遍历右子树
    3. 访问根节点
void postOrder(BiTree biTree) {
    //递归结束
    if (biTree == NULL) {
        return;
    }
    //左子树,因为子树和根都是一样的数据结构所以可以直接递归
    postOrder(biTree->lChild);
    //右子树,因为子树和根都是一样的数据结构所以可以直接递归
    postOrder(biTree->rChild);
    //根节点data打印
    printf("%dt", biTree->data);
}

总结

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/935970.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号