树与二叉树---数据结构

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

1)树的根结点没有前驱,除根结点外的所有结点有 且只有一个前驱。

2)树中所有结点可以有零个或多个后继。

树结点数据结构

 满二叉树和完全二叉树

注意

完全二叉树,从左到右依次排,没有缺漏

二叉树的顺序存储

二叉树的层次遍历实战

项目结构

function.h文件

#ifndef LEARN_FUNCTION_H
#define LEARN_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>
typedef char BiElemType;
typedef struct BiNode{BiElemType c;struct BiNode *lchild;struct BiNode *rchild;
}BiNode, *BiTree;
//tag结构体是辅助队列使用的
typedef struct tag{BiTree p;//树的某一个结点的地址值struct tag *pnext;
}tag_t, *ptag_t;
#endif //LEARN_FUNCTION_H

main.cpp文件

calloc

  • 申请的空间大小是两个参数直接相乘,并对空间进行初始化,赋值为0,
  • 头文件#include <stdlib.h>
#include "function.h"int main(){BiTree pnew;char c;BiTree tree = NULL;ptag_t  phead = NULL,ptail = NULL,listpnew = NULL,pcur;while(scanf("%c",&c)){if(c == '\n'){break;//读到换行就结束}//calloc申请的空间大小是两个参数直接相乘,并对空间进行初始化,赋值为0,头文件#include <stdlib.h>pnew = (BiTree)calloc(1, sizeof(BiNode));pnew -> c = c;listpnew = (ptag_t) calloc(1,sizeof(tag_t));//给队列结点申请空间if(NULL == tree){tree = pnew;//tree指向树的根结点phead = listpnew;//第一个结点即是队列头,也是队列尾ptail = listpnew;//pcur = listpnew;//pcur要指向要进入树的父亲元素}else{//让元素先入队列ptail -> pnext = listpnew;ptail = listpnew;//接下来把b结点放入树中if(NULL == pcur -> p -> lchild){pcur -> p -> lchild = pnew;//pcur -> p左孩子为空,就放入左孩子}else if(NULL == pcur -> p -> rchild){pcur -> p -> rchild = pnew;//pcur -> p右孩子为空,就放入右孩子pcur = pcur -> pnext;//当前结点左右孩子都有了,pcur就指向下一个}}}return 0;
}

二叉树的前序中序后序遍历

代码

main.cpp文件

#include "function.h"//前序遍历,也叫先序遍历,也是深度优先遍历
void PreOrder(BiTree p){if(p != NULL){printf("%c",p -> c);PreOrder(p -> lchild);//打印左子树PreOrder(p -> rchild);//打印右子树}
}//中序遍历
void InOrder(BiTree p){if(p != NULL){InOrder(p -> lchild);//打印左子树printf("%c",p -> c);InOrder(p -> rchild);//打印右子树}
}//后序遍历
void PostOrder(BiTree p){if(p != NULL){PostOrder(p -> lchild);//打印左子树v(p -> rchild);//打印右子树printf("%c",p -> c);}
}int main(){BiTree pnew;char c;BiTree tree = NULL;ptag_t  phead = NULL,ptail = NULL,listpnew = NULL,pcur;while(scanf("%c",&c)){if(c == '\n'){break;//读到换行就结束}//calloc申请的空间大小是两个参数直接相乘,并对空间进行初始化,赋值为0,头文件#include <stdlib.h>pnew = (BiTree)calloc(1, sizeof(BiNode));pnew -> c = c;listpnew = (ptag_t) calloc(1,sizeof(tag_t));//给队列结点申请空间if(NULL == tree){tree = pnew;//tree指向树的根结点phead = listpnew;//第一个结点即是队列头,也是队列尾ptail = listpnew;//pcur = listpnew;//pcur要指向要进入树的父亲元素}else{//让元素先入队列ptail -> pnext = listpnew;ptail = listpnew;//接下来把b结点放入树中if(NULL == pcur -> p -> lchild){pcur -> p -> lchild = pnew;//pcur -> p左孩子为空,就放入左孩子}else if(NULL == pcur -> p -> rchild){pcur -> p -> rchild = pnew;//pcur -> p右孩子为空,就放入右孩子pcur = pcur -> pnext;//当前结点左右孩子都有了,pcur就指向下一个}}}printf("--------PreOrder--------\n");PreOrder(tree);printf("--------InOrder--------\n");InOrder(tree);printf("--------PostOrder--------\n");PostOrder(tree);return 0;
}

 二叉树的层序遍历

注意:

层序遍历,又称广度优先遍历;而层次遍历中的前序遍历又称深度优先遍历。

项目结构

function.h文件

#ifndef LEARN_FUNCTION_H
#define LEARN_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>
typedef char BiElemType;
typedef struct BiNode{BiElemType c;struct BiNode *lchild;struct BiNode *rchild;
}BiNode, *BiTree;//tag结构体是辅助队列使用的
typedef struct tag{BiTree p;//树的某一个结点的地址值struct tag *pnext;
}tag_t, *ptag_t;//队列的结构体
typedef int ElenType;
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkNode;
typedef struct{LinkNode *front,*rear;//链表头,链表尾,也可以称为对头,队尾
}LinkQueue;//先进先出void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkNode &Q,ElemType x);
bool DeQueue(LinkNode &Q,E;emType &x);#endif //LEARN_FUNCTION_H

CMakeList.txt文件

里面的内容自动生成

queue.cpp文件

#include "function.h"//初始化队列
void InitQueue(LinkQueue &Q){Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//头和尾指向同一个结点Q.front -> next = NULL;//头结点的next指针为NULL
}//判断队列是否为空
bool IsEmpty(LinkNode Q){return Q.rear == Q.front;
}//入队
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *pnew = (LinkNode*) malloc(sizeof(LinkNode));pnew -> data = x;pnew -> next =NULL;//要让next为NULL;Q.rear -> next = pnew;//尾指针的next指向pnew,因为从尾部入队Q.rear = pnew;//rear要指向新的尾部
}bool DeQueue(LinkQueue &Q,ElemType &x){if(Q.rear == Q.front){//队列为空return false;}LinkNode* q = Q.front -> next;//拿到第一个结点,存入qx = q -> data;//获取要出对的元素值Q.front -> next = q->next;//让第一个结点断链if(Q.rear == q){//链表只剩余一个结点时,被删除后,要改变rearQ.rear = Q.front;}free(q);return true;
}

main.cpp文件

#include "function.h"//层次遍历,层序遍历,广度优先遍历
void LevelOrder(BiTree T){LinkQueue Q;//辅助队列InitQueue(Q);//初始化队列BiTree p;EnQueue(Q,T);//树根入队while(!IsEmpty(Q)){DeQueue(Q,p);//出队当前结点并打印putchar(p->c);if(p->lchild!=NULL){//入队左孩子EnQueue(Q,p->lchild);}if(p->rchild!=NULL){ //入队右孩子EnQueue(Q,p->rchild);}}
}//层次建树
int main(){BiTree pnew;//用来指向新申请的树结点char c;BiTree tree=NULL;//树根//phead 就是队列头,ptail 就是队列尾ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;//输入内容为 abcdefghijwhile(scanf("%c",&c)){if(c=='\n'){break;}pnew=(BiTree)calloc(1,sizeof(BiTNode));//calloc 申请空间并对空间进行初始化,赋值为 0pnew->c=c;//数据放进去listpnew=(ptag_t)calloc(1,sizeof(tag_t));//给队列结点申请空间listpnew->p=pnew;if(NULL==tree){tree=pnew;//树的根phead=listpnew;//队列头ptail=listpnew;//队列尾pcur=listpnew;continue;}else{ptail->pnext=listpnew;//新结点放入链表,通过尾插法ptail=listpnew;//ptail 指向队列尾部}//pcur 始终指向要插入的结点的位置if(NULL==pcur->p->lchild)//如何把新结点放入树{pcur->p->lchild=pnew;//把新结点放到要插入结点的左边}else if(NULL==pcur->p->rchild){pcur->p->rchild=pnew;//把新结点放到要插入结点的右边pcur=pcur->pnext;//左右都放了结点后,pcur 指向队列的下一个}}PostOrder(tree);printf("\n--------层次遍历-----------\n");LevelOrder(tree);printf("\n");return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vs用msys2编译安装 gmp

1 下载 1.1下载MSYS2工具 MSYS2 1.2 下载gmp The GNU MP Bignum Library 2 使用windows的msys2命令窗口,有三个msys2命名窗口 mingw64 3 4 命令 pacman -Syu 重启&#xff1a; pacman -Su 安装&#xff1a; pacman -S mingw-w64-x86_64-gcc pacman -S mingw-w64-x86_64-make…

8个简约精美的WordPress外贸网站主题模板

Simplify WordPress外贸网站模板 Simplify WordPress外贸网站模板&#xff0c;简洁实用的外贸公司wordpress外贸建站模板。 查看演示 Invisible Trade WP外贸网站模板 WordPress Invisible Trade外贸网站模板&#xff0c;做进出口贸易公司官网的wordpress网站模板。 查看演…

政安晨:政安晨:机器学习快速入门(三){pandas与scikit-learn} {模型验证及欠拟合与过拟合}

这一篇中&#xff0c;咱们使用Pandas与Scikit-liarn工具进行一下模型验证&#xff0c;之后再顺势了解一些过拟合与欠拟合&#xff0c;这是您逐渐深入机器学习的开始&#xff01; 模型验证 评估您的模型性能&#xff0c;以便测试和比较其他选择。 在上一篇中&#xff0c;您已经…

【stomp实战】websocket原理解析与简单使用

一、WebSocket 原理 WebSocket是HTML5提供的一种浏览器与服务器进行全双工通讯的网络技术&#xff0c;属于应用层协议。它基于TCP传输协议&#xff0c;并复用HTTP的握手通道。浏览器和服务器只需要完成一次握手&#xff0c;两者之间就直接可以创建持久性的连接&#xff0c; 并…

解决计算机“缺失ffmpeg.dll”报错?修复ffmpeg.dll文件方案

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“ffmpeg.dll丢失”。ffmpeg.dll是FFmpeg多媒体框架中的一个重要组件&#xff0c;它负责处理音频和视频的编解码。当打开某些软件时&#xff0c;如果系统找不到该文件&#xff0c;就会出现这…

Rust开发WASM,浏览器运行WASM

首先需要安装wasm-pack cargo install wasm-pack 使用cargo创建工程 cargo new --lib mywasm 编辑Cargo.toml文件&#xff0c;修改lib的类型为cdylib&#xff0c;并且添加依赖wasm-bindgen [package] name "mywasm" version "0.1.0" edition "…

51 -25 Scene as Occupancy 3D占用作为场景表示 论文精读

本文阅读的文章是Scene as Occupancy&#xff0c;介绍了一种将物体表示为3D occupancy的新方法&#xff0c;以描述三维场景&#xff0c;并用于检测、分割和规划。 文章提出了OccNet和OpenOcc两个核心概念。 OccNet 3D占用网络是一种以多视图视觉为中心的方法&#xff0c;通过…

第 383 场 LeetCode 周赛题解

A 边界上的蚂蚁 模拟 class Solution { public:int returnToBoundaryCount(vector<int> &nums) {int s 0;int res 0;for (auto x: nums) {s x;if (s 0)res;}return res;} };B 将单词恢复初始状态所需的最短时间 I 枚举&#xff1a;若经过 i i i 秒后 w o r d w…

ubuntu22.04安装部署03: 设置root密码

一、前言 ubuntu22.04 安装完成以后&#xff0c;默认root用户是没有设置密码的&#xff0c;需要手动设置。具体的设置过程如下文内容所示&#xff1a; 相关文件&#xff1a; 《ubuntu22.04装部署01&#xff1a;禁用内核更新》 《ubuntu22.04装部署02&#xff1a;禁用显卡更…

【语音合成】中文-多情感领域-16k-多发音人

模型介绍 语音合成-中文-多情感领域-16k-多发音人 框架描述 拼接法和参数法是两种Text-To-Speech(TTS)技术路线。近年来参数TTS系统获得了广泛的应用&#xff0c;故此处仅涉及参数法。 参数TTS系统可分为两大模块&#xff1a;前端和后端。 前端包含文本正则、分词、多音字预…

回归预测 | Matlab实现ABC-BP人工蜂群算法优化BP神经网络多变量回归预测

回归预测 | Matlab实现ABC-BP人工蜂群算法优化BP神经网络多变量回归预测 目录 回归预测 | Matlab实现ABC-BP人工蜂群算法优化BP神经网络多变量回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab实现ABC-BP人工蜂群算法优化BP神经网络多变量回归预测&#x…

React+Antd实现表格自动向上滚动

1、效果 2、环境 1、react18 2、antd 4 3、代码实现 原理&#xff1a;创建一个定时器&#xff0c;修改表格ant-table-body的scrollTop属性实现滚动&#xff0c;监听表层的元素div的鼠标移入和移出实现实现鼠标进入元素滚动暂停&#xff0c;移出元素的时候表格滚动继续。 一…

Spring基础 - Spring简单例子引入Spring要点

Spring基础 - Spring简单例子引入Spring要点 设计一个Spring的Hello World 设计一个查询用户的案例的两个需求&#xff0c;来看Spring框架帮我们简化了什么开发工作 pom依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"htt…

vue3 之 商城项目—登陆

整体认识 登陆页面的主要功能就是表单校验和登陆登出业务 路由配置 模版 <script setup></script><template><div><header class"login-header"><div class"container m-top-20"><h1 class"logo"&g…

第1节、电路连接【51单片机+L298N步进电机系列】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;本节介绍如何搭建一个51单片机L298N步进电机控制电路&#xff0c;所用材料均为常见的模块&#xff0c;简单高效的方式搭建起硬件环境。 一、硬件清单 ①51单片机模块 ②恒流模块 ③开关电源 ④L298N模…

2024-02-08 Unity 编辑器开发之编辑器拓展1 —— 自定义菜单栏与窗口

文章目录 1 特殊文件夹 Editor2 在 Unity 菜单栏中添加自定义页签3 在 Hierarchy 窗口中添加自定义页签4 在 Project 窗口中添加自定义页签5 在菜单栏的 Component 菜单添加脚本6 在 Inspector 为脚本右键添加菜单7 加入快捷键8 小结 1 特殊文件夹 Editor ​ Editor 文件夹是 …

MYSQL笔记:约束条件

MYSQL笔记&#xff1a;约束条件 主键约束 不能为空&#xff0c;值必须是不同的&#xff08;唯一性&#xff09; 一个表只能修饰一个主键 PRIMARY KEY自增约束 AUTO_INCREMENT唯一键约束 可以为空 unique非空约束 not null 默认值约束 default 外键约束 foreign key …

代码随想录|Day 14

Day 14 新年将至 一、理论学习 BFS 的使用场景总结&#xff1a;层序遍历、最短路径问题(https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/244853/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/) BFS 的应用一&#xff1a;层序遍历 BFS …

详述FlinkSql Join操作

FlinkSql 的 Join Flink 官网将其分为了 Joins 和 Window Joins两个大类&#xff0c;其中里面又分了很多 Join 方式 参考文档&#xff1a; Joins | Apache Flink Window JOIN | Apache Flink Joins 官网介绍共有6种方式&#xff1a; Regular Join&#xff1a;流与流的 Joi…

开发JSP应用程序

开发JSP应用程序 问题陈述 TecknoSoft Pvt Ltd.公司的首席技术官(CTO)John Barrett将创建一个应用程序的任务委托给了开发团队,该应用程序应在客户访问其账户详细信息前验证其客户ID和密码。客户ID应是数字形式。John希望如果所输入的客户ID或密码不正确,应向客户显示错误…