#数据结构 笔记三

二叉树

1. 概念

二叉树Binary Treen个结点的有限集合。它或者是空集n=0,或者是由一个根结点以及两颗互不相交、分别称为左子树和右子树的二叉树组成。

二叉树与普通有序树不同,二叉树严格区分左子和右子,即使只有一个子结点也要区分左右。

二叉树的树度数最大为2

2. 性质*

关于树的一些基本念

(1)度数:一个节点的子树的个数(一个节点的子树的个数称为该节点的度数,3)

(2)树度数:树中节点的最大度数

(3)叶节点或终端节点: 度数为零的节点

(4)分支节点:度数不为零的节点(B一层)

(5)内部节点:除根节点以外的分支节点 (B,C,D)

(6)节点层次: 根节点的层次为1,根节点子树的根为第2层,以此类推

(7)树的深度或高度: 树中所有节点层次的最大值 (4)

  1. 二叉树的第k层上的结点最多个2k-1
  2. 深度为k的二叉树最多有2k-1个结点

Sn=a1(1-qn)/(1-q)=a1(1-2k)/(1-2)=(1-2k)/-1=2k-1

  1. 在任意一颗二叉树中,树叶的数目比度数为2的结点数目多1

N:结点的总数

N0:没有子结点的结点个数

N1:只有一个子结点的结点个数

N2:有两个子结点的结点个数

总结点 = 各节点数目之和 N = N0 + N1 + N2

总结点 = 所有子节点 + 根 N = 0 × N0 + 1 × N1 + 2 × N2 + 1

联立以上两式可得: N0 = N2 + 1

(网易)一棵二叉树有8个度为2的节点,5个度为1的节点,那么度为0的节点个数为 ( 9 )

满二叉树和完全二叉树

满二叉树:深度为k(k>=1)时,第k层结点个数为2k-1

完全二叉树:只有最下面两层有度数小于2的节点,且最下面一层的结点集中在最左边的若干位置上。

3. 实现

二叉树的存储结构有两种,分为顺序存储和链式存储

3.1. 顺序存储

二叉树的顺序存储,指的是使用顺序表(数组)存储二叉树。需要注意,顺序存储只适用于完全二叉树。换句话说,只有完全二叉树才可以用顺序表存储。因此,如果我们想要顺序存储普通二叉树,就需要将其提前转换成完全二叉树。

普通二叉树转完全二叉树的方法很简单,只需给二叉树额外添加一些结点,将其"拼凑"成一个完全二叉树即可。

如图所示:

左侧是普通二叉树,右侧是转化后的完全(满)二叉树。

完全(满)二叉树的顺序存储,仅需要从根结点开始,按照层次依次将树中结点存储到数组即可。

存储图 2 所示的完全二叉树:

存储由普通二叉树转化来的完全二叉树也是如此。

图 1 中普通二叉树在顺组中的存储状态如图:

完全二叉树中结点按照层次并从左到右依次编号(123...),若结点i有左子,则其左子的结点编号为2*i,右子编号为2*i+1

设完全二叉树的结点数为n,某结点的编号为i

i>1时(不是根结点时),有父节点,其编号为i/2

2*i <= n时,有左子,其编号为2*i,否则没有左子,没左子一定没右子,其本身为叶节点。

2*i+1 <= n时,有右子,其编号为2*i+1,否则就没有右子。

3.1.1. 遍历*

先序:根----->左----->右

A B D H I E J C F K G

中序:左----->根----->右

H D I B E J A F K C G

后序:左----->右----->根

H I D J E B K F G C A

已知遍历结果如下,试画出对应的二叉树,写出后续:

先序:A B C E H F I J D G K 根----->左----->右

中序:A H E C I F J B D K G 左----->根----->右

因为先序是根在最前面的,所以在先序中从前往后地取结点拿到中序中作为根,循环重复。

3.2. 链式存储

链式存储此二叉树,从根结点开始,将各个结点以及其左右子的地址使用链表进行存储。

3.2.1. 定义操作完全二叉树结构体*

结点结构体由三部分组成:

  1. 指向左子结点的指针(Lchild)
  2. 结点存储的数据(结点编号)
  3. 指向右子结点的指针(Rchild)

// 1. 定义操作二叉树的结构体
typedef char datatype_tree;
typedef struct tree_node_t
{datatype_tree data;//数据域struct tree_node_t *lchild;//左子left struct tree_node_t *rchild;//右子right 
}bitree_node_t,*bitree_list_t;

3.2.2. 创建二叉树*

#include "bitree.h"// 2. 创建二叉树
// 主函数传参 n 树中结点总数; i 结点编号(从1开始)
bitree_list_t CreateBitree(int n,int i)
{// 2.1 开辟空间存放结构体bitree_list_t r = (bitree_list_t)malloc(sizeof(bitree_node_t));if(NULL == r){printf("CreateBitree malloc failed\n");return NULL;}// 2.2 初始化结构体成员// 2.3 判断有无左右子// 2.3.1 有左子r->data = i;if(2 * i <= n){r->lchild = CreateBitree(n,2*i);}// 2.3.2 无左子else{r->lchild = NULL;}// 2.3.3 有右子if(2*i + 1 <= n){r->rchild = CreateBitree(n,2*i+1);}// 2.3.4 无右子else{r->rchild = NULL;}return r;
}#include "bitree.h"
int main(int argc, const char *argv[])
{bitree_node_t *r = CreateBitree(3,1);return 0;
}

3.2.3. 先序遍历*

//前序
// 3. 先序遍历二叉树
// 根——左——右
void PreOrder(bitree_list_t r)
{if(NULL == r)return;printf("%d ",r->data);							 // 根// 如果有左子,则将左子作为根将该函数的全部操作走一遍if(r->lchild != NULL)							 // 左PreOrder(r->lchild);
// 如果有右子,则将右子作为根将该函数的全部操作走一遍if(r->rchild != NULL)PreOrder(r->rchild);						 // 右
}

3.2.4. 中序遍历

// 4. 中序遍历
// 左——根——右
void InOrder(bitree_list_t r)
{if(NULL == r)return;// 如果有左子,则将左子作为根将该函数的全部操作走一遍if(r->lchild != NULL)								 // 左InOrder(r->lchild);printf("%d ",r->data);								 // 根// 如果有右子,则将右子作为根将该函数的全部操作走一遍if(r->rchild != NULL)InOrder(r->rchild);									 // 右
}

3.2.5. 后序遍历

// 5. 后序遍历
// 左——右——根
void PostOrder(bitree_list_t r)
{if(NULL == r)return;// 如果有左子,则将左子作为根将该函数的全部操作走一遍if (r->lchild != NULL)                           // 左PostOrder(r->lchild);// 如果有右子,则将右子作为根将该函数的全部操作走一遍if (r->rchild != NULL)                           // 右PostOrder(r->rchild);printf("%d\t", r->data);                         // 根
}

总结:

#include "bitree.h"
bitree_list_t CreateBitree(int n,int i)
{bitree_list_t r = (bitree_list_t)malloc(sizeof(bitree_node_t));if(NULL == r){printf("CreateBitree malloc failed\n");return NULL;}r->data = i;if(2 * i <= n){r->lchild = CreateBitree(n,2*i);}else{r->lchild = NULL;}if(2*i + 1 <= n){r->rchild = CreateBitree(n,2*i+1);}else{r->rchild = NULL;}return r;
}
//前序
void PreOrder(bitree_list_t r)
{if(NULL == r)return;printf("%d ",r->data);if(r->lchild != NULL)PreOrder(r->lchild);if(r->rchild != NULL)PreOrder(r->rchild);
}
//中序
void InOrder(bitree_list_t r)
{if(NULL == r)return;if(r->lchild != NULL)InOrder(r->lchild);printf("%d ",r->data);if(r->rchild != NULL)InOrder(r->rchild);
}
//后序
void PostOrder(bitree_list_t r)
{if(NULL == r)return;if(r->lchild != NULL)PostOrder(r->lchild);if(r->rchild != NULL)PostOrder(r->rchild);printf("%d ",r->data);}
#include "bitree.h"
int main(int argc, const char *argv[])
{	bitree_node_t *r = CreateBitree(3,1);PreOrder(r);	printf("\n");InOrder(r);printf("\n");PostOrder(r);printf("\n");return 0;
}
#ifndef _BITREE_H_
#define _BITREE_H_
#include <stdio.h>
#include <stdlib.h>
typedef char datatype_tree;
typedef struct tree_node_t
{datatype_tree data;//数据域struct tree_node_t *lchild;//左子left struct tree_node_t *rchild;//右子right 
}bitree_node_t,*bitree_list_t;
bitree_list_t CreateBitree(int n,int i);
//前序
void PreOrder(bitree_list_t r);
//中序
void InOrder(bitree_list_t r);
//后序
void PostOrder(bitree_list_t r);
//层次
void unOrder(bitree_list_t r);
#endif	

3.2.6. 层序遍历

队列的思想

不需要敲代码,看懂就行

示意图

#ifndef _BITREE_H_
#define _BITREE_H_
typedef char datatype_tree;
typedef struct tree_node_t
{datatype_tree data;//数据域 struct tree_node_t *lchild;//左子指针struct tree_node_t *rchild;//右子指针
}bitree_t;
//前序遍历
void preOrder(bitree_t *r);//r二叉树根节点的指针
//中序遍历
void inOrder(bitree_t * r);
//后序遍历
void postOrder(bitree_t *r);
//遍历二叉树 
//s 代表的是打印提示, void (*p)(bitree_t *)函数指针  r遍历的树
void showBitree(char *s,void (*p)(bitree_t *),bitree_t *r);
//创建二叉树,用递归函数创建
bitree_t *createBitree();
//层次遍历
void unOrder(bitree_t *r);
#endif
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_#include "bitree.h"//将 bitree_t * 改名 为datatype_linkqueue 
typedef bitree_t * datatype_linkqueue;//把队列的数据域变成指向树节点的指针
typedef struct node
{datatype_linkqueue data;//数据域struct node *next;//指针域
}linkqueue_node_t,*linkqueue_list_t;//linkqueue_list_t p === linkqueue_node_t *
typedef struct//将队列头指针和尾指针封装到一个结构体里
{linkqueue_list_t front;//相当于队列的头指针linkqueue_list_t rear;//相当于队列的尾指针//有了链表的头指针和尾指针,那么我们就可以操作这个链表
}linkqueue_t;//1.创建一个空的队列
linkqueue_t *createEmptyLinkQueue();
//2.入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p,datatype_linkqueue data);
//3.出列 
datatype_linkqueue outLinkQueue(linkqueue_t *p);
//4.判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p);
//5.求队列长度的函数
int lengthLinkQueue(linkqueue_t *p);
//6.清空队列
void clearLinkQueue(linkqueue_t *p);
#endif
#include "bitree.h"
#include "linkqueue.h"
#include <stdio.h>
#include <stdlib.h>
//前序遍历
void preOrder(bitree_t *r)//r二叉树根节点的指针
{if(r == NULL)//递归函数的结束条件return;printf("%c ",r->data);//根preOrder(r->lchild);//左preOrder(r->rchild);//右
}
//中序遍历
void inOrder(bitree_t * r)
{if(r == NULL)//递归的结束条件return;inOrder(r->lchild);//左printf("%c ",r->data);//根inOrder(r->rchild);//右
}
//后序遍历
void postOrder(bitree_t *r)
{if(r == NULL)//递归函数的结束条件return;postOrder(r->lchild);//左postOrder(r->rchild);//右printf("%c ",r->data);//根
}
//遍历二叉树 
//s 代表的是打印提示, void (*p)(bitree_t *)函数指针  r遍历的树
void showBitree(char *s,void (*p)(bitree_t *),bitree_t *r)
{printf("%s",s);p(r);printf("\n");
}
//创建二叉树,用递归函数创建
bitree_t *createBitree()
{//root 
//	ABD###CE##F##bitree_t *r = NULL;//用来保存二叉树的根节点char ch;scanf("%c",&ch);if(ch == '#')//输入是'#',代表没有左子或右子return NULL;r = (bitree_t *)malloc(sizeof(bitree_t));if(NULL == r){perror("r malloc failed");return NULL;}r->data = ch;r->lchild = createBitree();r->rchild = createBitree();return r;
}//层次遍历
void unOrder(bitree_t *r)
{//1.创建一个队列,队列的数据域变成指向树节点的指针linkqueue_t *p = createEmptyLinkQueue();if(r != NULL)inLinkQueue(p,r);//2.循环打印while(!isEmptyLinkQueue(p)){r = outLinkQueue(p);printf("%c ",r->data);if(r->lchild != NULL)//只要左子不为空,就入列,之后出列的时候打印inLinkQueue(p,r->lchild);if(r->rchild != NULL)//只要右子不为空,就入列,之后出列的时候打印inLinkQueue(p,r->rchild);}
}
#include "linkqueue.h"
#include <stdio.h>
#include <stdlib.h>//1.创建一个空的队列
linkqueue_t *createEmptyLinkQueue()
{linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));if(NULL == p){perror("createEmptyLinkQueue p malloc failed");return NULL;}//申请空间就是为了装东西//申请链表的头节点空间,让rear和front都指向头结点p->front = p->rear = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if(NULL == p->rear){perror("p->rear malloc failed");return NULL;}p->rear->next = NULL;//或者用p->front->next = NULL;因为p->rear 和 p->front 指向同一个位置即头节点return p;
}
//2.入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p,datatype_linkqueue data)
{//1.创建一个新的节点,用来保存即将插入的数据linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if(NULL == pnew){perror("inLinkQueue pnew malloc failed");return -1;}//2.将入列的数据放入到新的节点中pnew->data = data;pnew->next = NULL;//3.将新节点链链接到链表的尾巴p->rear->next = pnew;//新节点链接到链表的尾p->rear = pnew;//rear移动,因为rear永远指向当前链表的尾return 0;
}
//3.出列 
datatype_linkqueue outLinkQueue(linkqueue_t *p)
{linkqueue_list_t pdel = NULL;//指向被删除的节点//1.容错判断if(isEmptyLinkQueue(p)){printf("isEmptyLinkQueue !!\n");return NULL;}//2.出列数据//(1)定义pdel指向即将被删除的节点就是front指向的节点,出列每次删除的都是front指向的那个节点pdel = p->front;//(2)将front向后移动一个位置p->front = p->front->next;//(3)释放被删除节点free(pdel);pdel = NULL;//(4)将数据出列return p->front->data;
}
//4.判断队列是否为空
int isEmptyLinkQueue(linkqueue_t *p)
{return p->front == p->rear;
}
//5.求队列长度的函数
int lengthLinkQueue(linkqueue_t *p)
{int len = 0;linkqueue_list_t h = p->front;//将链表的头指针保存的地址给h,如果直接用front,求长度之后会找不到链表的头,用h的移动代替front的移动//求长度,相当于遍历有头的单向链表while(h->next != NULL){h = h->next;len++;}return len;
}
//6.清空队列
void clearLinkQueue(linkqueue_t *p)
{while(!isEmptyLinkQueue(p))//只要不为空,就出列outLinkQueue(p);
}
#include "bitree.h"
#include <stdio.h>
#include <stdlib.h>int main(int argc, const char *argv[])
{bitree_t *r = createBitree();showBitree("前序:",preOrder,r);showBitree("中序:",inOrder,r);showBitree("后序:",postOrder,r);showBitree("层次:",unOrder,r);return 0;
}

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

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

相关文章

Spring MVC 中 使用 RESTFul 实现用户管理系统

1. Spring MVC 中 使用 RESTFul 实现用户管理系统 文章目录 1. Spring MVC 中 使用 RESTFul 实现用户管理系统2. 静态页面准备2.1 user.css2.2 user_index.html2.3 user_list.html2.4 user_add.html2.5 user_edit.html 3. SpringMVC环境搭建3.1 创建module&#xff1a;usermgt3…

3个让你爽到爆炸的学习工具

We OCR WeOCR 是一个基于浏览器的文字识别工具&#xff0c;用户可以通过上传图片来识别其中的文本信息。它是一个渐进式网络应用程序&#xff08;PWA&#xff09;&#xff0c;可以在浏览器中离线使用。WeOCR 是开源的&#xff0c;并且基于 Tesseract OCR 引擎开发。用户无需在本…

STM32第十二课:ADC检测烟雾浓度(MQ2)

文章目录 需求一、MQ-2 气体传感器特点应用电路及引脚 二、实现流程1.开时钟&#xff0c;分频&#xff0c;配IO2.配置ADC的工作模式3.配置通道4.复位&#xff0c;AD校准5.数值的获取 需求实现总结 需求 使用ADC将MQ2模块检测到的烟雾浓度模拟量转化为数字量。 最后&#xff0c…

MySQL内存使用率高且不释放问题排查与总结

背景 生产环境mysql 5.7内存占用超过90%以上&#xff0c;且一直下不来。截图如下&#xff1a; 原因分析 1、确定mysql具体的占用内存大小&#xff0c;通过命令&#xff1a;cat /proc/Mysql进程ID/status查看 命令执行后的结果比较多&#xff08;其他参数的含义想了解可参考这…

【Django】网上蛋糕项目商城-首页

概念 本文在上一文章搭建完数据库&#xff0c;以及创建好项目之后&#xff0c;以及前端静态文件后&#xff0c;对项目的首页功能开发。 后端代码编写 在views.py文件中创建方法&#xff0c;连接数据库&#xff0c;并获取首页需要的数据 def getGoodsList(type):# 获取所有横…

Python学生信息管理系统(完整代码)

引言&#xff1a;&#xff08;假装不是一个大学生课设&#xff09;在现代教育管理中&#xff0c;学生管理系统显得尤为重要。这种系统能够帮助教育机构有效地管理学生资料、成绩、出勤以及其他教育相关活动&#xff0c;从而提高管理效率并减少人为错误。通过使用Python&#xf…

Winform使用HttpClient调用WebApi的基本用法

Winform程序调用WebApi的方式有很多&#xff0c;本文学习并记录采用HttpClient调用基于GET、POST请求的WebApi的基本方式。WebApi使用之前编写的检索环境检测数据的接口&#xff0c;如下图所示。 调用基于GET请求的无参数WebApi 创建HttpClient实例后调用GetStringAsync函数获…

什么是单例模式?

前言&#x1f440;~ 上一章我们介绍了多线程下引发的安全问题&#xff0c;今天接着讲解多线程的内容&#xff0c;同样很重要&#xff0c;请细品 单例模式 饿汉模式 懒汉模式 饿汉模式和懒汉模式的区别 再遇线程不安全问题 指令重排序问题 如果各位对文章的内容感兴趣的话…

学习笔记(linux高级编程)11

进程间通信 》信号通信 应用&#xff1a;异步通信。 中断&#xff0c;&#xff0c; 1~64&#xff1b;32应用编程。 如何响应&#xff1a; Term Default action is to terminate the process. Ign Default action is to ignore the signal. wait Core Default action is …

ffmpeg将多个yuv文件编码为MP4视频文件

一、编码方案 在视频录制时&#xff0c;每一帧保存为一个yuv文件&#xff0c;便于纠错和修改。在编码为MP4文件时&#xff0c;我的方案是将所有yuv文件先转码为单个MP4文件&#xff0c;然后使用ffmpeg的concat功能拼接为完整的视频。 二、shell脚本 #!/bin/bash# 检查参数数量…

【Arduino】ESP8266开发环境配置(图文)

ESP8266与ESP32开发很类似&#xff0c;相当于是低配版本的ESP32&#xff0c;其同样具有无线网络连接能力&#xff0c;功能强大&#xff0c;而且价格比ESP32更具有优势。接下来我们就来设置一下ESP8266的开发环境。 使用Arduino开发平台软件&#xff0c;选择首选项进行设置。 h…

【C++】 ——【模板初阶】——基础详解

目录 1. 泛型编程 1.1 泛型编程的概念 1.2 泛型编程的历史与发展 1.3 泛型编程的优势 1.4 泛型编程的挑战 2. 函数模板 2.1 函数模板概念 2.2 函数模板格式 2.3 函数模板的原理 2.4 函数模板的实例化 2.5 模板参数的匹配原则 2.6 函数模板的特化 2.7 函数模板的使…

事务底层与高可用原理

1.事务底层与高可用原理 事务的基础知识 mysql的事务分为显式事务和隐式事务 默认的事务是隐式事务 显式事务由我们自己控制事务的开启&#xff0c;提交&#xff0c;回滚等操作 show variables like autocommit; 事务基本语法 事务开始 1、begin 2、START TRANSACTION&…

MySQL数据恢复(适用于误删后马上发现)

首先解释一下标题&#xff0c;之所以适用于误删后马上发现是因为太久了之后时间和当时操作的数据表可能会记不清楚&#xff0c;不是因为日志丢失 1.首先确保自己的数据库开启了binlog&#xff08;我的是默认开启的我没有配置过&#xff09; 根据这篇博客查看自己的配置和自己…

AI墓地:738个倒闭AI项目的启示

近年来&#xff0c;人工智能技术迅猛发展&#xff0c;然而&#xff0c;不少AI项目却在市场上悄然消失。根据AI工具聚合网站“DANG”的统计&#xff0c;截至2024年6月&#xff0c;共有738个AI项目停运或停止维护。本文将探讨这些AI项目失败的原因&#xff0c;并分析当前AI初创企…

前端跨域问题--解析与实战

引言 在现代网络应用中&#xff0c;跨域问题是一个常见的挑战。由于浏览器的同源策略&#xff0c;限制了从不同源&#xff08;域名、协议或端口&#xff09;进行资源共享&#xff0c;这就造成了跨域访问的限制。跨域资源共享&#xff08;CORS&#xff09;是一种技术&#xff0…

九、函数的声明和定义

函数声明&#xff1a; 1. 告诉编译器有一个函数叫什么&#xff0c;参数是什么&#xff0c;返回类型是什么。但是具体是不是存在&#xff0c;函数 声明决定不了。 2. 函数的声明一般出现在函数的使用之前。要满足先声明后使用。 3. 函数的声明一般要放在头文件中的。 定义的函…

育才兴业,助力数字产业蓬勃发展

成都树莓集团通过校企合作、建设人才项目转化中心、推动一线多园战略以及提供全方位服务等举措&#xff0c;积极培养数字产业人才&#xff0c;为行业发展提供了有力支持。 一、校企合作&#xff0c;打造人才培养高地 树莓集团深知企业协同育人的重要性&#xff0c;积极与高校建…

某DingTalk企典 - Token

⚠️前言⚠️ 本文仅用于学术交流。 学习探讨逆向知识&#xff0c;欢迎私信共享学习心得。 如有侵权&#xff0c;联系博主删除。 请勿商用&#xff0c;否则后果自负。 网址 aHR0cHM6Ly9kaW5ndGFsay5jb20vcWlkaWFuLw 浅聊一下 没毛病&#xff0c;就这字段&#xff0c;有效期…

java考试题20道

选择题 编译Java源代码文件的命令是javac javac命令是将Java源代码文件进行编译得到字节码文件(.class文件) java命令是在JVM上运行得到的字节码文件 下面是一个示例&#xff1a; javac test.java -------> test.class java test ------> 运行test.class文件下列那…