树型结构、二叉树、二叉树的创建销毁、二叉树的四种遍历、二叉树层序遍历与队列结合

我要成为嵌入式高手之3月23日数据结构第六天！！
————————————————————————————

树形结构

特性： 一对多

概念：

由n个结点组成的有限集

有一个根结点；其他结点只有一个前驱结点，但可以有多个后继结点（一对多）

n = 0时为空树

专业词汇：

叶子结点（终端结点 ）

只有前驱没有后继

根结点

A

分支节点

B\C\D

结点度

该结点后继结点的个数 

度（默认为广度）

深度：这棵树所对应的层数

广度：这棵树里结点度最大的度

二叉树

树的度（广度）为2   且子节点的位置不能交换的数叫做二叉树

满二叉树

        在不增加层数的情况下无法再增加一个结点（叶子结点处于同一层、除叶子结点其他结点的度都为2）

k层满二叉树：

        第k层结点个数：2^(k-1);

        k层结点总个数：2^k-1;

完全二叉树

满二叉树是完全二叉树，完全二叉树不一定是满二叉树

概念：在满二叉树的基础上，若要增加结点只能从上至下、从左至右依次增加；若要删除结点只能从下至上、从右至左依次删除，则剩下的树为完全二叉树

例：有一棵完全二叉树的总结点个数为4847个，求该二叉树的叶子结点个数

答：2424个

二叉树的遍历

解决如何将一对多的树形结构存储到一对一的线性结构中的问题

前序遍历

根结点        左子树        右子树 —— A B C E H D F G        深度优先

中序遍历

左子树        根结点        右子树 —— C B H E A F D G        深度优先

后序遍历

左子树        右子树        根节点 —— C H E B F G D A        深度优先

层序遍历

从上至下、从左至右  逐层遍历 —— A B D C E F G H        广度优先

通过遍历的序列还原二叉树

只知道前序或后序不能还原唯一的二叉树，前序和后序也不能还原唯一二叉树、只有

前序 + 中序 = 唯一二叉树

后序 + 中序 = 唯一二叉树

前序：A B C

 前序：A B  C        后序：C B A

 

代码实现二叉树

结点

左子节点指针        数据域        右子节点指针

扩展二叉树

前序遍历：A B C # # E H # # # D F # # G # #

1、创建二叉树

/* 创建一个二叉树 */
TREE_NODE *CreateBtree()
{
    DATA_TYPE data = tree[idx++];

    if ('#' == data)
    {
        return NULL;
    }

    TREE_NODE *pnode = malloc(sizeof(TREE_NODE));
    if (NULL == pnode)
    {
        perror("fail to malloc TREE_NODE");
        return NULL;
    }

    pnode->data = data;
    pnode->pl = CreateBtree();
    pnode->pr = CreateBtree();

    return pnode;
}

2、前序遍历

/* 前序遍历一遍二叉树 */
void PreOrder(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    printf("%c ", proot->data);
    PreOrder(proot->pl);
    PreOrder(proot->pr);
}

3、中序遍历

void MidOrder(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    
    MidOrder(proot->pl);
    printf("%c ", proot->data);
    MidOrder(proot->pr);
}

4、后序遍历

void PosOrder(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    PosOrder(proot->pl);
    PosOrder(proot->pr);
    printf("%c ", proot->data);
}

5、获取二叉树的结点个数

/* 获取二叉树的结点个数 */
int GetBtreeNodeCnt(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return 0;
    }
    return 1+GetBtreeNodeCnt(proot->pl)+GetBtreeNodeCnt(proot->pr);
}

6、获取二叉树的层数

/* 获取二叉树层数 */
int GetBtreeLayerCnt(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return 0;
    }
    int lay_l = GetBtreeLayerCnt(proot->pl);
    int lay_r = GetBtreeLayerCnt(proot->pr);

    return lay_l > lay_r ? lay_l + 1 : lay_r + 1;
}

7、销毁二叉树

void DestroyBtree(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    DestroyBtree(proot->pl);
    DestroyBtree(proot->pr);
    free(proot);
}

 前7项运行结果：

8、二叉树的层序遍历

要依靠队列结构

头文件使用需要注意

哪里需要哪里包含

易知只有在tree.c的层序遍历中需要用到队列相关函数，故只需要在tree.c中包含queue.h

/* 二叉树的层序遍历 */
void LayerOrder(TREE_NODE *proot)
{
    QUEUE_LIST *pque = CreateQueueList();
    if (NULL == pque)
    {
        return ;
    }

    DATA_TYPE outdata;
    QUEUE_NODE *pnode = CreateQueueNode(proot);
    JoinQueueNode(pque, pnode);

    while (!IsEmptyQueue(pque))
    {
        LeaveQueueNode(pque, &outdata);
        printf("%c ", outdata->data);
        if (outdata->pl != NULL)
        {
            pnode = CreateQueueNode(outdata->pl);
            JoinQueueNode(pque, pnode);
        }
        if (outdata->pr != NULL)
        {
            pnode = CreateQueueNode(outdata->pr);
            JoinQueueNode(pque, pnode);
        }
    }

    DestroyQueue(pque);
}

 总程序

tree.c

#include "tree.h"
#include "queue.h"

int idx = 0;
char tree[] = "ABC##EH###DF##G##";

/* 创建一个二叉树 */
TREE_NODE *CreateBtree()
{
    BTDATA_TYPE data = tree[idx++];

    if ('#' == data)
    {
        return NULL;
    }

    TREE_NODE *pnode = malloc(sizeof(TREE_NODE));
    if (NULL == pnode)
    {
        perror("fail to malloc TREE_NODE");
        return NULL;
    }

    pnode->data = data;
    pnode->pl = CreateBtree();
    pnode->pr = CreateBtree();

    return pnode;
}

/* 前序遍历一遍二叉树 */
void PreOrder(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    printf("%c ", proot->data);
    PreOrder(proot->pl);
    PreOrder(proot->pr);
}

void MidOrder(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    
    MidOrder(proot->pl);
    printf("%c ", proot->data);
    MidOrder(proot->pr);
}

void PosOrder(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    PosOrder(proot->pl);
    PosOrder(proot->pr);
    printf("%c ", proot->data);
}

/* 获取二叉树的结点个数 */
int GetBtreeNodeCnt(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return 0;
    }
    return 1+GetBtreeNodeCnt(proot->pl)+GetBtreeNodeCnt(proot->pr);
}

/* 获取二叉树层数 */
int GetBtreeLayerCnt(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return 0;
    }
    int lay_l = GetBtreeLayerCnt(proot->pl);
    int lay_r = GetBtreeLayerCnt(proot->pr);

    return lay_l > lay_r ? lay_l + 1 : lay_r + 1;
}

void DestroyBtree(TREE_NODE *proot)
{
    if (NULL == proot)
    {
        return ;
    }
    DestroyBtree(proot->pl);
    DestroyBtree(proot->pr);
    free(proot);
}

/* 二叉树的层序遍历 */
void LayerOrder(TREE_NODE *proot)
{
    QUEUE_LIST *pque = CreateQueueList();
    if (NULL == pque)
    {
        return ;
    }

    DATA_TYPE outdata;
    QUEUE_NODE *pnode = CreateQueueNode(proot);
    JoinQueueNode(pque, pnode);

    while (!IsEmptyQueue(pque))
    {
        LeaveQueueNode(pque, &outdata);
        printf("%c ", outdata->data);
        if (outdata->pl != NULL)
        {
            pnode = CreateQueueNode(outdata->pl);
            JoinQueueNode(pque, pnode);
        }
        if (outdata->pr != NULL)
        {
            pnode = CreateQueueNode(outdata->pr);
            JoinQueueNode(pque, pnode);
        }
    }

    DestroyQueue(pque);
}

tree.h

#ifndef _TREE_H_
#define _TREE_H_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char BTDATA_TYPE;

typedef struct tree_node
{
    BTDATA_TYPE data;
    struct tree_node *pl;
    struct tree_node *pr;
}TREE_NODE;

extern TREE_NODE *CreateBtree();
extern void PreOrder(TREE_NODE *proot);
extern void MidOrder(TREE_NODE *proot);
extern void PosOrder(TREE_NODE *proot);
extern int GetBtreeNodeCnt(TREE_NODE *proot);
extern int GetBtreeLayerCnt(TREE_NODE *proot);
extern void DestroyBtree(TREE_NODE *proot);
extern void LayerOrder(TREE_NODE *proot);

#endif

queue.c 

#include "queue.h"

/* 创建队列 */
QUEUE_LIST *CreateQueueList()
{
    QUEUE_LIST *plist = malloc(sizeof(QUEUE_LIST));
    if (NULL == plist)
    {
        perror("fail to malloc list");
        return NULL;
    }

    plist->pbegin = NULL;
    plist->pend = NULL;
    plist->clen = 0;

    return plist;
}

QUEUE_NODE *CreateQueueNode(DATA_TYPE data)
{
    QUEUE_NODE *pnode = malloc(sizeof(QUEUE_NODE));
    if (NULL == pnode)
    {
        perror("fail to malloc node");
        return NULL;
    }
    pnode->data = data;
    pnode->pnext = NULL;

    return pnode;
}

/* 判断队列是否为空 */
int IsEmptyQueue(QUEUE_LIST *pque)
{
    return NULL == pque->pbegin;
}

/* 入队 */
int JoinQueueNode(QUEUE_LIST *plist, QUEUE_NODE *pnode)
{
    QUEUE_NODE *ptmp = NULL;
    
    if (NULL == plist->pbegin)
    {
        plist->pbegin = pnode;
        plist->pend = pnode;
        plist->clen++;
    }
    else
    {
        ptmp = plist->pend;
        ptmp->pnext = pnode;
        plist->pend = pnode;
        plist->clen++;
    }

    return 0;
}

/* 出队 */
int LeaveQueueNode(QUEUE_LIST *plist, DATA_TYPE *pdata)
{
    if (IsEmptyQueue(plist))
    {
        return -1;
    }

    QUEUE_NODE *pnode = plist->pbegin;
    plist->pbegin = pnode->pnext;
    if (NULL == plist->pbegin)
    {
        plist->pend = NULL;
    }
    if (pdata != NULL)
    {
        *pdata = pnode->data;
    }
    free(pnode);
    plist->clen--;

    return 0;
}

/* 清空队列 */
int DeleteQueueAll(QUEUE_LIST *plist)
{
    QUEUE_NODE *ptmp = plist->pbegin;
    QUEUE_NODE *pfree = NULL;
    
    if (NULL == plist->pbegin && plist->pend == NULL)
    {
        return -1;
    }
    while (ptmp != NULL)
    {
        pfree = ptmp;
        ptmp = ptmp->pnext;
        plist->pbegin = ptmp;
        free(pfree);
        plist->clen--;
    }
    plist->pend = NULL;

    return 0;
}

/* 获取队头数据 */
QUEUE_NODE *GetQueueBegin(QUEUE_LIST *plist)
{
    if (NULL == plist->pbegin && NULL == plist->pend)
    {
        return NULL;
    }
    else
    {
        return plist->pbegin;
    }
}

/* 销毁队列 */
int DestroyQueue(QUEUE_LIST *plist)
{
    int ret = 0;

    if (NULL == plist->pbegin && plist->pend == NULL)
    {
        free(plist);
    }
    else
    {
        ret = DeleteQueueAll(plist);
        if (0 == ret)
        {
            free(plist);
        }
    }

    return 0;
}

/* 测试:遍历 */
int SearchAllQueue(QUEUE_LIST *plist)
{
    QUEUE_NODE *ptmp = plist->pbegin;

    if (NULL == plist->pbegin && NULL == plist->pend)
    {
        printf("NO DATA!\n");
        return -1;
    }
    else
    {
        while (ptmp != NULL)
        {
            //printf("%d\n", ptmp->data);
            ptmp = ptmp->pnext;
        }
    }
    printf("len = %d\n", plist->clen);

    return 0;
}

 queue.h

#ifndef _QUEUE_H
#define _QUEUE_H

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

typedef TREE_NODE* DATA_TYPE;

typedef struct node
{
    DATA_TYPE data;
    struct node *pnext;
}QUEUE_NODE;

typedef struct list
{
    QUEUE_NODE *pbegin;
    QUEUE_NODE *pend;
    int clen;
}QUEUE_LIST;


extern QUEUE_LIST *CreateQueueList();
extern QUEUE_NODE *CreateQueueNode(DATA_TYPE data);
extern QUEUE_NODE *GetQueueBegin(QUEUE_LIST *plist);
extern int IsEmptyQueue(QUEUE_LIST *pque);
extern int JoinQueueNode(QUEUE_LIST *plist, QUEUE_NODE *pnode);
extern int LeaveQueueNode(QUEUE_LIST *plist, DATA_TYPE *pdata);
extern int SearchAllQueue(QUEUE_LIST *plist);
extern int DeleteQueueAll(QUEUE_LIST *plist);
extern int DestroyQueue(QUEUE_LIST *plist);

#endif

main.c

#include "tree.h"

int main()
{
    int cnt = 0;

    TREE_NODE *proot = CreateBtree();
    if (NULL == proot)
    {
        return -1;
    }

    printf("前序遍历:\n");
    PreOrder(proot);
    putchar('\n');

    printf("中序遍历:\n");
    MidOrder(proot);
    putchar('\n');

    printf("后序遍历:\n");
    PosOrder(proot);
    putchar('\n');
   
    printf("二叉树的结点个数: ");
    cnt = GetBtreeNodeCnt(proot);
    printf("%d\n", cnt);

    printf("二叉树的层数: %d\n", GetBtreeLayerCnt(proot));

    printf("二叉树的层序遍历: ");
    LayerOrder(proot);
    putchar('\n');

    DestroyBtree(proot);

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/484643.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

图论基础|841.钥匙和房间、463. 岛屿的周长

图论基础|841.钥匙和房间、463. 岛屿的周长

目录 841.钥匙和房间 思路&#xff1a;本题是一个有向图搜索全路径的问题。 只能用深搜&#xff08;DFS&#xff09;或者广搜&#xff08;BFS&#xff09;来搜。 463. 岛屿的周长 841.钥匙和房间 力扣题目链接 (opens new window) 有 N 个房间&#xff0c;开始时你位于 0…
阅读更多...
Windows Server 2016 配置NTP客户端

Windows Server 2016 配置NTP客户端

目录 1. 前提条件1.1 进入服务管理界面1.2 开启Windows Time服务 2. 情况1&#xff1a;可以直接设置NTP时钟2.1 Internet时间设置 3. 情况2&#xff1a;有的版本服务器上没有“Internet时间”3.1 运行gpedit.msc 打开本地策略组3.2 Windows 时间服务3.3 配置Windows NTP客户端3…
阅读更多...
2023年天府杯全国大学生数学建模竞赛A题震源属性识别模型构建与震级预测解题全过程文档及程序

2023年天府杯全国大学生数学建模竞赛A题震源属性识别模型构建与震级预测解题全过程文档及程序

2023年天府杯全国大学生数学建模竞赛 A题 震源属性识别模型构建与震级预测 原题再现&#xff1a; 地震是一种较为复杂的地壳运动现象&#xff0c;全世界每年发生的地震灾害事故不计其数。旨在减少地震灾害的地震预警预报技术需要在日常地震监测中有效识别出天然地震事件&…
阅读更多...
go面向对象

go面向对象

继承 封装 多态 定义结构体 //定义老师的结构体 type Teacher struct {Name stringAge intSchool string }func main() {var t1 Teacherfmt.Println(t1)t1.Name "tom"t1.Age 20t1.School "school"fmt.Println(t1) } 结构体实例的创建 package ma…
阅读更多...
springboot项目中，子模块中无法引入父模块中类

springboot项目中，子模块中无法引入父模块中类

问题&#xff1a; 当前模块kangning_admin中想引入 com.google.code.kaptcha.Producer类&#xff0c;但是当前模块中没有该类 解决办法 1、在pom.xml文件上右键---Maven---Reload project 重新加载pom文件中的依赖 2、 在Idea的右边Maven窗口&#xff0c;在根目录上执行cle…
阅读更多...
基于SpringBoot的会员制医疗预约服务管理信息系统

基于SpringBoot的会员制医疗预约服务管理信息系统

开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea 系统展示 系统功能模块 会员制医疗预约服务管…
阅读更多...
02课程发布模块之部署Nginx

02课程发布模块之部署Nginx

部署Nginx 部署网关 通过Nginx访问后台网关&#xff0c;然后由网关再将请求转发到具体的微服务,网关会把请求转发到具体的服务 upstream gatewayserver{server 127.0.0.1:63010 weight10; } # 网站首页对应的虚拟机 server {listen 80;server_name www.51xuecheng.cn…
阅读更多...
Java 沉淀-2

Java 沉淀-2

一维数组 初始化&#xff1a; 动态初始化&#xff1a;数组声明且为数组元素分配空间与赋值操作分开进行 静态初始化&#xff1a;在定义数组的同时就为数组元素分配空间并赋值 数组元素类型 二维数组 数组中的数组 初始化 注意特殊学法情况&#xff1a;int[]x,y[]: x是一维数…
阅读更多...
数据库范式拆分实战

数据库范式拆分实战

函数依赖 如果给定一个X&#xff0c;能唯一确定一个Y&#xff0c;就称X确定Y&#xff0c;或者说Y依赖于X&#xff0c;例如Y X*X函数。 X -> Y&#xff08;X确定Y&#xff0c;Y依赖于X&#xff09; 部分函数依赖 A可确定C&#xff0c;&#xff08;A&#xff0c;B&#xff09…
阅读更多...
[金三银四] 操作系统上下文切换系列

[金三银四] 操作系统上下文切换系列

图源&#xff1a; https://zhuanlan.zhihu.com/p/540717796 文章目录 2.11 cpu 的上下文切换2.12 协程的上下文切换2.13 线程的上下文切换2.14 进程的上下文切换2.15 中断上下文切换2.16 什么时候会发生进程的上下文切换2.17 什么时候会发生线程的上下文切换2.18 什么时候会发生…
阅读更多...
程序汪保姆教程在linux上部署运行一套SpringBoot内容管理系统

程序汪保姆教程在linux上部署运行一套SpringBoot内容管理系统

❝ 程序汪已经分享了很多开源项目了&#xff0c;发现一个痛点很多人拿到开源项目了不会部署运行&#xff0c;光看代码很多人看不下去的&#xff08;程序汪也是这样&#xff09;&#xff0c;程序汪建议拿到开源项目了&#xff0c;一定要想办法把项目运行起来跑跑&#xff0c;然后…
阅读更多...
树的遍历方式DFS和BFS

树的遍历方式DFS和BFS

DFS(depth first search) 深度优先遍历 从图中一个未访问的顶点V开始&#xff0c;沿着一条路一直走到底&#xff0c;然后从这条路尽头的节点回退到上一个节点&#xff0c;再从另一条路走到底…不断递归重复这个过程&#xff0c;直到所有的顶点都遍历完成。前序遍历&#xff0c…
阅读更多...
【Postman】工具使用介绍

【Postman】工具使用介绍

一、postman工具介绍 1.什么是postman postman是谷歌开发的一款网页调试和接口测试工具&#xff0c;能够发送任何请求类型的http请求&#xff0c;支持GET/POST/PUT/DELETE等方法。postman简单易用&#xff0c;可以直接填写URL&#xff0c;header&#xff0c;body就可以发送一…
阅读更多...
OpenHarmony开发自测试执行框架

OpenHarmony开发自测试执行框架

OpenHarmony为开发者提供了一套全面的开发自测试框架OHA-developer_test&#xff0c;开发者可根据测试需求开发相关测试用例&#xff0c;开发阶段提前发现缺陷&#xff0c;大幅提高代码质量。 本文从基础环境构建&#xff0c;用例开发&#xff0c;编译以及执行等方面介绍OpenH…
阅读更多...
双向链表

双向链表

目录 单向链表 双向链表 特点 缺点 双向链表的封装 单向链表 只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。也就是链表相连的过程是单向的. 实现的原理是上一个链表中有一个指向下一个的引用 单向链表有一个比较明显的缺点: 我们可以轻松的到达下一个节点,但是回到…
阅读更多...
Docker 入门使用说明

Docker 入门使用说明

Docker 入门使用说明 Docker 安装 Docker 官网&#xff1a;Docker Docker 安装说明&#xff1a;Docker 安装说明 这里由于 Docker 在实时更新&#xff0c;所以每次安装 Docker 用来导入 key 的链接可能会有变化&#xff0c;这里就参考官方的安装方法即可 Docker 常用命令说…
阅读更多...
OSCP靶场--Clue

OSCP靶场--Clue

OSCP靶场–Clue 考点(文件读取读取配置中的密码rce认证后利用sudo 提权) 1.nmap扫描 ┌──(root㉿kali)-[~/Desktop] └─# nmap -sV -sC -p- 192.168.163.240 --min-rate 2500 Starting Nmap 7.92 ( https://nmap.org ) at 2024-03-14 08:44 EDT Nmap scan report for 192…
阅读更多...
网络通信VLAN学习篇

网络通信VLAN学习篇

拓扑图 如上图&#xff0c;pc3&#xff0c;pc5同一网络&#xff0c;pc4&#xff0c;pc6同一网络&#xff0c;vlan的划分就是虚拟局域网&#xff0c;局域网的理解就是同一vlan下的设备可以相互通信&#xff0c;不同vlan不可以通信&#xff08;通过三层交换机可以实现通信的&…
阅读更多...
缓存穿透、缓存击穿、缓存雪崩及其解决方法

缓存穿透、缓存击穿、缓存雪崩及其解决方法

缓存穿透、缓存击穿、缓存雪崩是redis的三大问题。 在介绍这三大问题之前&#xff0c;我们需要先了解Redis作为一个缓存中间件&#xff0c;在项目中是如何工作的。首先看一下在没有缓存中间件的时候的系统数据访问的架构图&#xff1a; 客户端发起一个查询请求的时候&#xff…
阅读更多...
面试算法-98-随机链表的复制

面试算法-98-随机链表的复制

题目 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&#xff0c;其中每个新节点的值都设为其对应的原节点的值。新节…
阅读更多...
最新文章

Copyright @ 2022~2023