二叉树的创建与遍历

目录

前言:

二叉树的概念与结构

二叉树的链式存储

 二叉树的创建

二叉树的销毁

二叉树结点个数计算

二叉树叶子结点个数计算

二叉树第k层节点个数的计算

二叉树高度的计算

二叉树查找值为x的结点

 二叉树的遍历

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

二叉树的层序遍历

判断二叉树是否为完全二叉树


前言:

二叉树的层序遍历需要使用队列实现,队列的实现见数据结构之队列,对于二叉树的代码,需要不断画递归展开图进行结合理解,递归展开图不展开描述;

二叉树的概念与结构

一棵二叉树是n个有限结点的集合,该集合或者为空,或者由一个称为根(root)的结点或者由一个根结点加上两棵别称为左子树和右子树的二叉树组成 ;

二叉树的链式存储

二叉树的链式存储结构指的是用链表表示一棵二叉树,即用链表指示元素的逻辑关系;

通常的方法是链表中每个结点由三个域组成,数据域与左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址;

 二叉树的创建

扩展二叉树是指在二叉树中出现空子树的位置增加空树叶,所形成的二叉树,使得子树成为满二叉树的二叉树叫做扩展二叉树;

先序遍历字符串 A B C # # # D # # 其中“#”表示的是空格,空格字符代表空树,则建立起来的二叉树如下图所示:

//二叉树结点结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;
}BTNode;
//创建二叉树,返回根结点地址
//A B C # # # D # #
BTNode* CreateTree(char* str, int* pi)
{if (str[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = str[*pi];(*pi)++;root->left = CreateTree(str, pi);root->right = CreateTree(str, pi);return root;}
int main()
{char arr[100] = { 'A', 'B', 'C', '#', '#', '#', 'D', '#', '#' };int i = 0;BTNode* root = CreateTree(arr, &i);return 0;
}

二叉树的销毁

按照先销毁其左子树,再销毁右子树,最后销毁根的顺序递归销毁二叉树;

void DestroyTree(BTNode* root)
{if (root == NULL)return;DestroyTree(root->left);DestroyTree(root->right);free(root);
}

二叉树结点个数计算

若根结点为空,则二叉树结点个数=0;

若根节点不为空,则二叉树结点个数=左子树的结点个数+右子树极点个数+1;

//二叉树结点个数
int TreeSize(BTNode* root)
{if (root == NULL)return 0;return TreeSize(root->left) + TreeSize(root->right) + 1;
}

二叉树叶子结点个数计算

叶子结点即某一节点出的左孩子为空并且右孩子为空则为叶子结点;

//二叉树叶子结点个数
int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

二叉树第k层节点个数的计算

规定:二叉树的层数K以1为起点,即第一层 k = 1;

二叉树的第k层节点个数=其左子树的第k-1层节点个数+其右子树的第k-1层节点个数;

int TreeKLevel(BTNode* root,int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

二叉树高度的计算

二叉树的高度=左子树的高度与右子树的高度较大值+1;

//二叉树的高度
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int LeftHeight = TreeHeight(root->left);int RightHeight = TreeHeight(root->right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}

二叉树查找值为x的结点

如根节点非空,先查找根,如果根结点处的值即为查找的值,直接返回根节点的地址,如果根节点处未查找到,先查找左子树,找到了直接返回,找不到继续查找右子树;

//二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;struct BinaryTreeNode* ret = NULL;ret = TreeFind(root->left, x);if (ret != NULL)return ret;ret = TreeFind(root->right, x);if (ret != NULL)return ret;return NULL;
}

 二叉树的遍历

  • 前序遍历NLR(依次遍历:根结点—左子树—右子树)
  • 中序遍历LNR(依次遍历:左子树—根结点—右子树)
  • 后序遍历LRN(依次遍历:左子树—右子树—根结点)

 由于二叉树是递归定义的,按照下图所示方法,便可得到前序遍历的结点顺序

 前序遍历结果:A->B->D->E->C->F->G        

中序遍历结果为D->B->E->A->F->C->G;后序遍历结果:D->E->B->F->G->C->A;

二叉树的前序遍历

//二叉树的前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL)return;printf("%c ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}

二叉树的中序遍历

//二叉树的中序遍历
void InOrder(BTNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}

二叉树的后序遍历

//二叉树的后序遍历
void PostOrder(BTNode* root)
{if (root == NULL)return;PostOrder(root->left);PostOrder(root->right);printf("%c ", root->val);
}

二叉树的层序遍历

二叉树的层序遍历是指将二叉树从上到下,从左到右依次遍历,如下图所示层序遍历结果为

A—>B—>D—>C

层序遍历的思路如下:

1.  判断根结点是否为空,非空则入队列

2. 判断队列是否为空,不为空则队头元素出队列,再将队头元素的孩子入队列,若队头元素的孩子为空,则不入队列;

3.判断队列是否为空,将B出队列,再将B的孩子入队列;

4.判断队列是否为空,将D出队列,再将D的孩子入队列;

5. 判断队列是否为空,将C出队列,再将C的孩子入队列;队列为空时结束遍历;

//二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;InitQueue(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%c ", front->val);if (front->left != NULL);QueuePush(&q, front->left);if (front->right != NULL)QueuePush(&q, front->right);QueuePop(&q);}DestroyQueue(&q);
}

判断二叉树是否为完全二叉树

满二叉树:当二叉树深度为K,二叉树结点个数为2^k-1,则为满二叉树;

对满二叉树结点位置进行编号

  • 编号的规则:自上而下,从左向右 ;
  • 每一节点位置都有元素;

完全二叉树

深度为K具有n个结点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中的编号为1~n的节点一 一对应时,称为完全二叉树;

判断二叉树是否是完全二叉树,是完全二叉树返回true,否则返回false;
利用二叉树层序遍历,非空结点连续为完全二叉树,非空结点不连续,存在空节点,则为非完全二叉树;

int BinaryTreeComplete(BTNode* root)
{Queue q;InitQueue(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);QueuePop(&q);}//若已经出现空结点,队列后面结点存在非空结点,则为非完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){DestroyQueue(&q);return false;}}DestroyQueue(&q);return true;
}

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

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

相关文章

代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结

代码随想录算法训练营第五十五天 | LeetCode 583. 两个字符串的删除操作、72. 编辑距离、编辑距离总结 文章链接:两个字符串的删除操作、编辑距离、编辑距离总结 视频链接:两个字符串的删除操作、编辑距离 1. LeetCode 583. 两个字符串的删除操作 1.1 思…

计算机编程入门软件,计算机编程初学入门什么语言

计算机编程入门软件,计算机编程初学入门什么语言 给大家分享一款中文编程工具,零基础轻松学编程,不需英语基础,编程工具可下载。 这款工具不但可以连接部分硬件,而且可以开发大型的软件,象如图这个实例就是…

科研学习|研究方法——逻辑回归系数的显著性检验(python实现)

1. 背景 回归方程与回归系数的显著性检验 2. statsmodels 库 statsmodels库可以用来做逻辑回归、线性回归。并且会在summary中给出显著性检验的结果。最终我们想要的就是如下图的报告。 3. 计算过程 如果我们使用的sklearn构建的逻辑回归就没有办法直接输出这个报告&#xff0c…

swiper垂直方向全屏实现鼠标滚轮滚动一下切换一屏

效果 20231116092014 添加mousewheelControl: true,这个属性即可 <div class"swiper-container"><div class"swiper-wrapper"><div class"swiper-slide" > <div class"" style"height: 100%; background-…

如何使用iPhone15在办公室观看家里电脑上的4k电影?

如何使用iPhone15在办公室观看家里电脑上的4k电影&#xff1f; 文章目录 如何使用iPhone15在办公室观看家里电脑上的4k电影&#xff1f;1.使用环境要求&#xff1a;2.下载群晖videostation&#xff1a;3.公网访问本地群晖videostation中的电影&#xff1a;4.公网条件下使用电脑…

jenkins+centos7上传发布net6+gitlab

工作中实践了一下jenkins的操作&#xff0c;所以记录一下这次经验&#xff0c;没有使用到docker 先看下成果&#xff1a; 选择发布项目 选择要发布的分支 构建中 发布成功 开始 首先安装好jenkins并注册自己的jenkins账号 因为我们的项目代码管理使用的是gitlab&#xff0c…

使用python电脑轻量级控制手机—adb命令和手机投屏

文章目录 一、通过无线连接手机和电脑二、使用adb命令轻量级控制手机二、使用scrcpy控制手机 通过电脑控制手机有多种方式如appnium等&#xff0c;本文介绍的是两种轻量级的方案&#xff0c;使用adb命令刚和手机投屏。 一、通过无线连接手机和电脑 1、手机设置 开发者选项—us…

【视觉SLAM十四讲学习笔记】第二讲——初识SLAM

专栏系列文章如下&#xff1a; 【视觉SLAM十四讲学习笔记】第一讲 一个机器人&#xff0c;如果想要探索某一块区域&#xff0c;它至少需要知道两件事&#xff1a; 我在什么地方——定位周围环境是什么样——建图 一方面需要明白自身的状态&#xff08;即位置&#xff09;&#…

Spring Boot 整合xxl-job实现分布式定时任务

xxl-job介绍 XXL-JOB是一个分布式任务调度平台&#xff0c;其核心设计目标是开发迅速、学习简单、轻量级、易扩展。现已开放源代码并接入多家公司线上产品线&#xff0c;开箱即用。 xxl是xxl-job的开发者大众点评的许雪里名称的拼音开头。 设计思想 将调度行为抽象形成“调度…

高频CSS面试题

给大家推荐一个实用面试题库 1、前端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;web前端面试题库 BFC 块级格式上下文(block format context)是页面一块独立的渲染区域&#xff0c;具有一套独立的渲染规则 内部的…

芯科科技推出新的8位MCU系列产品,扩展其强大的MCU平台

新的BB5系列为简单应用提供更多开发选择 中国&#xff0c;北京 - 2023年11月14日 – 致力于以安全、智能无线连接技术&#xff0c;建立更互联世界的全球领导厂商Silicon Labs&#xff08;亦称“芯科科技”&#xff0c;NASDAQ&#xff1a;SLAB&#xff09;&#xff0c;今日宣布…

Elasticsearch的配置学习笔记

文/朱季谦 Elasticsearch是一个基于Lucene的搜索服务器。它提供一个分布式多用户能力的全文搜索引擎&#xff0c;基于RESTful web接口&#xff0c;Elasticsearch是用Java语言开发的。 关于Elasticsearch系列笔记&#xff0c;主要从Elasticsearch的配置、核心组件、架构设计、使…

还有医学生不知道这个免费好用的在线样本量计算器吗?

相信很多小伙伴都有过这样的经历&#xff1a;做科研设计、撰写论文&#xff0c;设计好主题后摆在眼前的是你最头痛的问题——样本量计算。事实上&#xff0c;样本量计算往往是临床医生做临床研究设计的一大障碍&#xff0c;是临床研究设计、临床知识经验以及统计学知识的结合。…

高阶智驾必上「激光雷达」,一场车企的集体投票

‍作者 | 张祥威 编辑 | 德新 2023年尾上市的这一批车型中&#xff0c;以问界新M7、理想MEGA、小鹏X9、智界S7和极氪007最为典型&#xff0c;它们的头顶大多搭载了一颗激光雷达&#xff0c;有的车型比如小鹏X9&#xff0c;甚至在前大灯位置配置了两颗激光雷达。 这是为实现高…

Pinia 及其数据持久化 Vue新一代状态管理插件

黑马前端Vue新一代状态管理插件Pinia快速入门视频教程 Pinia主页 超级简单&#xff0c;不需要耐心 pinia &#xff1a;新一代的VueX 1. 安装 npm install pinia2. 在main.js中引入 import { createPinia } from pinia app.use(createPinia())3. 新建stores目录&#xff0c…

生命在于学习——主板跳线的学习

一、前言 好吧&#xff0c;又是一个我之前没接触过的东西&#xff0c;秉持遇到什么就学什么的精神&#xff0c;来学&#xff01; 我一发小来找我&#xff0c;问我关于跳线的事情&#xff0c;我就一个表情&#xff1a; 好吧&#xff0c;我承认&#xff0c;纵观我23岁&#xf…

Looking for downloadable pre-built shared indexes关闭

这个功能很烦,把他关闭就行了 PyCharm的“Looking for downloadable pre-built shared indexes”是指PyCharm IDE中的一个功能&#xff0c;用于搜索和下载可共享的预构建索引。 这个功能的主要用途是帮助开发人员在开发过程中快速地获取和使用预构建的索引&#xff0c;以提高…

Leo赠书活动-08期 【程序员到架构师演变】文末送书

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 赠书活动专栏 ✨特色专栏&#xff1a;…

91.移动零(力扣)

问题描述 代码解决以及思想 class Solution { public:void moveZeroes(vector<int>& nums) {int left 0; // 左指针&#xff0c;用于指向当前非零元素应该放置的位置int right 0; // 右指针&#xff0c;用于遍历数组int len nums.size(); // 数组长度while …

Xilinx Kintex7中端FPGA解码MIPI视频,基于MIPI CSI-2 RX Subsystem架构实现,提供工程源码和技术支持

目录 1、前言免责声明 2、我这里已有的 MIPI 编解码方案3、本 MIPI CSI2 模块性能及其优缺点4、详细设计方案设计原理框图OV5640及其配置权电阻硬件方案MIPI CSI-2 RX SubsystemSensor Demosaic图像格式转换Gammer LUT伽马校正VDMA图像缓存AXI4-Stream toVideo OutHDMI输出 5、…