树二叉树

树

​ 树是 n（n≥0）个结点的有限集。当 n = 0时，称为空树。在任意一颗非空树中应满足：

（1）有且仅有一个特定的称为根的结点。

（2）当 n > 1时，其余结点可分为 m（m > 0）个互不相交的有限集T1, T2, …, Tm，其中每个集合本身又是一棵树，并且称为根的子树。

​ 树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

（1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。

（2）树中所有结点可以有零个或多个后继。
请添加图片描述

二叉树

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

​ 与树相似，二叉树也以递归的形式定义，二叉树是 n（n ≥ 0）个结点的有限集合：

（1）或者为空二叉树，即 n = 0。

（2）或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树分别是一颗二叉树。

满二叉树：

如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 。
1
2
3
4
5
6
7

完全二叉树：

深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。
1
2
3
4
5
6

普通二叉树：
1
2
3
4
5
6
7
8
9
10
A
B
D
C

二叉查找树：

二叉查找树又称二叉排序树或者二叉搜索树。
1
2
3
4
5
6
7
8
9
10
A
B
D
C

特点：

  • 每个节点上最多有两个子节点。
  • 左子树上所有节点的值都小于根节点的值。
  • 右子树上所有节点的值都大于根节点的值。

目的：

  • 提高检索数据的性能。

二茶树的链式存储

typedef char BiElemType;
typedef struct BiTNode {
    BiElemType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}

请添加图片描述

二叉树建树

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


typedef char BiElemType;
// 树结点
typedef struct BiTNode {
    // 数据
    BiElemType data;
    // 左子树
    struct BiTNode *lchild;
    // 右子树
    struct BiTNode *rchild;

} BiTNode, *BiTree;

// 用于构建辅助链队结点
typedef struct LinkNode {
    // 用于存储树的某一个结点的地址
    BiTree p_tree;
    struct LinkNode *next;
} LinkNode;


int main() {

    // 创建树根
    BiTree Tree = NULL;

    // 用来指向新申请的树结点
    BiTree tree_new_node;

    // 队列头 队列尾 队列新结点 当前树的父结点（要插入结点的位置）
    LinkNode *q_head = NULL, *q_tail = NULL, *q_new_node = NULL, *q_cur = NULL;

    char c;
    while (scanf("%c", &c)) {
        if ('\n' == c) {
            break;
        }

        // 申请树结点
        // calloc 申请空间并对空间进行初始化为0
        tree_new_node = (BiTree) calloc(1, sizeof(BiTNode));
        tree_new_node->data = c;

        // 队列新结点
        q_new_node = (LinkNode *) calloc(1, sizeof(LinkNode));
        // 新结点p_tree存储新的树结点地址
        q_new_node->p_tree = tree_new_node;
        q_new_node->next = NULL;

        // 如果树为空
        if (NULL == Tree) {
            // 树根
            Tree = tree_new_node;

            // 队首
            q_head = q_new_node;
            // 队尾
            q_tail = q_new_node;
            // 当前树的父结点（要插入结点的位置）
            q_cur = q_new_node;

            // 结束本次循环
            continue;
        } else {
            // 新结点放入队列中
            q_tail->next = q_new_node;
            // 新结点成为新尾部
            q_tail = q_new_node;
        }

        // 当前父结点插入左子树
        if (NULL == q_cur->p_tree->lchild) {
            q_cur->p_tree->lchild = tree_new_node;
        } else if (NULL == q_cur->p_tree->rchild) {
            q_cur->p_tree->rchild = tree_new_node;

            //当前父结点左右子树都有了 队列下一个结点作为树的父结点
            q_cur = q_cur->next;
        }
    }

    return 0;
}

二叉树遍历

深度优先遍历

二叉树的深度优先遍历有三种方式，前序遍历、中序遍历、后序遍历。

  • 前序遍历是先打印自身，再打印左子树，再打印右子树。
  • 中序遍历是先打印左子树，再打印自身，再打印右子树，中序遍历相当于把树压扁。
  • 后序遍历是先打印左子树，再打印右子树，最后打印当前结点。
#include <stdio.h>
#include <stdlib.h>


typedef char BiElemType;
// 树结点
typedef struct BiTNode {
    // 数据
    BiElemType data;
    // 左子树
    struct BiTNode *lchild;
    // 右子树
    struct BiTNode *rchild;

} BiTNode, *BiTree;

// 用于构建辅助链队结点
typedef struct LinkNode {
    // 用于存储树的某一个结点的地址
    BiTree p_tree;
    struct LinkNode *next;
} LinkNode;


/*
 * 先序遍历
 * 用递归思想解决 把每个结点看作一棵树
 */
void pre_order(BiTree p) {
    if (NULL != p) {
        // 本身
        printf("%c", p->data);
        // 左子树
        pre_order(p->lchild);
        // 右子树
        pre_order(p->rchild);
    }
}

/*
 * 中序遍历
 * 用递归思想解决 把每个结点看作一棵树
 */
void in_order(BiTree p) {
    if (NULL != p) {
        // 左子树
        in_order(p->lchild);
        // 本身
        printf("%c", p->data);
        // 右子树
        in_order(p->rchild);
    }
}


/*
 * 后续遍历
 * 用递归思想解决 把每个结点看作一棵树
 */
void post_order(BiTree p) {
    if (NULL != p) {
        // 左子树
        post_order(p->lchild);
        // 右子树
        post_order(p->rchild);
        // 本身
        printf("%c", p->data);
    }
}


int main() {

    // 创建树根
    BiTree Tree = NULL;

    // 用来指向新申请的树结点
    BiTree tree_new_node;

    // 队列头 队列尾 队列新结点 当前树的父结点（要插入结点的位置）
    LinkNode *q_head = NULL, *q_tail = NULL, *q_new_node = NULL, *q_cur = NULL;

    char c;
    while (scanf("%c", &c)) {
        if ('\n' == c) {
            break;
        }

        // 申请树结点
        // calloc 申请空间并对空间进行初始化为0
        tree_new_node = (BiTree) calloc(1, sizeof(BiTNode));
        tree_new_node->data = c;

        // 队列新结点
        q_new_node = (LinkNode *) calloc(1, sizeof(LinkNode));
        // 新结点p_tree存储新的树结点地址
        q_new_node->p_tree = tree_new_node;
        q_new_node->next = NULL;

        // 如果树为空
        if (NULL == Tree) {
            // 树根
            Tree = tree_new_node;

            // 队首
            q_head = q_new_node;
            // 队尾
            q_tail = q_new_node;
            // 当前树的父结点（要插入结点的位置）
            q_cur = q_new_node;

            // 结束本次循环
            continue;
        } else {
            // 新结点放入队列中
            q_tail->next = q_new_node;
            // 新结点成为新尾部
            q_tail = q_new_node;
        }

        // 当前父结点插入左子树
        if (NULL == q_cur->p_tree->lchild) {
            q_cur->p_tree->lchild = tree_new_node;
        } else if (NULL == q_cur->p_tree->rchild) {
            q_cur->p_tree->rchild = tree_new_node;

            //当前父结点左右子树都有了 队列下一个结点作为树的父结点
            q_cur = q_cur->next;
        }
    }

    // 先序遍历
    printf("Pre Order: ");
    pre_order(Tree);
    printf("\n");

    // 中序遍历
    printf("In Order: ");
    in_order(Tree);
    printf("\n");

    // 后序遍历
    printf("Post Order: ");
    post_order(Tree);
    printf("\n");

    return 0;
}

输入结果：

abcdefghi
Pre Order: abdhiecfg
In Order: hdibeafcg
Post Order: hidebfgca

Process finished with exit code 0

广度优先遍历

​ 层次遍历是一种广度优先遍历，层次遍历与层次建树的原理非常相似。层次遍历必须试用辅助队列。

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


typedef char BiElemType;
// 树结点
typedef struct BiTNode {
    // 数据
    BiElemType data;
    // 左子树
    struct BiTNode *lchild;
    // 右子树
    struct BiTNode *rchild;

} BiTNode, *BiTree;

// 用于构建辅助链队结点
typedef BiTNode ElemType;
typedef struct LinkNode {
    ElemType *data;
    struct LinkNode *next;
} LinkNode;
typedef struct LinkQueue {
    LinkNode *front, *rear;
} LinkQueue;


/*
 * 队列初始化
 */
void init_queue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}


/*
 * 队列是否为空
 */
bool queue_empty(LinkQueue Q) {
    return Q.front == Q.rear;
}


/*
 * 入队
 */
void enqueue(LinkQueue &Q, BiTree T) {
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = T;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

/*
 * 出队
 */
bool dequeue(LinkQueue &Q, BiTree &T) {
    // 队列为空
    if (queue_empty(Q)) {
        return false;
    }

    LinkNode *p = Q.front->next;
    T = p->data;

    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p);
    return true;
}


/*
 * 层序遍历
 *
 * 跟层次建树几乎一样 用辅助队列实现
 */
void level_order(BiTree T) {
    LinkQueue Q;
    init_queue(Q);

    // 树根入队
    enqueue(Q, T);
    // 从队列出队的树结点
    BiTree p;

    // 队列不为空
    while (!queue_empty(Q)) {
        // 出队
        dequeue(Q, p);
        putchar(p->data);

        // 判断当前结点是否有左孩子
        if (NULL != p->lchild) {
            // 左孩子入队
            enqueue(Q, p->lchild);
        }

        // 判断当前结点是否有右孩子
        if (NULL != p->rchild) {
            // 右孩子入队
            enqueue(Q, p->rchild);
        }
    }

}


int main() {

    // 创建树根
    BiTree Tree = NULL;

    // 用来指向新申请的树结点
    BiTree tree_new_node;

    // 队列头 队列尾 队列新结点 当前树的父结点（要插入结点的位置）
    LinkNode *q_head = NULL, *q_tail = NULL, *q_new_node = NULL, *q_cur = NULL;

    char c;
    while (scanf("%c", &c)) {
        if ('\n' == c) {
            break;
        }

        // 申请树结点
        // calloc 申请空间并对空间进行初始化为0
        tree_new_node = (BiTree) calloc(1, sizeof(BiTNode));
        tree_new_node->data = c;

        // 队列新结点
        q_new_node = (LinkNode *) calloc(1, sizeof(LinkNode));
        // 新结点p_tree存储新的树结点地址
        q_new_node->data = tree_new_node;
        q_new_node->next = NULL;

        // 如果树为空
        if (NULL == Tree) {
            // 树根
            Tree = tree_new_node;

            // 队首
            q_head = q_new_node;
            // 队尾
            q_tail = q_new_node;
            // 当前树的父结点（要插入结点的位置）
            q_cur = q_new_node;

            // 结束本次循环
            continue;
        } else {
            // 新结点放入队列中
            q_tail->next = q_new_node;
            // 新结点成为新尾部
            q_tail = q_new_node;
        }

        // 当前父结点插入左子树
        if (NULL == q_cur->data->lchild) {
            q_cur->data->lchild = tree_new_node;
        } else if (NULL == q_cur->data->rchild) {
            q_cur->data->rchild = tree_new_node;

            //当前父结点左右子树都有了 队列下一个结点作为树的父结点
            q_cur = q_cur->next;
        }
    }

    // 层次遍历
    printf("Level Order: ");
    level_order(Tree);

    return 0;
}

输出结果：

abcdefghi
Level Order: abcdefghi

Process finished with exit code 0

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

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

相关文章

bitset用法

bitset用法

参考:https://blog.csdn.net/weixin_45697774/article/details/105563993 题目:https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/description/ class Solution { public:int maxTotalReward(vector<int>& rewardValues) {bitset<10000…
阅读更多...
未卸载干净的proteus安装教程7.8

未卸载干净的proteus安装教程7.8

提醒&#xff1a; 针对第一次安装推荐博文&#xff1a;https://jingyan.baidu.com/article/656db918f8590de381249cbf.html 1、一定要以管理员身份运行软件。 2、以管理员身份运行软件后&#xff0c;默认的ISIS Professional路径是C:\Program Files \Labcenter Electronics\…
阅读更多...
写给大数据开发，如何去掌握数据分析

写给大数据开发，如何去掌握数据分析

这篇文章源于自己一个大数据开发&#xff0c;天天要做分析的事情&#xff0c;发现数据分析实在高大上很多&#xff0c;写代码和做汇报可真比不了。。。。 文章目录 1. 引言2. 数据分析的重要性2.1 技能对比2.2 业务理解的差距 3. 提升数据分析能力的方向4. 数据分析的系统过程4…
阅读更多...
初识springclould到生产者消费者的RPC通信

初识springclould到生产者消费者的RPC通信

SpringClould SpringBoot和SpringClould搭建springcloud创建项目管理实体类模块服务提供者模块消费者 Eureka 服务注册与发现 SpringBoot和SpringClould springboot和springclould都是spring系列的衍生品&#xff0c;都可以在spring的官网找到对应的参考文档和学习路线以及核心…
阅读更多...
PHP“well”运动健身APP-计算机毕业设计源码87702

PHP“well”运动健身APP-计算机毕业设计源码87702

【摘要】 随着互联网的趋势的到来&#xff0c;各行各业都在考虑利用互联网将自己的信息推广出去&#xff0c;最好方式就是建立自己的平台信息&#xff0c;并对其进行管理&#xff0c;随着现在智能手机的普及&#xff0c;人们对于智能手机里面的应用“well”运动健身app也在不断…
阅读更多...
安装systemd-bootchart

安装systemd-bootchart

要安装systemd-bootchart&#xff0c;你可以按照以下步骤进行&#xff1a; 步骤一&#xff1a;更新软件包列表 首先&#xff0c;打开终端并更新你的软件包列表&#xff0c;以确保你拥有最新的可用软件包信息。运行以下命令&#xff1a; sudo apt update步骤二&#xff1a;安…
阅读更多...
Python 连接 MySQL 及 SQL增删改查（主要使用sqlalchemy）

Python 连接 MySQL 及 SQL增删改查（主要使用sqlalchemy）

目录 一、环境 二、MySQL的连接和使用 2.1方式一&#xff1a;sql为主 2.1.1创建连接 2.1.2 表结构 2.1.3 新增数据 ​编辑 2.1.4 查看数据 ​编辑 2.1.5 修改数据 2.1.6 删除数据 2.2方式二&#xff1a;orm对象关系映射 2.2.1 mysql连接 2.2.2 创建表 2.2.3 新增…
阅读更多...
ORA-01652 表空间不够解决方案

ORA-01652 表空间不够解决方案

前章&#xff1a;出现表空间不足不要手动强制删除对应数据文件存储目录下的DBF文件&#xff0c;需要用SQL语句进行数据文件的DROP&#xff0c;否则会导致ORA-01033报错&#xff0c;因为我没有开启数据库的归档所以不能通过RECOVER的形式找回数据文件最后只能重装本地ORACLE。 …
阅读更多...
大模型如何通过token进行推理?

大模型如何通过token进行推理?

大型模型通过token进行推理的过程通常涉及以下步骤&#xff1a; 1、Tokenization&#xff08;分词&#xff09;&#xff1a;首先&#xff0c;输入文本或序列被分割成tokens&#xff0c;这些tokens通常是单词、子词或字符的序列。这一步通常由预训练模型的tokenizers完成。 2、…
阅读更多...
转型AI产品经理（7）：“格式塔原则”如何应用在Chatbot产品中

转型AI产品经理（7）：“格式塔原则”如何应用在Chatbot产品中

格式塔原则&#xff0c;又称为完形原则&#xff0c;它是一组关于人类如何感知视觉元素的心理学理论&#xff0c;这些原则说明了大脑如何将分散的视觉元素整合为有意义的整体&#xff0c;即使这些元素本身可能是分离的&#xff0c;帮助我们理解人们如何组织和解释复杂的视觉信息…
阅读更多...
2013年 阿拉斯加巴罗活动层厚度和土壤含水量

2013年 阿拉斯加巴罗活动层厚度和土壤含水量

Pre-ABoVE: Active Layer Thickness and Soil Water Content, Barrow, Alaska, 2013 ABoVE前&#xff1a;阿拉斯加巴罗活动层厚度和土壤含水量&#xff0c;2013年 简介 文件修订日期&#xff1a;2018-01-10 数据集版本&#xff1a;1 摘要 该数据集提供了 2013 年 8 月在…
阅读更多...
速卖通如何放关联？

速卖通如何放关联？

大家都知道&#xff0c;想要进行多账号操作必须一再小心&#xff0c;否则会有很大的关联风险&#xff0c;而账号关联所带来的后果是卖家绝对不能轻视的&#xff0c;严重的话会导致封号&#xff0c;这样一来自己前期的辛苦运营就全都打水漂了&#xff0c;因此防关联很重要&#…
阅读更多...
在idea中创建Scala项目教程

在idea中创建Scala项目教程

1.下载Scala支持插件 文件-设置-插件-marketplace 搜索Scala 下载 2.创建项目 文件-新建-项目-新项目-构建系统maven 3.创建Scala目录 Scr-main(右键)-新建-目录&#xff08;Scala回车键&#xff09;-scala(右键)-将项目标记为-源代码根目录 4.对当前项目引入Scala支持 未添…
阅读更多...
C++:day5

C++:day5

思维导图 例题 #include <iostream> using namespace std; class RMB { private:int yuan;int jiao;int fen;static int count;public:RMB(){count;}RMB(int yuan, int jiao, int fen) : yuan(yuan), jiao(jiao), fen(fen){count;}const RMB operator(const RMB &R)…
阅读更多...
14.《C语言》——【牛客网BC116—BC123题目讲解】

14.《C语言》——【牛客网BC116—BC123题目讲解】

亲爱的读者&#xff0c;大家好&#xff01;我是一名正在学习编程的高校生。在这个博客里&#xff0c;我将和大家一起探讨编程技巧、分享实用工具&#xff0c;并交流学习心得。希望通过我的博客&#xff0c;你能学到有用的知识&#xff0c;提高自己的技能&#xff0c;成为一名优…
阅读更多...
二叉树最大宽度

二叉树最大宽度

文章目录 前言二叉树最大宽度1.题目解析2.算法原理3.代码编写 总结 前言 二叉树最大宽度 1.题目解析 给你一棵二叉树的根节点 root &#xff0c;返回树的 最大宽度 。 树的 最大宽度 是所有层中最大的 宽度 。 每一层的 宽度 被定义为该层最左和最右的非空节点&#xff08;即…
阅读更多...
这个国际档案日，大比武放榜、直播预约、课件下载，一样都不能少!

这个国际档案日，大比武放榜、直播预约、课件下载，一样都不能少!

关注我们 - 数字罗塞塔计划 - 2024年6月9日第十七个国际档案日来临&#xff0c;数字罗塞塔计划放大招&#xff1a;第二届大比武活动榜单揭晓、ARCHE-2024上海智慧档案高峰论坛直播预约、2024上半年度课件大礼包下载。如此大礼&#xff0c;岂能错过&#xff1f; PART.01 榜单…
阅读更多...
SpringCloud-面试篇（二十四）

SpringCloud-面试篇（二十四）

&#xff08;1&#xff09;Nacos如何支撑数十万服务注册的压力 小型企业来讲nacos压力没有那么大&#xff0c;但是想阿里&#xff0c;服务的数量可能会达到数万&#xff0c;那麽多的服务。当服务原来越多时&#xff0c;除了服务注册以外&#xff0c;还有服务的定时更新&#x…
阅读更多...
2_1 Linux基础操作

2_1 Linux基础操作

2_1 Linux基础操作 文章目录 2_1 Linux基础操作0. 参考1. 装机后的一些小命令查看系统的信息2. 基础命令2.1 初识基本命令2.2 日期和时间 3. 帮助命令4. 关机、重启5. 设置主机名6. rm删除7. 软件包的管理RPM、 YUM8. IP知识9. 查看一些linux的信息10. 命令行快捷键11. 光盘挂载…
阅读更多...
网络网络层之(6)ICMPv6协议

网络网络层之(6)ICMPv6协议

网络网络层之(6)ICMPv6协议 Author: Once Day Date: 2024年6月2日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文章可参考专栏: 通信网络技术_Once-Day的博客-CS…
阅读更多...
最新文章

Copyright @ 2022~2023