数据结构-二叉树

一.二叉树的定义

二叉树有左右儿子之分

完美二叉树(满二叉树)除了最下面的没有儿子其他结点都有两个儿子,叶节点比较齐的,完全二叉树不是满二叉数允许缺失最后的结点

满二叉树可以达到2^k-1

边的总数=节点数-1

二.二叉树的存储结构

三.二叉树的遍历

前序遍历中序遍历后续遍历,结点所走的路径相同

#include<iostream>
using namespace std;
typedef int ElementType;
typedef struct TNode* Position;typedef Position BinTree;
typedef BinTree Element;
typedef struct TNode{ElementType Data;BinTree L;BinTree R;
};
typedef struct SNode* Stakc;
typedef struct SNode {Element *Data;int MaxSize;int top;
};
typedef struct QNode* Queue;
typedef struct QNode {Element* Data;int MaSize;int front;int back;
};
Queue Crq(int MaxSize) {Queue q = new QNode();q->Data = new Element[MaxSize];q->front = q->back = -1;q->MaSize = MaxSize;return q;
}
bool IsEmptyq(Queue q) {return q->front == q->back;
}
bool IsFullq(Queue q) {return q->front == q->back + 1;
}
void Pushq(Queue q,Element BT) {if (IsFullq(q)) {cout << "队列已满" << endl;return;}q->back = (q->back + 1) % q->MaSize;q->Data[q->back] = BT;
}
Element Delete(Queue q) {if (IsEmptyq(q)) {return NULL;}q->front = (q->front + 1) % q->MaSize;return q->Data[q->front];
}
Stakc Cr(int MaxSize) {Stakc s = new SNode();s->Data = new Element[MaxSize];s->MaxSize = MaxSize;s->top = -1;return s;
}
bool IsFull(Stakc s) {return s->MaxSize == s->top - 1;
}
bool IsEmpty(Stakc s) {return s->top == -1;
}
void Push(Stakc s, BinTree BT) {if (IsFull(s)) {cout << "堆栈已满无法插入" << endl;return;}s->Data[++s->top] = BT;
}
Element Pop(Stakc s) {if (IsEmpty(s)) {return NULL;}return s->Data[s->top--];
}
//二叉树插入
void insertTree(BinTree zs, ElementType num,int x ) {//x==0左插x==1右插BinTree ss,node;ss = zs;node = new TNode();node->Data = num;node->L = node->R = NULL;if (x == 0) {while (ss->L) {ss= ss->L;}ss->L = node;}else {while (ss->R) {ss = ss->R;}ss->R = node;}
}
//递归中序遍历
void InorderTraversal(BinTree BT)
{if (BT) {InorderTraversal(BT->L);/* 此处假设对BT结点的访问就是打印数据 */printf("%d ", BT->Data); /* 假设数据为整型 */InorderTraversal(BT->R);}
}
//递归前序遍历
void InorderTravers(BinTree BT) {if (BT) {cout << BT->Data<<" ";InorderTravers(BT->L);InorderTravers(BT->R);}
}
//递归后续遍历
void InorderH(BinTree BT) {if (BT) {InorderH(BT->L);InorderH(BT -> R);cout << BT->Data << " ";}
}
//非递归中序遍历
void fdgz(BinTree BT) {Stakc s = Cr(100);BinTree T = BT;while (T || !IsEmpty(s) ){while (T) {Push(s, T);T = T->L;}if (!IsEmpty(s)) {T = Pop(s);cout << T->Data << " ";T = T->R;}}
}
//非递归前序遍历
void fdgq(BinTree BT) {Stakc s = Cr(100);BinTree T = BT;while (T || !IsEmpty(s)) {while (T) {cout << T->Data << " ";Push(s, T);T = T->L;}if (!IsEmpty(s)) {T = Pop(s);T = T->R;}}
}
//非递归后续遍历(待实现)
void fdgh(BinTree BT) {Stakc s = Cr(100);BinTree T = BT;while (T || !IsEmpty(s)) {while (T) {Push(s, T);T = T->L;}if (!IsEmpty(s)) {T = Pop(s);cout << T->Data << " ";T = T->R;Push(s, T);}}
}
//层序遍历
void cencibanli(BinTree BT) {BinTree T = BT;Queue q = Crq(100);if (T == NULL)return;Pushq(q, T);while (!IsEmptyq(q)) {T = Delete(q);cout << T->Data << " ";if (T->L)Pushq(q, T->L);if (T->R)Pushq(q, T->R);}
}
//求叶子节点
void leaf(BinTree BT) {BinTree T = BT;if (T) {if (!T->L && !T->R)cout << T->Data << " ";leaf(T->L);leaf(T->R);}
}
//求树的高度
int treehigt(BinTree BT) {int HL, HR, MAXH;BinTree T = BT;if (T) {HL = treehigt(T->L);HR = treehigt(T->R);MAXH = max(HL, HR);return (MAXH + 1);}elsereturn 0;
}
int main()
{int x = 0;BinTree t1 = new TNode();t1->Data = 1;t1->R = t1->L = NULL;for (int i = 2; i <= 10; i++){insertTree(t1, i,x);x = ~x;}cout <<  "中序遍历";InorderTraversal(t1);cout << endl;cout << "前序遍历";InorderTravers(t1);cout << endl;cout << "后续遍历";InorderH(t1);cout << endl;cout << "层次遍历";cencibanli(t1);cout << endl;cout << "叶子结点:";leaf(t1);cout << endl;cout << "树的高度";cout << treehigt(t1) << endl;;system("pause");return 0;}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

OKR制定指南

Goal Crafting 目标制定是最基本的领导活动之一。组织绩效和团队成长依赖于精心制定的目标。没有良好的目标制定练习&#xff0c;团队可能只关注眼前的事务&#xff0c;解决看似可以快速解决的问题。良好的目标制定迫使你不忽视或推迟那些需要新思维方式、合作或克服困难的问题…

详细分析Java中FilterChain过滤器的基本知识

目录 前言1. 基本知识2. Demo 前言 基本的Java知识推荐阅读&#xff1a; java框架 零基础从入门到精通的学习路线 附开源项目面经等&#xff08;超全&#xff09;【Java项目】实战CRUD的功能整理&#xff08;持续更新&#xff09; 从实战中学习&#xff1a; 常用在一些重复代…

TableGPT2-7B:用于表格数据分析的大规模解码器模型

TableGPT2-7B 是浙江大学开发的最先进的大规模解码器模型&#xff0c;专为涉及表格数据的数据密集型任务而设计。该模型以 Qwen2.5 架构为基础&#xff0c;包括针对表格数据的专用编码&#xff0c;其中独特的语义编码器可从行、列和整个表格中获取洞察力。 主要特点和功能 Ta…

SQL面试题——抖音SQL面试题 主播播出时长

主播播出时长 现有如下数据,主播id、房间号、播出的批次号,每个批次号进出房间的时间戳、分区时间: 每一次直播都有一个上播和下播,每个房间里,同一个批次号会有两条数据,分别记录了上播和下播时间,求每个主播的播出时长? 通过上面的数据,可以清晰的看出,同一个批次…

数字信号处理Python示例(14)生成锯齿波和三角波

文章目录 前言一、锯齿波和三角波二、生成锯齿波和三角波的Python代码三、仿真结果及分析写在后面的话 前言 因其独特的数学特性和物理表现&#xff0c;在工程和技术领域扮演着重要角色。这是生成非正弦信号的几个Python示例的其中一个&#xff0c;生成三角波与锯齿波&#xf…

HBase理论_HBase架构组件介绍

近来有些空闲时间&#xff0c;正好最近也在开发HBase相关内容&#xff0c;借此整理一下学习和对HBase组件的架构的记录和个人感受&#xff0c;付出了老夫不少心血啊&#xff0c;主要介绍的就是HBase的架构设计以及我的拓展内容。内容如有不当或有其他理解 matirx70163.com HB…

前端快速上手(一):HTML

目录 1. HTML 基础 1.1 HTML 标签 1.2 标签的结构关系 2. HTML 常见标签 2.1 标题标签: h1 - h6 2.2 段落标签: p 2.3 换行标签: br 2.4 图片标签: img 2.5 超链接: a 标签 2.5.1 外部链接 2.5.2 内部链接 2.5.3 文件资源链接 2.5.4 空链接 2.6 表格标签 2.7 表单…

QT<30> Qt中使鼠标变为转圈忙状态

前言&#xff1a;当我们在写软件时&#xff0c;在等待阻塞耗时操作时可以将鼠标变为忙状态&#xff0c;并在一段时间后恢复状态&#xff0c;可以用到GxtWaitCursor&#xff1a;Qt下基于RAII的鼠标等待光标类。 一、效果演示 二、详细代码 在项目中添加C文件&#xff0c;命名为…

Shell环境导致编译失败处理方法

在嵌入式Linux系统源码&#xff08;BSP包&#xff09;编译时&#xff0c;有可能会如现如下提示&#xff1a; [[: not found 这种提示&#xff0c;一般是Shell环境为dash而不是bash导致&#xff0c;可以通过如下命令来切换&#xff1a; sudo dpkg-reconfigure dash 执行后会…

nginx openresty lua-resty-http 使用的一些问题记录

需求背景 需求是使用 nginx 做一个 https 服务的代理 nginx 收到 http 请求后&#xff0c;需要修改 body 中的某些参数值&#xff0c;然后将修改后的数据发送到目标服务器&#xff08;https&#xff09; 本来以为很简单的需求&#xff0c;结果中间出现了不少岔子&#xff0c;这…

Redis的分布式锁分析

系列文章目录 Java项目对接redis&#xff0c;客户端是选Redisson、Lettuce还是Jedis&#xff1f; 由Redis引发的分布式锁探讨 系列文章目录一、什么是分布式锁&#xff1f;二、Redis分布式锁的几种实现1. 简单分布式锁2. Redlock 三、Redis 锁的问题1. 互斥失效2. 时钟偏移 四…

柯桥生活英语口语学习“面坨了”英语怎么表达?

“面坨了”英语怎么表达&#xff1f; 要想搞清楚这个表达&#xff0c;首先&#xff0c;我们要搞明白“坨”是啥意思&#xff1f; 所谓“坨”就是指&#xff0c;面条在汤里泡太久&#xff0c;从而变涨&#xff0c;黏糊凝固在一起的状态。 有一个词汇&#xff0c;很适合用来表达这…

鸿蒙NEXT应用示例:切换图片动画

【引言】 在鸿蒙NEXT应用开发中&#xff0c;实现图片切换动画是一项常见的需求。本文将介绍如何使用鸿蒙应用框架中的组件和动画功能&#xff0c;实现不同类型的图片切换动画效果。 【环境准备】 电脑系统&#xff1a;windows 10 开发工具&#xff1a;DevEco Studio NEXT B…

UAC2.0 speaker——speaker 数据传输

文章目录 麦克风数据传输准备音频数据抓包原始数据频谱分析(FFT)应用麦克风数据传输 上一节中实现了 USB 麦克风设备 本节主要介绍 MCU 麦克风的数据如何传输给上位机。 准备音频数据 MCU 端发送 48KHZ, 16bit 单声道的正弦波数据,正弦波数据的生成参考 音频——C语言生…

【多语言】每种语言打印helloworld,编译为exe会占多大空间

文章目录 背景c语言 53KBc 53KBgo 1.8Mdart 4.6Mpython未测试nodejs未测试rust未测试java未测试cmd || bash || powershell 未测试other 背景 各个版本的helloworld&#xff0c;纯属闲的, 环境如下: - win10 - mingw: gcc8.1.0 - go1.21 - dart3.5.4c语言 53KB gcc main.c -…

Android12的ANR解析

0. 参考&#xff1a; ANR分析 深入理解 Android ANR 触发原理以及信息收集过程 1.ANR的触发分类: ANR分为4类&#xff1a; InputDispatchTimeout&#xff1a;输入事件分发超时5s,包括按键和触摸事件。BroadcastTimeout&#xff1a;比如前台广播在10s内未执行完成&#xff0…

2022-2023全国高校计算机能力挑战赛区域赛python组编程题

mi目录 2022 1. 2. 1. 使用 format() 方法 2. 使用 f-string&#xff08;Python 3.6 及以上&#xff09; 2023 1. 2. 3. 4 闽农大宝玲楼 2022 1. 1.某动物研究员给动物园的动物们定了一个园区幸福值&#xff0c;其中园区幸福值的计算为一个园区内“所有动物的活动时…

函数的栈帧

前言&#xff1a; 1.请使用vs2013调试&#xff0c;我使用vs2019被恶心到了&#xff0c;封装严重&#xff0c;不利于观察。 2.函数栈帧&#xff1a;函数就是程序&#xff0c;程序就需要空间来运行&#xff0c;所以我们要为他分配空间&#xff0c;分配的空间用ebp esp维护&…

机器学习基础04

目录 1.朴素贝叶斯-分类 1.1贝叶斯分类理论 1.2条件概率 1.3全概率公式 1.4贝叶斯推断 1.5朴素贝叶斯推断 1.6拉普拉斯平滑系数 1.7API 2.决策树-分类 2.1决策树 2.2基于信息增益的决策树建立 2.2.1信息熵 2.2.2信息增益 2.2.3信息增益决策树建立步骤 2.3基于基…

如何解决IDE添加错误GitHub token后无法连接GitHub的问题

背景 当初学者首次使用IDE&#xff08;IDEA、Xcode等&#xff09;对GitHub仓库进行操作&#xff08;push、fetch&#xff09;时&#xff0c;会提示输入GitHub账户和token&#xff0c;如果这时候你一不小心输入了错误的token&#xff0c;之后你就叫天天不应叫地地不灵了&#xf…