二叉树Bynary_Tree(2):二叉树的递归遍历-程序员宅基地

前言


 

  以下的代码实现都以该完全二叉树为例:

  

 

声明结构体


 

typedef struct node
{
        char ch;
        struct node *lchild;
        struct node *rchild;
}TreeNode,*Tree;  //注意区别,例如TreeNode X1与*Tree X2,X1为结构体变量,X2为结构体指针变量

 

创建树


 

  

  1.采用前序创建

  2.若某子结点为不存在,则将其置为NULL,方法为:判断输入的字符是否为' * ',若为* ,则置当前结点为NULL

  3.递归创建子结点

 

void Create_pro(Tree* T)
{
    char ch;
    scanf("%c", &ch);  //需一次性输入所有字符,若分行输入,由于缓冲区问题,多出的空格将一直递归下去
    if (ch == '*')
    {
        *T = NULL;
    }
    else
    {
        *T = (Tree)malloc(sizeof(TreeNode));
        (*T)->ch = ch;
        Create_pro(&((*T)->lchild));
        Create_pro(&((*T)->rchild));
    }
}

   这里遇到的scanf缓冲区问题可移步:http://bbs.csdn.net/topics/390284350?page=1

 

删除二叉树


 

void ClearTree(Tree *T)  
{  
    if (!*T)  
    {  
        return;  
    }  
  
    ClearTree(&(*T)->lchild);  
    ClearTree(&(*T)->rchild);  
    free(*T);  
    *T = NULL;  
}  

 

前(根)序遍历


 

  先访问根结点,再分别前序遍历左、右两棵子树。前序遍历的结果是:ABCDEF

void Show_pro(Tree t)
{
        if(!t)
                return;
        printf("%c ",t->ch);
        Show_pro(t->lchild);
        Show_pro(t->rchild);
}

 

中(根)序遍历


 

  先中序遍历左子树,然后再访问根结点,最后再中序遍历遍历右子树。中序遍历的结果是:CBADEF

void Show_mid(Tree t)
{
        if(!t)
                return;
        Show_mid(t->lchild);
        printf("%c ",t->ch);
        Show_mid(t->rchild);
}

 

后(根)序遍历


 

  先后序遍历左子树,然后后序遍历右子树,最后访问根结点。后序遍历的结果是:CBEFDA

void Show_back(Tree t)
{
        if(!t)
                return;
        Show_back(t->lchild);
        Show_back(t->rchild);
        printf("%c ",t->ch);
}

 

层次遍历


 

  先按深度划分层,深度为1的对应树的第一层,深度为二的对应树的第二层...以此类推。然后逐层访问结点。

  除层次遍历外的三种遍历的设计核心思想为栈,后进先出,因此想到递归。而层次遍历是队列,先进先出,我采用循环队列去解决。具体的算法设计如下:

    1.定义一个队列Tree q[MAX]存储队列数据,头变量front与尾变量rear存储首尾位置,规定front == rear时队列为空。

    2.初始化,令 front = 0 ,rear = 0

    3.入队操作。将树T存入q[rear]中,即T入队,然后 rear = (rear+1)%MAX ,保持rear在0到MAX中循环

    4.输出结点数据。同时判断子结点中数据的存在情况,子结点不为NULL,则再进行入队操作

    5.出队操作。front = (front+1)%MAX;

void Show_level(Tree T)
{
        Tree q[MAX];  //队列
        Tree p;  //当前结点
        int front;
        int rear;

        //初始化
        front =0;
        rear =0;

        if(T)
        {
                q[rear] = T;
                rear = (rear+1)%MAX;
        }

        while(front != rear)
        {
                p = q[front];
                printf("%c ",p->ch);
                if(p->lchild)
                {
                        q[rear] = p->lchild;
                        rear = (rear+1)%MAX;
                }
                if(p->rchild)
                {
                        q[rear] = p->rchild;
                        rear = (rear+1)%MAX;
                }
                front = (front+1)%MAX;
        }
}

  层次遍历模块中有一个难点,即是入队操作,如何将树并入队列呢?我们想到将若根结点并入队列,那么整棵树便并入队列了。然而,就必须考虑一个问题,根结点的地址就是T的地址吗?

  

  通过在create_tree时将每一次申请的结点地址打印出来,并在创建完毕后在main函数里printf一次T的地址,实际结果如图,根结点地址果然是T的地址,那么我们就可以用根结点入队来实现整棵树入队的操作了,同时也可得到一个结论:递归建树,根结点地址即是树的地址。

 

判断树是否为空树


 

void IsTreeEmpty(Tree T)
{
        if(T)
                printf("Tree is not empty\n");
        else
                printf("Tree is empty\n");
}

 

  

 

 源代码


 

/*************************************************************************
	> File Name: Binary tree
	> Author: Bw98
	> Mail: [email protected]
	> Blog: www.cnblogs.com/Bw98blogs/
	> Created Time: SUN 16th Jul. 2017
 ************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct node
{
        char ch;
        struct node *lchild;
        struct node *rchild;
}TreeNode,*Tree;

void InitTree(Tree *T);  //树初始化
void Create_pro(Tree *T);  //创建一棵树并输入相应元素
void Show_pro(Tree t);  //先(根)序遍历输出
void Show_mid(Tree t);  //中(根)序遍历输出
void Show_back(Tree t);  //后(根)序遍历输出
void Show_level(Tree T);  //层次遍历输出
void IsTreeEmpty(Tree T);  //检测树是否为空
void ClearTree(Tree *T);  //清除树


int main()
{
        Tree t;
        InitTree(&t);
        printf("输入前序遍历序列(输入'*'时,该树结点为空)\n");
        Create_pro(&t);
        Show_pro(t);
        Show_mid(t);
        Show_back(t);
        Show_level(t);
        IsTreeEmpty(t);
        ClearTree(&t);
        IsTreeEmpty(t);
        return 0;
}

void InitTree(Tree *T)
{
        *T =NULL;
}

void Create_pro(Tree* T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '*')
    {
        *T = NULL;
    }
    else
    {
        *T = (Tree)malloc(sizeof(TreeNode));
        (*T)->ch = ch;
        Create_pro(&((*T)->lchild));
        Create_pro(&((*T)->rchild));
    }
}

void Show_pro(Tree t)
{
        if(!t)
                return;
        printf("%c ",t->ch);
        Show_pro(t->lchild);
        Show_pro(t->rchild);
}

void Show_mid(Tree t)
{
        if(!t)
                return;
        Show_mid(t->lchild);
        printf("%c ",t->ch);
        Show_mid(t->rchild);
}

void Show_back(Tree t)
{
        if(!t)
                return;
        Show_back(t->lchild);
        Show_back(t->rchild);
        printf("%c ",t->ch);
}

void Show_level(Tree T)
{
        Tree q[MAX];  //队列
        Tree p;  //当前结点
        int front;
        int rear;

        //初始化
        front =0;
        rear =0;

        if(T)
        {
                q[rear] = T;
                rear = (rear+1)%MAX;
        }

        while(front != rear)
        {
                p = q[front];
                printf("%c ",p->ch);
                if(p->lchild)
                {
                        q[rear] = p->lchild;
                        rear = (rear+1)%MAX;
                }
                if(p->rchild)
                {
                        q[rear] = p->rchild;
                        rear = (rear+1)%MAX;
                }
                front = (front+1)%MAX;
        }
}

void IsTreeEmpty(Tree T)
{
        if(T)
                printf("Tree is not empty\n");
        else
                printf("Tree is empty\n");
}

void ClearTree(Tree *T)
{
    if (!(*T))
    {
        return;
    }

    ClearTree(&(*T)->lchild);
    ClearTree(&(*T)->rchild);
    free(*T);
    *T = NULL;
}

  

 

 

 

 

  

 

转载于:https://www.cnblogs.com/Bw98blogs/p/7201577.html

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

智能推荐

解决重装win10系统找不到驱动器_重装系统时我们找不到任何驱动器-程序员宅基地

文章浏览阅读3.8w次,点赞19次,收藏111次。重装win10系统找不到驱动器的原因是:英特尔第十一代处理器采用了intel vmd技术,在此技术下安装系统时想找到驱动器,必须在安装过程中加载IRST驱动程序步骤如下:首先,下载IRST驱动程序(1)、进入电脑厂家官网输入电脑型号或编号搜索(2)、进入该设备界面后,点击表明是下载驱动的超链接(3)、在能下载驱动的界面下找到IRST驱动程序并下载然后,将下载的IRST驱动程序解压到拥有win10镜像的U盘中..._重装系统时我们找不到任何驱动器

在Matlab中绘制系统的根轨迹图_matlab绘制根轨迹图-程序员宅基地

文章浏览阅读10w+次,点赞125次,收藏500次。在Matlab中绘制系统的根轨迹图例如某系统的开环传递函数为:通过上面的开环传递函数可以直接求出2个开环共轭复零点,以及5个开环极点,然后确定根轨迹分支数…自己画根轨迹图的话还是比较麻烦的,这么简单的事就交给计算机干吧!下面就是在Matlab中进行编程来完成系统根轨迹的绘制:num=[1,2,4]; %开环传函分子多项式系数den..._matlab绘制根轨迹图

CI/CD 持续集成和持续交付 (一)_ci cd 持续集成-程序员宅基地

文章浏览阅读3.4w次,点赞3次,收藏9次。CI/CD 持续集成和持续交付 系类一在互联网时代,对于每一个企业,公司,产品快速迭代的重要性不言而喻,针对敏捷开发以使用CICD来完成。但是持续集成和持续交付(CI/CD)其实并没有那么容易实现,开发和运维总是忙里忙外,最后还吃力不讨好,更不要说持续交付过程中保证应用平滑升级,避免服务宕机。 需求业务及BUG:可以通过测试提出的bug新需求业务来快速提交给开发来完成需求和b_ci cd 持续集成

喜大普奔:新可美购物广场终于迎来开业季_商场试营业文章-程序员宅基地

文章浏览阅读149次。随着服务回龙观地区及周边居民20年的京客隆撤离该地区便民服务措施锐减给周边居民带来了生活上很大的不便经历过短暂的痛苦后终于迎来了新的希望回龙观地区居民福利来了真来了这次是真的来了二拨子桥东,G6(原八达岭高速)辅路旁新可美购物广场终于揭开诱人的面纱面向回龙观地区及周边居民敞开双臂热拥您的到来2021年9月29日新可美购物广场开业仪式将在广场前侧盛大举行同时也揭开了新可美购物广场9月29日——10月7日为期9天的开业季5000份礼品等着您_商场试营业文章

为什么不能在字符串上使用switch语句?_java中字符串为什么不能用switchcase-程序员宅基地

文章浏览阅读994次。此功能是否将在以后的Java版本中使用? 有人可以解释为什么我不能这样做吗,例如Java的switch语句的技术方式? _java中字符串为什么不能用switchcase

获取某年某月的第一天是星期几-程序员宅基地

文章浏览阅读6.7k次。首先我们要知道是哪一年那一个月:例如2018年6月代码:var nowdate=new Date('2018,06,01');var weekday=nowdate.getDay()这样获取到的weekday有可能是0/1/2/3/4/5/6,要注意返回是0代表这个月的第一天是星期天,其他的依次类推就可以知道是这个月的第一天是星期几了。当然一般我们实战时候不可能写死年月,所以要var year=2..._某年某月的第一天是星期几

随便推点

消费向上商业向下,爱特茂商业奥莱MALL项目入驻山东,引领商业项目空前发展_潍坊新辰里购物中心-程序员宅基地

文章浏览阅读292次。  素称“齐鲁大地”,儒家文化发源地的山东省,是我国人口大省之一,常住人口10152.7万人。提起山东,人们最先想到的会是青岛、济南这些经济与旅游业都极为发达的城市,但山东最具有潜力的城市却不是这些,而是正在奋起直追的潍坊。  2016年潍坊便被认定为“中国最具投资潜力和发展活力的新兴经济强市”之一,2021年全市实现生产总值7010.6亿元,同比增长9.7%,全市社会消费品零售总额实现2781.5亿元,同比增长16.4%,按消费类型分,商品零售2589.1亿元,增长15.5%;餐饮收入192.4亿元,增_潍坊新辰里购物中心

理解SpringMVC核心原理和设计模式应用背景_springmvc 的这种 mvc 模式了解吗?他的工作原理是什么?用到了哪些设计模式?-程序员宅基地

文章浏览阅读511次。对Java程序员来讲,做web开发最熟悉的框架莫过于SpringMVC了。之所以它能一统江湖,不是自己太优秀,而是对手太坑了,不知道大家还记不记得2017年左右Struts2爆出了一个大漏洞,自此之后,Web开发领域的就是SpringMVC的天下了。但是鉴于这么优秀的框架,很多程序员还只是停留在会用的状态,对底层的原理却不甚了解,所以今天咱么就来聊聊SpringMVC的工作原理。三层架构在开始介绍SpringMVC之前,咱么要先来了解一下web开发的历史。我们的开发架构一般都是..._springmvc 的这种 mvc 模式了解吗?他的工作原理是什么?用到了哪些设计模式?

Kali渗透Windows Server 2003_kali渗透run报错-程序员宅基地

文章浏览阅读7.8k次,点赞6次,收藏29次。两台虚拟机kali ip 192.168.18.128windows ip 192.168.18.1331)首先先扫描一下靶机nmap -sS -sV -O -Pn 192.168.18.133其中sS是半开放扫描,sV是扫描版本号,O是扫描操作系统,Pn是不进行ping,会快一点。可以看到有445端口,且是windows server 2003。2)使用msfco..._kali渗透run报错

Oracle Database Configuration Assistant 打不开-程序员宅基地

文章浏览阅读2.8k次。1:如果想要创建新的数据库实例,你一定熟悉的 DataBase Configuration Assistant ,但出现以下标志。 如下方式也是解决问题的一种。 2:解决方式(1)找到oracle安装目录bin文件下的dbca.bat,双击,如图所示: (2)选中“下一步”点击,如下图所示就可以创建新的数据库实例了。 ..._database configuration assistant打不开

go 项目的规范_go 项目设计准则-程序员宅基地

文章浏览阅读249次。本文档为个人博客文档系统的备份版本、作者:小游、作者博客:点击访问发现一个不错的开源库https://github.com/golang-standards/project-layout解释https://wjp2013.github.io/go/go-project-structure/参考文章:1.https://studygolang.com/articles/122592.https://github.com/whjstc/openbilibili-go-common-1/tree._go 项目设计准则

定义Person类,Person类中含有两个属性name 和age ,使用compare方法比较两个对象是否为同一个对象。假定name 和age 都相同就似为同一个对象_定义一个person类,包括name和age两个属性-程序员宅基地

文章浏览阅读1.6w次。/*思路:1.用private定义String类型的name,和int类型的age2.定义boolean类型的函数compare,利用if来判断name和age是否相同。3.如果相同就返回true,否则返回false*/class Person{private String name;//private 权限修饰符private int age;Pe_定义一个person类,包括name和age两个属性

推荐文章

热门文章

相关标签