二叉树的四种基本遍历方式(C语言)_二叉树中序遍历c语言代码-程序员宅基地

技术标签: 算法  c语言  二叉树  数据结构  

前言

Algorithms Data Structures = Programs
”数据结构 + 算法 = 程序“

by Niklaus Wirth

二叉树

注意:在阅读本文之前需要掌握栈和队列这两种基本的数据结构

二叉树是一种树形结构,其特点是每个节点至多只有两颗子树(即二叉树中不存在度大于2的节点),并且二叉树的子树有左右之分,其次序不能任意颠倒。

基本数据结构

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define dataType char
#define MAX_SIZE 50
#define Element BinaryTree *
#define endl() printf("\n")
typedef struct TreeNode
{
    
    /* data */
    dataType val;
    struct TreeNode *left;		//左子树
    struct TreeNode *right;		//右子树
} BinaryTree;
typedef struct Stack		//栈
{
    
    /* data */
    Element data[MAX_SIZE];
    int cursor;
} Stack;

typedef struct Queue		//队列
{
    
    /* data */
    Element data[MAX_SIZE];
    int rear;
    int front;
} Queue;

基本数据结构算法

void visited(BinaryTree *tree);
Stack initStack();
Element pop(Stack *st);
void push(Stack *st, Element el);
bool IsEmpty(Stack st);
Element peek(Stack st);
Queue initQueue();
Element get(Queue *q);
void put(Queue *q, Element el);
bool IsEmptyQueue(Queue q);
bool IsOverflowQueue(Queue q);

void visited(BinaryTree *tree)
{
    
    printf("%c\t", tree->val);
}
Queue initQueue()
{
    
    Queue q;
    q.front = 0;
    q.rear = 0;
    return q;
}
bool IsEmptyQueue(Queue q)
{
    
    return q.rear == q.front;
}
bool IsOverflowQueue(Queue q)
{
    
    return q.front >= MAX_SIZE;
}
Element get(Queue *q)
{
    
    return (*q).data[(*q).rear++];
}
void put(Queue *q, Element el)
{
    
    (*q).data[(*q).front++] = el;
}
Stack initStack()
{
    
    Stack st;
    st.cursor = -1;
    return st;
}
Element pop(Stack *st)
{
    
    return (*st).data[(*st).cursor--];
}
void push(Stack *st, Element el)
{
    
    (*st).data[++(*st).cursor] = el;
}
bool IsEmpty(Stack st)
{
    
    return st.cursor == -1 ? true : false;
}
Element peek(Stack st)
{
    
    return st.data[st.cursor];
}

建立一颗二叉树

递归建立二叉树

BinaryTree *create_binary_tree();
BinaryTree *create_binary_tree()
{
    
    dataType ch = getchar();
    if (ch != '#')
    {
    
        BinaryTree *tree = (BinaryTree *)malloc(sizeof(BinaryTree));
        tree->val = ch;
        tree->left = create_binary_tree();
        tree->right = create_binary_tree();
        return tree;
    }
    return NULL;
}

二叉树样例

ABD##E#H##CG#I##F##

二叉树样例

二叉树的四种基本遍历

  • 前序遍历

前序遍历(VLR), 是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

实现前序遍历之前,请读者先思考一下一个问题,怎么才算遍历完一个节点?

要进行前序遍历,就得从根节点(样例中的A节点)出发,遍历完其右结点,遍历其左节点,我们发现如果直接分析根节点是很复杂的,于是我们选择自低向上的分析法,先看D节点,由于D节点没有子节点,所以在访问完D节点之后,是不需要保存D节点的。

再看B节点,在访问完B节点之后,如果不将B节点保存,则无法访问到其后继节点,因此首先确定一点如果存在有后继节点的节点是需要先保存下来的,然后进入到其子节点,A节点同理。于是我们发现,越是后面保存的节点反而越先被访问完,因此我们选取一种能够实现后进先出得数据结构 — — , 这种数据结构作为保存节点的工具。

数据结构确定了,那我们应该采取何种算法呢?这就需要找到前序遍历的特点了,前面有底向上分析,得出数据结构,接下来就模拟遍历过程,找出规律或者是共同点。访问A,A是否有子节点,是,那就将A节点存入栈,然后往下走,此时问题又来了,往哪里走?往C走?显然不符合先序遍历,那么就只能往B走,走走走,边走边存,走到D,发现D点没有子节点,访问完之后可以不保存,那么接下来怎么办呢,我们发现B的的右节点E还没访问,那么怎么才能访问到E呢,我们惊喜的发现栈中存了B而且还是最后一个存入的,因此取出B,进入B的右子树E,发现E也有子节点,因此将E也存入栈,如此循环往复,直至栈为空,也就是遍历完成,分析至此,程序也不难写出,代码如下:

void preorder(BinaryTree *tree)
{
    
    Stack st = initStack();
    BinaryTree *temp = tree;
    while (!IsEmpty(st) || temp != NULL)
    {
    
        /* code */
        while (temp != NULL)
        {
    
            /* code */
            push(&st, temp);
            visited(temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
    
            temp = pop(&st);
            temp = temp->right;
        }
    }
}

前序遍历: A B D E H C G I F

  • 中序遍历

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

把所有的节点投影到水平面就是中序遍历的顺序。
中序遍历与前序遍历的思路差不多,区别在于什么时候进行访问节点。

void inorder(BinaryTree *tree)
{
    
    Stack st = initStack();
    BinaryTree *temp = tree;
    while (!IsEmpty(st) || temp != NULL)
    {
    
        /* code */
        while (temp != NULL)
        {
    
            /* code */
            push(&st, temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
    
            temp = pop(&st);
            visited(temp);
            temp = temp->right;
        }
    }
}

中序遍历: D B E H A G I C F

  • 后序遍历

后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。

后序遍历比较难,主要难点在于如何判断一个节点的左右节点是否都已访问。

void postorder(BinaryTree *tree)
{
    
    Stack st = initStack();
    BinaryTree *temp = tree;
    BinaryTree *record = NULL;
    while (!IsEmpty(st) || temp != NULL)
    {
    
        /* code */
        while (temp != NULL)
        {
    
            /* code */
            push(&st, temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
    
            temp = peek(st);

            if (temp->right != NULL && temp->right != record)
            {
    
                temp = temp->right;
            }
            else
            {
    
                visited(temp);
                record = pop(&st);
                temp = NULL;
            }
        }
    }
}

后序遍历: D H E B I G F C A

  • 层次遍历

二叉树的层次遍历 ,顾名思义就是指从二叉树的第一层(根节点)开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中,按从顶层到底层的次序访问树中元素,在同一层中,从左到右进行访问。

void levelorder(BinaryTree *tree)
{
    
    Queue q = initQueue();
    BinaryTree *temp = tree;
    put(&q, temp);
    while (!IsEmptyQueue(q))
    {
    
        /* code */
        temp = get(&q);
        visited(temp);
        if (temp->left != NULL)
            put(&q, temp->left);
        if (temp->right != NULL)
            put(&q, temp->right);
    }
}

层次遍历: A B C D E G F H I

总结

在本文中仅给出前序遍历的详细思路,因为四种遍历方式大同小异。写程序之前先思考以何种数据结构存储数据,以何种算法操作数据,把思路理清楚,写起程序来事半功倍。方法是死的,思路是活的,数据结构与算法之路,基础与思考很重要,不要做一个只会ctrl+c、crtl+v 程序员,与君共勉!

"学而不思则罔,思而不学则殆"

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42659832/article/details/120586222

智能推荐

40W+年薪算法岗,面试官都在问些什么?_算法岗年薪40-程序员宅基地

文章浏览阅读2.2k次。2015年自从我担任当时算法组的小组leader,我作为面试官面试了不少同学。前前后后面试了超过200名同学,其中有不少入职的同学后来发展都不错,也坚定了自己对于选人的标准的自信心。今年2020年找工作尤其艰难,我把这些年作为面试官一些重要的面试题整理出来,一共80道,希望能够帮助到大家,为了方便大家,我做了一个归类,一共分成了6大类,分别是:机器学习,特征工程,深度学习,NLP,CV,推荐系统。这些知识既是面试中的常见问题,也可以作为大家整理自己思路的参考资料。机器学习理论类:1. ._算法岗年薪40

STM32串行通信理解_stm32最大支持的串行通信个数-程序员宅基地

文章浏览阅读492次。文章目录一、通信接口的背景知识1.处理器与外部设备通信的两种方式2.串行通信按照数据传送方向分为:3.串行通信的通信方式:二、STM32串口通信基础1.STM32的串口通信接口2.UART异步通信方式引脚连接方法:3.UART异步通信方式特点:4.STM32串口通信过程:5.STM32异步通信要定义哪些参数:6.串口通信框图7.串口设置的一般步骤可以总结为如下几个步骤:一、通信接口的背景知识1.处理器与外部设备通信的两种方式(1)并行通信 -传输原理:数据各个位同时传输-优点:速度快-缺点:_stm32最大支持的串行通信个数

php简洁版JWT加密解密适用Laravel/ThinkPHP/Yii_laravel 解密 jwt-程序员宅基地

文章浏览阅读1.9k次。composer require firebase/php-jwtgit地址:https://github.com/firebase/php-jwt栗子:&lt;?phpuse \Firebase\JWT\JWT;$key = "example_key";$token = array( "iss" =&gt; "http://example.org", "aud"..._laravel 解密 jwt

RAID知识以及利用率-程序员宅基地

文章浏览阅读338次,点赞2次,收藏3次。作者:知乎用户链接:https://www.zhihu.com/question/20131784/answer/28026813来源:知乎著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。一共有0~6一共7种,这其中RAID 0、RAID1、RAID 5和RAID6比较常用。RAID 0:如果你有n块磁盘,原来只能同时写一块磁盘,写满了再下一块,做了RAID 0之..._raid4 得盘率

SQL Server如何启动_sqlserver启动程序在哪-程序员宅基地

文章浏览阅读1.2w次,点赞10次,收藏34次。1.单击开始程序,找到Microsoft SQL Server 2012,点击SQL Server配置管理器2.在弹出的窗口中点击sqlserver网络配置,点击协议在右侧点击tcp/ip,如果状态为禁用的话 先启用3.启用后右键点击tcp/ip协议,选择属性4.4.在弹出的窗口中,切换到ip地址窗口找到127.0.0.1本地IP地址,修改启用状态为是,然后点击确定5.然后返回到sqlserver服务,选择实例服务右键进行重新启动6.再次点击开始菜单,找到sql server mana_sqlserver启动程序在哪

Parsing ranges item in pcie-designware.c-程序员宅基地

文章浏览阅读1.3k次。parsing ranges item in pcie-designware.c

随便推点

Task :app:transformClassesAndResourcesWithR8ForRelease FAILED-程序员宅基地

文章浏览阅读5.5k次。这个是针对tinker报错问题,在运行gradlew assemblerelease的时候报一下错误:> Task :app:transformClassesAndResourcesWithR8ForRelease FAILEDR8 is the new Android code shrinker. If you experience any issues, ple..._transformclassesandresourceswithr8forrelease

Linux Install——SSH server_sudo apt install openssh-server-程序员宅基地

文章浏览阅读2.8k次,点赞3次,收藏5次。一、确认服务端是否安装ssh的服务器端ssh -V #这一步不准确netstat -tlp #用这个直接看有没有这样的进程[::]:ssh 如果安装可以看到下图所示:二、安装ssh服务端#执行如下命令sudo apt install openssh-server三、启动ssh-server#执行如下命令:/etc/init.d/ssh restart四、确认ssh-server已经正常工作#执行如下命令netstat -tlp如果正常工作会看到如下图所示的信息:看_sudo apt install openssh-server

greenplum麒麟安装笔记_麒麟系统编译greenplum-程序员宅基地

文章浏览阅读2.2k次。本周尝试在中标麒麟操作系统下安装greenplum。中标麒麟操作系统采用强化的Linux内核,我们首先准备好三台已安装中标麒麟服务版系统的虚拟机。规划他们的IP地址分别为:Master:10.81.2.20Segment1:10.81.2.21Segment2:10.81.2.22通过查找greenplum的官方网站可知,greenplum支持的操作系统如下:Red Hat Enterprise Linux 64-bit 7.x (See the following Note.)Re_麒麟系统编译greenplum

【Python】Web自动化,Xpath快速定位元素_python webfriver xpath-程序员宅基地

文章浏览阅读329次。例:百度一下:输入百度,点击搜索,这个过程的自动化1.点击元素 右键检查/打开开发者工具;2.选择那行代码右键选择copy,选择copy Xpath;3.粘贴到自己所写的代码里;4.搜索按钮定位使用同样方法;5.结果如下;参考:https://blog.csdn.net/Hu_wen/article/details/94738559..._python webfriver xpath

VMware Workstation 15 与 Device/Credential Guard_vmware与device/credential分别采用什么虚拟化架构-程序员宅基地

文章浏览阅读133次。VMware Workstation 15 与 Device/Credential Guard不兼容解决办法参考1参考2参考3看完 参考1 能解决问题的不用看 往后看了 因为 我是两者结合起来弄得 也就是关了hv,设置了hv服务禁用,并且关闭了内核保护1. 打开本电脑-》管理-》服务和应用程序-》服务下找到如下图的HV 主机服务,双击选择禁用。2. 打开Windows Po..._vmware与device/credential分别采用什么虚拟化架构

快速Android开发系列网络篇之Android-Async-Http-程序员宅基地

文章浏览阅读280次。先来看一下最基本的用法AsyncHttpClient client = new AsyncHttpClient();client.get("http://www.google.com", new AsyncHttpResponseHandler() { @Override public void onSuccess(String response) {..._d:\desk\android\meowsic-master\meowsic-master\app\libs\android-async-http-1.

推荐文章

热门文章

相关标签