【数据结构】树与二叉树、树与森林部分习题以及算法设计例题 2

目录

  • 【数据结构】树与二叉树、树与森林部分习题以及算法设计例题
    • 一、交换二叉树每个结点的左右孩子
      • Swap 函数(先序遍历):
      • Swap 函数(中序遍历)××× 不可行:
      • Swap 函数(后序遍历):
    • 二、非递归算法求森林中有几棵树
      • 树的二叉链表(孩子-兄弟)存储表示法
    • 三、判断二叉树是否为完全二叉树
    • 四、求二叉树的最小深度 以及 二叉树树高

  1. 树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)
  2. 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子)
  3. 树与森林知识点文章: 【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)
  4. 树与二叉树、树与森林部分习题: 【数据结构】树与二叉树、树与森林部分习题与算法设计例题

【数据结构】树与二叉树、树与森林部分习题以及算法设计例题

一、交换二叉树每个结点的左右孩子

以上代码实现了交换二叉树每个节点的左右孩子的功能,分别使用了先序、中序和后序遍历的方式。

遍历二叉树算法的变式:

  1. Swap 函数(先序遍历):

    • 从根节点开始,先交换当前节点的左右孩子。
    • 然后递归地对左子树和右子树执行相同的操作。
  2. Swap2 函数(中序遍历):

    • 与先序遍历不同,中序遍历中需要先对左子树进行操作,然后交换当前节点的左右孩子,最后对右子树进行操作。
    • 但是这个实现方式是错误的,因为在交换左子树之后,对右子树进行操作时,右子树的结构已经发生了变化,导致结果错误。
  3. Swap3 函数(后序遍历):

    • 与先序遍历类似,但是是在遍历完左右子树之后再交换当前节点的左右孩子。
    • 这样可以保证在交换左右孩子时,左右子树的结构不会被改变。

通过上述分析,正确的交换方式是采用先序或后序遍历,中序遍历方式不适合这个场景。

Swap 函数(先序遍历):

//前序
void Swap(BiTree& T){//(先序遍历) if(T){//根节点 if(T->lchild||T->rchild){BiTree p;p= T->lchild;T->lchild = T->rchild;T->rchild = p;}Swap(T->lchild);Swap(T->rchild);}
}

Swap 函数(中序遍历)××× 不可行:

//中序的不行 
void Swap2(BiTree& T){//(中序遍历) if(T){//根节点 Swap2(T->lchild);if(T->lchild||T->rchild){BiTree p;p= T->lchild;T->lchild = T->rchild;T->rchild = p;}Swap2(T->rchild);}
}

Swap 函数(后序遍历):

//后序
void Swap3(BiTree& T){//(后序遍历) if(T){//根节点 Swap3(T->lchild);Swap3(T->rchild);if(T->lchild||T->rchild){BiTree p;p= T->lchild;T->lchild = T->rchild;T->rchild = p;}}}

综上可行的只有先序和后序这两种方法:

//交换二叉树每个结点的左右孩子
//先序
void XXSwap_LandRchild(BiTree &T){BiTree p;if(T==NULL) return;else{//先序if(!T->lchild&&!T->rchild) return;p=T->lchild;T->lchild=T->rchild;T->rchild=p;XXSwap_LandRchild(T->lchild);XXSwap_LandRchild(T->rchild);}
}
//后序
void HXSwap_LandRchild(BiTree &T){BiTree p;if(T==NULL) return;else{//后序if(!T->lchild&&!T->rchild) return;HXSwap_LandRchild(T->lchild);HXSwap_LandRchild(T->rchild);p=T->lchild;T->lchild=T->rchild;T->rchild=p;}
}

完整代码示例:

//设二叉树采用二叉链表存储,设计递归算法实现二叉树中所有结点的左右孩子交换。
#include<iostream>
using namespace std;//二叉链表
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(BiTree &T) {char ch; scanf("%c",&ch);if (ch=='#') T = NULL;else {T = (BiTNode*)malloc(sizeof(BiTNode));T->data = ch;      // 生成根结点CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}
}void XXSwap_LandRchild(BiTree &T){BiTree p;if(T==NULL) return;else{//先序if(!T->lchild&&!T->rchild) return;p=T->lchild;T->lchild=T->rchild;T->rchild=p;XXSwap_LandRchild(T->lchild);XXSwap_LandRchild(T->rchild);}
}void HXSwap_LandRchild(BiTree &T){BiTree p;if(T==NULL) return;else{//后序if(!T->lchild&&!T->rchild) return;HXSwap_LandRchild(T->lchild);HXSwap_LandRchild(T->rchild);p=T->lchild;T->lchild=T->rchild;T->rchild=p;}
}void XXPrintTree(BiTree T){if(T==NULL) return;else{cout<<T->data<<" ";XXPrintTree(T->lchild);XXPrintTree(T->rchild);}
}int main()
{BiTree T;CreateBiTree(T);XXPrintTree(T);cout<<endl;XXSwap_LandRchild(T);XXPrintTree(T);cout<<endl;HXSwap_LandRchild(T);XXPrintTree(T);cout<<endl;return 0;
}

二、非递归算法求森林中有几棵树

树的二叉链表(孩子-兄弟)存储表示法

[fc,data,nb]
在这里插入图片描述

typedef struct CSNode{int data;struct CSNode *fc, *nb;
}CSNode, *CSTree;

树中每个结点三部分:
数据域(data),长子指针域(fc),
右邻兄弟指针域(nb)

树和二叉树的转换
• 树以孩子兄弟表示法存,相当于将树转换成二叉树,但此二叉树根结点无右子树
• 好处:借助二叉树的操作实现树的操作

森林与二叉树的转换

⮚ 树采用二叉链表(孩子-兄弟)存储表示法,转换成二叉树
⮚ 森林由多棵树组成: F = ( T 1 , T 2 , … , T n ) F = ( T1, T2, …, Tn ) F=(T1,T2,,Tn); 将其每棵树转换成二叉树 B T 1 , B T 2 , … , B T n BT₁, BT₂, …, BTn BT1,BT2,,BTn;
⮚ 每棵二叉树BT的根的右子树皆为空树,从BTn开始依次将其根结点链为前一棵二叉树的根的右孩子
⮚ 将森林转换成一棵二叉树,森林的操作可借助二叉树的操作完成

森林和二叉树的转换
• 森林以孩子兄弟表示法存,相当于将森林转换成二叉树
• 好处:借助二叉树的操作实现森林的操作

因此只需要一直向右下数结点的个数就行

typedef struct CSNode{int data;struct CSNode *fc, *nb;
}CSNode, *CSTree;//非递归算法求森林中有几棵树。
int CountForestTrees(CSTree F){CSTree p=F;int num=1;while(p){p=p->nb;//右子树num++;}return num;
}

完整代码示例:

//设森林采用根节点为T的二叉链表存储,设计非递归算法求森林中有几棵树。
#include<iostream>
using namespace std;typedef struct CSNode{int data;struct CSNode *fc, *nb;
}CSNode, *CSTree;//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(CSTree &T) {char ch; scanf("%c",&ch);if (ch=='#') T = NULL;else {T = (CSNode*)malloc(sizeof(CSNode));T->data = ch;      // 生成根结点CreateBiTree(T->fc); // 构造左子树CreateBiTree(T->nb); // 构造右子树}
}//非递归算法求森林中有几棵树。
int CountForestTrees(CSTree F){CSTree p=F;int num=1;while(p){p=p->nb;//右子树num++;}return num;
}int main()
{CSTree T;CreateBiTree(T);cout<<"森林一共有"<<CountForestTrees(T)<<"棵树"<<endl;return 0;
}

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

判断二叉树是否为完全二叉树的函数:

//完全二叉树的性质
bool check(BiTree T){if((T->lchild && T->rchild)||(!T->lchild && !T->rchild))return true;return false;
}       //判断是否的完全二叉树
bool is_Complete_Binarytree(BiTree T){BiTree p=T;SqQueue Q;if(!T) return true;//空树也是完全二叉树InitQueue(Q);EnQueue(Q,p);while(!is_QueueEmpty(Q)){DeQueue(Q,p);if(!check(p)) return false;else{if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);}}return true;
}

(带main函数)题解代码示例:

//给定一个二叉树,找出其最小深度。
//最小深度是从根节点到最近叶子节点的最短路径上的节点数量。#include<iostream>
using namespace std;//判断二叉树是否为完全二叉树//结点定义入下:
//二叉链表
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;//若用到队列,请用循环队列,并请实现队列的相关操作以供调用。#define MAXQSIZE 100typedef struct {BiTree *base;int front,rear;
} SqQueue; //定义循环队列//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(BiTree &T) {char ch; scanf("%c",&ch);if (ch=='#') T = NULL;else {T = (BiTNode*)malloc(sizeof(BiTNode));T->data = ch;      // 生成根结点CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}
}
//队列的初始化
void InitQueue(SqQueue &Q){Q.base = (BiTree *)malloc(MAXQSIZE*sizeof(BiTree));Q.front = Q.rear = 0;//队列初始化
}//队空
bool is_QueueEmpty(SqQueue Q){if(Q.rear==Q.front) return true;return false;
}//队满
bool is_QueueMAX(SqQueue Q){if((Q.rear+1)%MAXQSIZE == Q.front) return true;return false;
}//入队
void EnQueue(SqQueue &Q,BiTree e){if(!is_QueueMAX(Q)){Q.base[Q.rear]=e;Q.rear = (Q.rear + 1) % MAXQSIZE;}else{cout<<"ERROR!!! 队列已满"<<endl;}
}
//出队
void DeQueue(SqQueue &Q,BiTree &e){if(!is_QueueEmpty(Q)){e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXQSIZE;}else{cout<<"ERROR!!! 队列为空"<<endl;}
}//完全二叉树的性质
bool check(BiTree T){if((T->lchild && T->rchild)||(!T->lchild && !T->rchild))return true;return false;
}       //判断是否的完全二叉树
bool is_Complete_Binarytree(BiTree T){BiTree p=T;SqQueue Q;if(!T) return true;//空树也是完全二叉树InitQueue(Q);EnQueue(Q,p);while(!is_QueueEmpty(Q)){DeQueue(Q,p);if(!check(p)) return false;else{if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);}}return true;
}//层次遍历算法 
void LevelOrderTraverse(BiTree T)
{	BiTree p = T;SqQueue Q;if(!T) return;	InitQueue(Q); EnQueue(Q,p);while (!is_QueueEmpty(Q)){	DeQueue(Q,p);printf("%c ", p->data);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);}
}int main(){BiTree T;//例如输入:ABC##DE##F### 来创建二叉树 CreateBiTree(T);LevelOrderTraverse(T);cout<<endl;if(is_Complete_Binarytree(T)){cout<<"是完全二叉树"<<endl;}else{cout<<"不是完全二叉树"<<endl;}return 0; 
} 

四、求二叉树的最小深度 以及 二叉树树高

给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

求二叉树的最小深度的函数:

//直接就是将求树高的程序进行修改,将找左右子树最大树高 改为求左右子树 最小树高
//求二叉树的最小深度
int Get_minHeigt(BiTree T){//二叉树的最小深度if(T==NULL) return 0;else{int Left_Height = Get_minHeigt(T->lchild);int Right_Height = Get_minHeigt(T->rchild);int Tree_minHeight = 1+(Left_Height < Right_Height?Left_Height:Right_Height);//取最短路径return Tree_minHeight;}}

(带main函数)题解代码示例:

//给定一个二叉树,找出其最小深度。
//最小深度是从根节点到最近叶子节点的最短路径上的节点数量。#include<iostream>
using namespace std;typedef struct TreeNode{int data;//数据域TreeNode *rchild;//右孩子指针TreeNode *lchild;//左孩子指针
}TreeNode, *BiTree;//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(BiTree &T) {char ch; scanf("%c",&ch);if (ch=='#') T = NULL;else {T = (TreeNode*)malloc(sizeof(TreeNode));T->data = ch;      // 生成根结点CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}
}//求树高 
int Get_Height(BiTree node){//递归 求树高 if(node==NULL) return 0;else{int Left_Height = Get_Height(node->lchild);int Right_Height = Get_Height(node->rchild);int Tree_Height = 1 + (Left_Height > Right_Height?Left_Height:Right_Height);//计算树高return Tree_Height;}}
//求二叉树的最小深度
int Get_minHeigt(BiTree T){//二叉树的最小深度if(T==NULL) return 0;else{int Left_Height = Get_minHeigt(T->lchild);int Right_Height = Get_minHeigt(T->rchild);int Tree_minHeight = 1+(Left_Height < Right_Height?Left_Height:Right_Height);//取最短路径return Tree_minHeight;}}int main(){BiTree T;//例如输入:ABC##DE##F### 来创建二叉树 CreateBiTree(T);cout<<"树高为:" ;cout<<Get_Height(T)<<endl;cout<<"根节点到叶节点的最短路径上的节点数量为:";cout<<Get_minHeigt(T)<<endl;return 0; 
} 

感谢阅读!!!

  1. 树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)
  2. 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子)
  3. 树与森林知识点文章: 【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)
  4. 树与二叉树、树与森林部分习题: 【数据结构】树与二叉树、树与森林部分习题与算法设计例题

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

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

相关文章

【开发篇】十三、JVM基础参数设置与垃圾回收器的选择

文章目录 1、-Xmx 和 –Xms2、-XX:MaxMetaspaceSize 和 –XX:MetaspaceSize3、-Xss4、不建议改的参数5、其他参数6、选择GC回收器的调试思路7、CMS的并发模式失败现象的解决8、调优案例 GC问题解决方式&#xff1a; 优化JVM基础参数&#xff0c;避免频繁Full GC减少对象的产生…

0基础如何入门编程?

0基础如何进入IT行业 &#xff1f; 前言 简介&#xff1a;对于没有任何相关背景知识的人来说&#xff0c;如何才能成功进入IT行业&#xff1f;是否有一些特定的方法或技巧可以帮助他们实现这一目标&#xff1f; 主要方法有如下几点建议提供给宝子们 目录 免费视频网课学习…

读书笔记之《如何精心设计提示词来精通ChatGPT》

《如何精心设计提示词来精通ChatGPT》这本书英文标题为&#xff1a;《The Art of Prompt Engineering with chatGPT》&#xff0c;于2023年出版。作者是Nathan Hunter 。 Nathan Hunter简介&#xff1a;ChatGPT培训的创始人。作为一名资深培训师和教学设计师&#xff0c;我在过…

Spring Cloud 集成 Redis 发布订阅

目录 前言步骤引入相关maven依赖添加相关配置 使用方法发布订阅发布一个消息 注意总结 前言 在当今的软件开发领域&#xff0c;分布式系统已经成为一种主流的架构模式&#xff0c;尤其是在处理大规模、高并发、高可用的业务场景时。然而&#xff0c;随着系统复杂性的增加&…

elementor和divi的对比,哪个更适合你,他们国产化替代方案

Elementor和Divi都是流行的WordPress页面构建器&#xff0c;它们各自具有一些独特的优点和缺点。现在有越来越多的应用服务商开发了自助建站工具&#xff0c;通过自助建站工具&#xff0c;我们可以轻松的创建一个看起来很专业的网站。但在眼花缭乱的软件产品面前&#xff0c;我…

SpringMVC(三)【REST 风格】

1、REST 风格 1.1、REST 简介 REST&#xff08;Representational State Transfer&#xff09;&#xff0c;表现形式状态转换 在开发中&#xff0c;它其实指的就是访问网络资源的格式 1.1.1、传统风格资源描述形式 http://localhost/user/getById?id1http://localhost/user…

数据结构——栈(C++实现)

数据结构——栈 什么是栈栈的实现顺序栈的实现链栈的实现 今天我们来看一个新的数据结构——栈。 什么是栈 栈是一种基础且重要的数据结构&#xff0c;它在计算机科学和编程中扮演着核心角色。栈的名称源于现实生活中的概念&#xff0c;如一叠书或一摞盘子&#xff0c;新添加…

【C++初阶】C++简单入门(长期维护)

本篇博客是对C的一些简单知识分享&#xff0c;有需要借鉴即可。 C简单入门目录 一、C前言1.C的概念&#xff1a;2.C发展历程3.C如何学&#xff1f; 二、C入门1.C关键字(C98标准)2.命名空间3.C输入&输出①概念说明②使用说明③特征说明④细节拓展⑤cout与cin的意义 4.缺省参…

处理json文件,并将数据汇总至Excel表格

从scores.jason文件中读取学生信息,输出学生的学号&#xff0c;姓名&#xff0c;各科成绩&#xff0c;平均分, 各科标准差 scores.jason {"学院": "计算机学院","班级": "2022级1班","成绩": [{"学号": 1001,&q…

【vue】绑定事件 v-on

v-on 简写&#xff1a; clickkeyupkeydownkeyup.wkeyup.ctrl.a <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><…

BK9534 博通BEKEN 无线麦克风芯片 提供配置工具软件

BK9534 芯片是在 BK9532 芯片基础上增加了一个内置MCU 来实现单芯片简单工作模式&#xff0c;内置己经固化了如开关机&#xff0c;对码&#xff0c;低电侦测&#xff0c;自动频率跟随等基本功能。另外还可以借助工具修改如频率&#xff0c;ID等相关配置信息. 1. 升级了接收芯片…

SpringBoot修改菜品模块开发

需求分析与设计 一&#xff1a;产品原型 在菜品管理列表页面点击修改按钮&#xff0c;跳转到修改菜品页面&#xff0c;在修改页面回显菜品相关信息并进行修改&#xff0c;最后点击保存按钮完成修改操作。 修改菜品原型&#xff1a; 二&#xff1a;接口设计 通过对上述原型图…

Midjourney常见玩法及prompt关键词技巧

今天系统给大家讲讲Midjourney的常见玩法和prompt关键词的一些注意事项&#xff0c;带大家入门&#xff5e;&#xff08;多图预警&#xff0c;建议收藏&#xff5e;&#xff09; 一、入门及常见玩法 1、注册并添加服务器&#xff08;会的童鞋可跳过&#xff5e;&#xff09; …

SpringBoot与MyBatisPlus的依赖版本冲突问题

记录使用SpringBoot和MyBatisPlus时遇到的版本冲突问题解决。 java版本&#xff1a;jdk17 废话&#xff1a;&#xff09;目前在IDEA中使用Spring官方的脚手架最低jdk版本竟然是jdk17了。 当使用SpringBoot3.0版本(3.2.4)&#xff0c;配合使用MP3.5.2版本时报错&#xff1a; Er…

H5代码video标签引入视频在浏览器的兼容性问题解决办法

H5标签video引入视频&#xff0c;在谷歌浏览器正常但是在火狐浏览器和版本较低的浏览器或者IE浏览器却无法观看视频&#xff0c;只能看到音频&#xff0c;是什么原因&#xff1f; 代码如下 <video class"video" muted loop"loop" style"display…

前端三剑客 —— JavaScript (第九节)

目录 内容回顾&#xff1a; 1.事件解除 2. Ajax jQuery选择器 回顾CSS选择器 CSS选择 1.基本选择器 2.包含选择器 3.伪类选择器 4.伪元素选择器 5.属性选择器 jQuery 库 jQuery 动画 系统动画 自定义动画 常见API操作 内容回顾&#xff1a; 1.事件解除 如果是使…

《由浅入深学习SAP财务》:第2章 总账模块 - 2.6 定期处理 - 2.6.3 月末操作:外币评估

2.6.3 月末操作&#xff1a;外币评估 企业的外币业务在记账时一般使用期初的汇率或者即时汇率&#xff0c;但在月末&#xff0c;需要按照月末汇率对外币的余额或者未清项进行重估&#xff08;revaluation&#xff09;。 企业在资产负债表日&#xff0c;应当按照下列规…

微信小程序全局配置

全局配置文件及常用的配置项 小程序根目录下的 app.json 文件是小程序的全局配置文件。常用的配置项如下&#xff1a; ① pages 记录当前小程序所有页面的存放路径 ② window 全局设置小程序窗口的外观 ③ tabBar 设置小程序底部的 tabBar 效果 ④ style 是否启用新版的组件样…

SpringBoot菜品分页查询模块开发(多表连接查询)

需要注意的地方 为什么创建VO类怎么进行多表连接查询分页查询的统一返回结果类PageResult分页查询Mapper的返回结果是Page<目标实体类> 需求分析与设计 一&#xff1a;产品原型 系统中的菜品数据很多的时候&#xff0c;如果在一个页面中全部展示出来会显得比较乱&…

华火电燃灶荣获国家级科技型中小企业

华火电燃灶作为一家国家级科技型中小企业&#xff0c;凭借其创新的技术和卓越的产品性能&#xff0c;在新能源厨电领域取得了显著的成就。华火&#xff0c;潜心钻研等离子电生明火技术近十年&#xff1b;华火电燃灶&#xff0c;电生明火&#xff0c;以“电”作为唯一能源&#…