C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历

这篇具有很好参考价值的文章主要介绍了C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、先序遍历原理

       先序遍历就是:根、左、右,也就是先遍历根结点再遍历左结点最后再遍历右结点,注意:如果遍历到的结点不是叶子结点的话需要对该结点进行拆分,比如这棵二叉树:

C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历

先遍历A,然后是B,然后再是C,但是由于B并不是叶子结点,他本身又是一棵子树的根结点,所以B可以拆分成B、D、E(根、左、右),同理因为C本身又是一棵子树的根结点根据先序遍历的原则C也可以拆分为C、F(根、左、右),然后再组合在一起便是A、B、D、E、C、F,此时D还不是叶子结点,同理再将D进行拆分为D、G(根左右),最后得到A、B、D、G、E、C、F。如下图所示

C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历

 二、代码实现

通过上面的分析我们可以通过递归来实现树的遍历

1、先序遍历

void preOrder(BiTree T){
    if(T != NULL){
        visit(T);//先访问根节点
        preOrder(T->lchild);//再访问左结点
        preOrder(T->rchild);//最后访问右结点
    }
    return;
}

2、中序遍历

void midOrder(BiTree T){
    if(T != NULL){
        midOrder(T->lchild);//先访问左结点
        visit(T);//再访问根结点
        midOrder(T->rchild);//最后访问右结点
    }
    return;
}

3、后序遍历

void lastOrder(BiTree T){
    if(T != NULL){
        lastOrder(T->lchild);//先访问左结点
        lastOrder(T->rchild);//再访问右结点
        visit(T);//最后访问根节点
    }
    return;
}

     其中visit函数就是打印访问到的结点,xxxOrder函数就是一个递归函数,如果T已经是叶子结点了,那么就会返回,如果T是分支结点,也就是说还有左孩子或右孩子的话那么就访问对应的左孩子或右孩子,直到为叶子结点再返回,可以理解为上面讲的拆分(剥开)的原理,其实也就是递归的原理。

4、完整代码实现

#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
//初始化根节点
BiTree init_Tree(BiTree T){
      //创建根节点,让指针T指向根节点
      T = (BiTree)malloc(sizeof(struct BiTNode));
      T->data = 'A';
      T->lchild = NULL;
      T->rchild = NULL;
      return T;
}
BiTree insert_Tree_left(BiTree Tree,char ch){
     BiTree p = (BiTree) malloc(sizeof(struct BiTNode));
     p->lchild = NULL;
     p->rchild = NULL;
     p->data = ch;
     Tree->lchild = p;
     return p;
}
BiTree insert_Tree_right(BiTree Tree,char ch){
    BiTree p = (BiTree) malloc(sizeof(struct BiTNode));
    p->lchild = NULL;
    p->rchild = NULL;
    p->data = ch;
    Tree->rchild = p;
    return p;
}
//访问对应的结点的值
void visit(BiTree tree){
    printf("%c ",tree->data);
    return;
}

//树的先序遍历
void preOrder(BiTree T){
    if(T != NULL){
        visit(T);//先访问根节点
        preOrder(T->lchild);//再访问左结点
        preOrder(T->rchild);//最后访问右结点
    }
    return;
}
//中序遍历
void midOrder(BiTree T){
    if(T != NULL){
        midOrder(T->lchild);//先访问左结点
        visit(T);//再访问根结点
        midOrder(T->rchild);//最后访问右结点
    }
    return;
}
void lastOrder(BiTree T){
    if(T != NULL){
        lastOrder(T->lchild);//先访问左结点
        lastOrder(T->rchild);//再访问右结点
        visit(T);//最后访问根节点
    }
    return;
}
int main() {
    BiTree T = NULL;
    T = init_Tree(T);
    BiTree B = insert_Tree_left(T,'B');
    BiTree C = insert_Tree_right(T,'C');

    BiTree D = insert_Tree_left(B,'D');
    BiTree E = insert_Tree_right(B,'E');

    insert_Tree_right(D,'G');
    insert_Tree_left(C,'F');
    printf("先序遍历:");
    preOrder(T);
    printf("\n");
    printf("中序遍历:");
    midOrder(T);
    printf("\n");
    printf("后序遍历:");
    lastOrder(T);
    return 0;
}

5、运行结果

C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历

 文章来源地址https://www.toymoban.com/news/detail-469765.html

 

到了这里,关于C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——二叉树的先中后序遍历

    ——本节内容为Bilibili王道考研《数据结构》P43~P45视频内容笔记。 目录 一、二叉树的先中后序遍历 1.先中后序遍历 2.举例  3.先中后序遍历和前中后缀的关系 4.代码实现 5.求遍历序列 6.应用:求树的深度 二、二叉树的层次遍历 1.层次遍历 2.算法思想: 3.算法演示: 4.代码实

    2024年02月12日
    浏览(39)
  • 【数据结构】二叉树的创建和遍历(先序、中序、后序)

    最近一段时间学习了数据结构中二叉树的基本操作,包括二叉树的结构、二叉树的创建、递归先序中序后序遍历、非递归遍历等,想着把二叉树的相关知识和自己的见解放到网上来让网友看看是否正确,想和网友一起共同交流。 先了解一下二叉树的三个基本性质: 性质1:在

    2024年02月04日
    浏览(45)
  • 【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)

    一个二叉树是一个有穷的结点集合。 它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成的。 二叉树可具有以下5种形态。 一个二叉树第i层的最大结点数为 2 i − 1 2^{i-1} 2 i − 1 , i ≥ 1 i geq 1 i ≥ 1 每层最大结点可以对应完美二叉树(满二叉树),其所有分支结

    2024年02月20日
    浏览(45)
  • 二叉树的遍历(先序遍历,中序遍历,后序遍历)递归与非递归算法

    先序遍历:先遍历一颗树的根节点,后遍历左子树,最后遍历右子树     先序遍历序列: 1 - 2 - 4 - 5 - 3 - 6 - 7 分解子问题方法 思路:将一颗二叉树看做两个部分,一个部分是左路节点,另一个部分是左路节点的右子树,先将二叉树的左路节点全部入栈,再依次出栈,出栈的

    2024年02月14日
    浏览(40)
  • 二叉树的编程与实现(C语言)

    一 、目的 : 掌握指针变量、动态变量的含义; 掌握二叉树的结构特征,以及各种存储结构的特点及适用范围; 掌握指针类型描述、访问和处理二叉树的运算; 二 、环境: operating system version:Win11 CPU instruction set:  x64 Integrated Development Environment:Viusal Studio 2022 三 、内容:

    2024年02月05日
    浏览(38)
  • 二叉树的实现(C语言数据结构)

    目录 一、以下是我们需要实现的功能 二、以下是我们具体功能的实现 1.创建新的结点 2.通过数组生成二叉树  3.先序遍历 4.中序遍历 5.后序遍历   6.层序遍历 7.计算二叉树的结点个数 8.查找指定值为x的结点 9.查找第K层的结点个数 10.统计二叉树叶子结点的个数 11.判断是否为

    2024年02月04日
    浏览(39)
  • 数据结构-二叉树的代码实现(详解)

    内容:二叉树的前、中,后序遍历,层序遍历,二叉树节点个数,叶子节点个数,二叉树高度,第k层节点的个数,查找某个节点,二叉树销毁,判断是否为完全二叉树 目录  前序遍历: 中序遍历: 后序遍历: 层次遍历:需要借助队列  二叉树节点个数:  二叉树叶子节点

    2024年02月03日
    浏览(42)
  • 二叉树的链式结构 - 遍历 - C语言递归实现

    前序、中序以及后序遍历         二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次 。 按照规则,二叉树的遍历有: 前序/中序/后序 的递归结构遍历 : 1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结

    2024年02月15日
    浏览(33)
  • C语言数据结构初阶(10)----二叉树的实现

    · CSDN的uu们,大家好。这里是C语言数据结构的第十讲。 · 目标:前路坎坷,披荆斩棘,扶摇直上。 · 博客主页: @姬如祎 · 收录专栏: 数据结构与算法     目录 1. 函数接口一览 2. 函数接口的实现 2.1 BTNode* BuyNode(BTDataType x) 的实现 2.2 BTNode* CreateTree() 的实现  2.3 void

    2023年04月08日
    浏览(44)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包