【数据结构】树与二叉树(八):二叉树的中序遍历(非递归算法NIO)

文章目录

5.2.1 二叉树

  二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是空集,被称为空二叉树,要么由一个根结点和两棵不相交的子树组成,分别称为左子树右子树。每个结点最多有两个子结点,分别称为左子结点和右子结点。
在这里插入图片描述

二叉树性质

引理5.1:二叉树中层数为i的结点至多有 2 i 2^i 2i个,其中 i ≥ 0 i \geq 0 i0

引理5.2:高度为k的二叉树中至多有 2 k + 1 − 1 2^{k+1}-1 2k+11个结点,其中 k ≥ 0 k \geq 0 k0

引理5.3:设T是由n个结点构成的二叉树,其中叶结点个数为 n 0 n_0 n0,度数为2的结点个数为 n 2 n_2 n2,则有 n 0 = n 2 + 1 n_0 = n_2 + 1 n0=n2+1

  • 详细证明过程见前文:【数据结构】树与二叉树(三):二叉树的定义、特点、性质及相关证明

满二叉树、完全二叉树定义、特点及相关证明

  • 详细证明过程见前文:【数据结构】树与二叉树(四):满二叉树、完全二叉树及其性质

5.2.2 二叉树顺序存储

  二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中,详见:
【数据结构】树与二叉树(五):二叉树的顺序存储(初始化,插入结点,获取父节点、左右子节点等)

5.2.3 二叉树链接存储

  二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中,结点之间的关系用指针说明。在链式存储中,每个二叉树结点都包含三个域:数据域(Data)、左指针域(Left)和右指针域(Right),用于存储结点的信息和指向子结点的指针,详见:
【数据结构】树与二叉树(六):二叉树的链式存储

5.2.4 二叉树的遍历

  • 遍历(Traversal)是对二叉树中所有节点按照一定顺序进行访问的过程。
  • 通过遍历,可以访问树中的每个节点,并按照特定的顺序对它们进行处理。
  • 对二叉树的一次完整遍历,可给出树中结点的一种线性排序。
    • 在二叉树中,常用的遍历方式有三种:先序遍历中序遍历后序遍历
    • 这三种遍历方式都可以递归地进行,它们的区别在于节点的访问顺序
      • 在实现遍历算法时,需要考虑递归终止条件和递归调用的顺序。
    • 还可以使用迭代的方式来实现遍历算法,使用栈或队列等数据结构来辅助实现。
  • 遍历是二叉树中基础而重要的操作,它为其他许多操作提供了基础,如搜索、插入、删除等。
    在这里插入图片描述

1-3 先序、中序、后序遍历递归实现及相关练习

【数据结构】树与二叉树(七):二叉树的遍历(先序、中序、后序及其C语言实现)

中序遍历递归实现

void inOrderTraversal(struct Node* root) {if (root == NULL) {return;}// 递归遍历左子树inOrderTraversal(root->left);// 访问根节点printf("%c ", root->data);// 递归遍历右子树inOrderTraversal(root->right);
}

4. 中序遍历非递归

a. 算法NIO

在这里插入图片描述

b. 算法解读

  NIO算法利用了一个辅助堆栈S来模拟递归过程中的函数调用栈。通过在循环中不断将左子节点入栈,然后处理栈顶节点,并将指针移动到右子节点,实现了中序遍历的非递归算法。

  1. 创建一个空堆栈S,并将指针p指向树的根节点t。
  2. 进入循环,只要p不为空,执行以下步骤:
    a. 将p入栈S。
    b. 将p指向其左子节点(p = Left( p ))。
  3. 如果堆栈S为空,则结束算法。
  4. 从堆栈S中弹出栈顶元素,并将p指向弹出的节点。
  5. 打印p节点的值。
  6. 将p指向p的右子节点(p = Right( p ))。
  7. 跳转到步骤2,继续循环。

  该算法的时间复杂度为O(n),其中n是二叉树中节点的数量。因为每个节点都会被访问一次且入栈一次,所以算法的时间复杂度与节点数量成正比。

  这个非递归中序遍历算法可以应用于需要遍历二叉树并按照中序顺序访问节点的场景,例如在构建二叉树的线索化结构时,或者需要按照中序顺序遍历二叉搜索树等情况下。

c. 典例剖析

在这里插入图片描述

在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

d.代码实现

void nonRecursiveInOrder(struct Node* root) {struct Node* stack[100];  // 辅助堆栈,用于模拟递归调用栈int top = -1;  // 栈顶指针struct Node* current = root;while (current != NULL || top != -1) {// 将当前结点的左子结点入栈while (current != NULL) {stack[++top] = current;current = current->left;}// 弹出栈顶结点,并访问current = stack[top--];printf("%c ", current->data);// 处理右子结点current = current->right;}
}

5. 代码整合

#include <stdio.h>
#include <stdlib.h>// 二叉树结点的定义
struct Node {char data;struct Node* left;struct Node* right;
};// 创建新结点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));if (newNode == NULL) {printf("Memory allocation failed!\n");exit(1);}newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}
// 递归中序遍历
void inOrderTraversal(struct Node* root) {if (root == NULL) {return;}// 递归遍历左子树inOrderTraversal(root->left);// 访问根节点printf("%c ", root->data);// 递归遍历右子树inOrderTraversal(root->right);
}// 非递归中序遍历
void nonRecursiveInOrder(struct Node* root) {struct Node* stack[100];  // 辅助堆栈,用于模拟递归调用栈int top = -1;  // 栈顶指针struct Node* current = root;while (current != NULL || top != -1) {// 将当前结点的左子结点入栈while (current != NULL) {stack[++top] = current;current = current->left;}// 弹出栈顶结点,并访问current = stack[top--];printf("%c ", current->data);// 处理右子结点current = current->right;}
}int main() {// 创建一棵二叉树struct Node* root = createNode('a');root->left = createNode('b');root->right = createNode('c');root->left->left = createNode('d');root->left->right = createNode('e');root->left->right->left = createNode('f');root->left->right->right = createNode('g');// 递归中序遍历二叉树printf("Recursive In-order traversal: \n");inOrderTraversal(root);printf("\n");// 非递归中序遍历二叉树printf("Non-recursive In-order traversal:\n");nonRecursiveInOrder(root);printf("\n");return 0;
}

在这里插入图片描述

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

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

相关文章

从零开始的C++(十四)

继承&#xff1a; 作用&#xff1a;减少重复代码&#xff0c;简化程序。 用法&#xff1a; class b&#xff1a;public a {//...b中成员 } 在如上代码中&#xff0c;b类以public的方式继承了a类。规定a类是父类、基类&#xff0c;b类是子类、派生类。 关于继承方式&#xf…

力扣字符串--总结篇

前言 字符串学了三天&#xff0c;七道题。初窥kmp&#xff0c;已经感受到算法的博大精深了。 内容 对字符串的操作可以归结为以下几类&#xff1a; 字符串的比较、连接操作&#xff08;不同编程语言实现方式有所不同&#xff09;&#xff1b; 涉及子串的操作&#xff0c;比…

Electron-vue出现GET http://localhost:9080/__webpack_hmr net::ERR_ABORTED解决方案

GET http://localhost:9080/__webpack_hmr net::ERR_ABORTED解决方案 使用版本解决方案解决总结 使用版本 以下是我解决此问题时使用的electron和vue等的一些版本信息 【附】经过测试 electron 的版本为 13.1.4 时也能解决 解决方案 将项目下的 .electron-vue/dev-runner.js…

【PWN · ret2csu】[HNCTF 2022 WEEK2]ret2csu

记一道ret2csu 一、题目 二、思路 1.ret2csu用write泄露write的真实地址->泄露libc->获得system的真实地址 2.ret2csu用read写/bin/sh字符串到bss段上 3.ret2csu用write将system的真实地址写到bss段上 4.ret2csu调用system 三、exp from pwn import * from pwn impo…

[100天算法】-最短无序连续子数组(day 70)

题目描述 给定一个整数数组&#xff0c;你需要寻找一个连续的子数组&#xff0c;如果对这个子数组进行升序排序&#xff0c;那么整个数组都会变为升序排序。你找到的子数组应是最短的&#xff0c;请输出它的长度。示例 1:输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5 解释: 你只需要…

Linux下内网穿透实现云原生观测分析工具的远程访问

&#x1f4d1;前言 本文主要是Linux下内网穿透实现云原生观测分析工具的远程访问设置的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风讲故事 &…

[C/C++]数据结构 链表OJ题:环形链表(如何判断链表是否有环)

题目描述: 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&…

Docker+K8s基础(重要知识点总结)

目录 一、Docker的核心1&#xff0c;Docker引擎2&#xff0c;Docker基础命令3&#xff0c;单个容器运行多个服务进程4&#xff0c;多个容器运行多个服务进程5&#xff0c;备份在容器中运行的数据库6&#xff0c;在宿主机和容器之间共享数据7&#xff0c;在容器之间共享数据8&am…

OSG交互:选中场景模型并高亮显示

1、目的 可以在osg视图中选中指定模型实体,并高亮显示。共分为两种,一种鼠标点选,一种框选。 2、鼠标点选 2.1 功能说明 生成两组对象,一组cow对象可以被选中,另一组robot不能被选中;点击cow对象被选中高亮,点击robot被选中不高亮;点击空白处,弹出“select nothing!…

P6入门:项目初始化2-项目详情之日期Date

前言 使用项目详细信息查看和编辑有关所选项目的详细信息&#xff0c;在项目创建完成后&#xff0c;初始化项目是一项非常重要的工作&#xff0c;涉及需要设置的内容包括项目名&#xff0c;ID,责任人&#xff0c;日历&#xff0c;预算&#xff0c;资金&#xff0c;分类码等等&…

STM32H743XX/STM32H563XX芯片烧录一次后,再次上电无法烧录

近期在使用STM32H563ZIT6这款芯片在开发板上使用正常&#xff0c;烧录到自己打的板子就遇到了芯片烧录一次后&#xff0c;再次上电无法烧录的问题。 遇到问题需要从以下5点进行分析。 首先看下开发板的原理图 1.BOOT0需要拉高。 2.NRST脚在开发板上是悬空的。这里我建议大家…

远程电脑未连接显示器时分辨率太小的问题处理

背景&#xff1a;单位电脑显示器坏了&#xff0c;使用笔记本通过向日葵远程连接&#xff0c;发现分辨率只有800*600并且不能修改&#xff0c;网上找了好久找到了处理方法这里记录一下&#xff0c;主要用到的是一个虚拟显示器软件usbmmidd_v2 1)下载usbmmidd_v2 2&#xff09;…

2022年12月 Python(四级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 有n个按名称排序的商品,使用对分查找法搜索任何一商品,最多查找次数为5次,则n的值可能为?()(2分) A.5 B.15 C.30 D.35 答案:C 答案解析:对分查找最多查找次数m与个数之间n的…

【星海随笔】SDN neutron (一)

一、SDN的原理&#xff1a; 控制平面与数据平面分离&#xff1a;传统网络中&#xff0c;网络设备同时承担控制和数据转发功能&#xff0c;而SDN将这两个功能分离&#xff0c;使得网络控制集中在一个中心控制器上。 中心控制器&#xff1a;SDN架构中的中心控制器负责网络的全局…

一个“Hello, World”Flask应用程序

如果您访问Flask网站&#xff0c;会看到一个非常简单的示例应用程序&#xff0c;只有5行代码。为了不重复那个简单的示例&#xff0c;我将向您展示一个稍微复杂一些的示例&#xff0c;它将为您编写大型应用程序提供一个良好的基础结构。 应用程序将存在于包中。在Python中&…

aosp定制android系统

目录 AOSP 准备工作(配置) 确定机型和版本 初始化 git安装 curl安装 同步源码 环境变量 创建aosp目录 指定同步版本 解下来安装编译需要的依赖 编译aosp源码 刷入系统 AOSP 全称 Android Open Source Project 是指Android开源项目&#xff0c;它是由Google主导的…

gird 卡片布局

场景一&#xff1a;单元格大小相等 这承载了所有 CSS Grid 中最著名的片段&#xff0c;也是有史以来最伟大的 CSS 技巧之一&#xff1a; 等宽网格响应式卡片实现 .section-content {display: grid;grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));gap: 10px; …

list部分接口模拟实现(c++)

List list简介list基本框架list构造函数list_node结构体的默认构造list类的默认构造 push_back()iteartor迭代器迭代器里面的其他接口const迭代器通过模板参数实现复用operator->() insert()erase()clear()析构函数迭代器区间构造拷贝构造operator() list简介 - list可以在…

使用 pubsub-js 进行消息发布订阅

npm 包地址 github 包地址 pubsub-js 是一个轻量级的 JavaScript 基于主题的消息订阅发布库 &#xff0c;压缩后小于1b。它具有使用简单、性能高效、支持多平台等优点&#xff0c;可以很好地满足各种需求。 功能特点&#xff1a; 无依赖同步解耦ES3 兼容。pubsub-js 能够在…

Angular 由一个bug说起之一:List / Grid的性能问题

在angular中&#xff0c;MatTable构建简单&#xff0c;使用范围广。但某些时候会出现卡顿 卡顿情景&#xff1a; 1&#xff1a;一次性请求太多的数据 2&#xff1a;一次性渲染太多数据&#xff0c;这会花费CPU很多时间 3&#xff1a;行内嵌套复杂的元素 4&#xff1a;使用过多的…