二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解

二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解0.写在最前面希望大家收藏:本文持续更新地址:https://haoqchen.site/2018/05/23/go-through-binary-tree/    复习到二叉树,看到网上诸多博客文章各种绕,记得头晕。个人觉得数学、算法这些东西都是可以更直观简洁地表示,然后被记住的,并不需要靠死记硬背。本文的程序基本来源于《大话数据结构》,个人感觉是一本非常好的书,推荐去看。…

大家好,又见面了,我是你们的朋友全栈君。

0. 写在最前面

希望大家收藏:

本文持续更新地址:https://haoqchen.site/2018/05/23/go-through-binary-tree/

    复习到二叉树,看到网上诸多博客文章各种绕,记得头晕。个人觉得数学、算法这些东西都是可以更直观简洁地表示,然后被记住的,并不需要靠死记硬背。

本文的程序基本来源于《大话数据结构》,个人感觉是一本非常好的书,推荐去看。

1. 为什么叫前序、后序、中序?

    一棵二叉树由根结点、左子树和右子树三部分组成,若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树,则二叉树的遍历方式有 6 种:DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别,所以,只讨论三种方式:

DLR–前序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 )

LDR–中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面)

LRD–后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)

需要注意几点:

  1. 根是相对的,对于整棵树而言只有一个根,但对于每棵子树而言,又有自己的根。比如对于下面三个图,对于整棵树而言,A是根,A分别在最前面、中间、后面被遍历到。而对于D,它是G和H的根,对于D、G、H这棵小树而言,顺序分别是DGH、GDH、GHD;对于C,它是E和F的根,三种排序的顺序分别为: CEF、ECF、EFC。是不是根上面的DLR、LDR、LRD一模一样呢~~
  2. 整棵树的起点,就如上面所说的,从A开始,前序遍历的话,一棵树的根永远在左子树前面,左子树又永远在右子树前面,你就找他的起点好了。
  3. 二叉树结点的先根序列、中根序列和后根序列中,所有叶子结点的先后顺序一样
  4. 建议看看文末第3个参考有趣详细的推导

二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解

                  前序遍历(DLR)                                 中序遍历(LDR)                             后序遍历(LRD)

 

2. 算法上的前中后序实现

除了下面的递归实现,还有一种使用栈的非递归实现。因为递归实现比较简单,且容易关联到前中后,所以

typedef struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode * parent;
}TreeNode;
 
void pre_order(TreeNode * Node)//前序遍历递归算法
{
    if(Node == NULL)
        return;
    printf("%d ", Node->data);//显示节点数据,可以更改为其他操作。在前面
    pre_order(Node->left);
    pre_order(Node->right);
}
void middle_order(TreeNode *Node)//中序遍历递归算法
{
    if(Node == NULL)
        return;
    middle_order(Node->left);
    printf("%d ", Node->data);//在中间
    middle_order(Node->right);
}
void post_order(TreeNode *Node)//后序遍历递归算法
{
    if(Node == NULL)
        return; 
    post_order(Node->left);
    post_order(Node->right);
    printf("%d ", Node->data);//在最后
}

3. 层序遍历

  层序遍历嘛,就是按层,从上到下,从左到右遍历,这个没啥好说的。

二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解

参考

1.《大话数据结构》

2.https://cnbin.github.io/blog/2016/01/05/er-cha-shu-de-bian-li/

3.https://blog.csdn.net/soundwave_/article/details/53120766

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/131498.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • linux查看网卡速率命令_linux查看网卡千兆还是万兆

    linux查看网卡速率命令_linux查看网卡千兆还是万兆1、ethtoolethtool网络接口名#ethtoolem4Settingsforem4:Supportedports:[TP]Supportedlinkmodes:10baseT/Half10baseT/Full100baseT/Half100baseT/Full1000baseT/FullSupportsauto-negotiation:YesAdvertis…

  • wing是什么_数独算法代码

    wing是什么_数独算法代码原题链接设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。输入格式第一行为一个整数N,表示 N×N 的方格图。接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。行和列编号从

  • Android移动应用程序开发

    Android移动应用程序开发

  • Linux常用命令大全

    Linux常用命令大全

    2021年10月15日
  • kafka topicPartitions问题

    kafka topicPartitions问题当我实现三个消费者去同时消费一个Topic(默认没有分区)消息时,三个消费者同时消费到了同样的消息现象如下:2019-06-1115:30:02.516[org.springframework.kafka.KafkaListenerEndpointContainer#0-0-C-1]INFOcom.example.kafka.consumer.TestB-==[cousumerC…

  • Pycharm 最新激活码 2021[免费获取]

    (Pycharm 最新激活码 2021)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlMLZPB5EL5Q-eyJsaWNlbnNlSWQi…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号