树和二叉树：二叉树的基本运算算法的实现

一.前言

当前版本仅供笔者复盘

二.二叉树

2.1题目

编写一个程序，实现二叉树的基本运算，具体要求如下：（指定示范实例1：图1。指定示范实例2：图2 ）

1，先序遍历输出该树（带“^"标志)。

2，中序遍历输出该树（带“^"标志)。

3，后序遍历输出该树（带“^"标志)。

4，层次遍历输出该树（带“^"标志)。

5，输出该树的先序凹入表表示法(参考附件)。

6，输出该树的中序凹入表表示法。

7，输出该树的后序凹入表表示法。

8，设计一个算法把二叉树b所有的左、右子树进行交换，并用括号表示法输出该树。（要求不破坏原二叉树）

9，（选做题）输出该树相隔最远的一对结点。（例：对图1，N与I相隔最远。提示：相隔最远不一定分别在左右两棵子树上，相隔最远是两个叶子，还有一种就是叶子与根。）

图一
图二

2.2知识点总结

2.2.1排序

我的总结是

#include<bits/stdc++.h>
using namespace std;
#define MAX 10000
typedef char ch;
//首先每个节点的属性如下有数据域，左右孩子
typedef struct BTnode
{
	ch data;
	struct BTnode *lchild;
	struct BTnode *rchild;
}BT;//注意这个是节点的定义
//解读树,用二叉链的形式
void CreatBtree(BT *&B1,ch *str)//输入我们创建的树和树的括号表示法
{//B1是我们的树，str是括号表示法的那串字符
	BT *st[MAX],*p;//B作为一个顺序栈。p就是我们扫描的元素
	int top=-1,k,j=0;ch l;//top是表示栈顶，k表示左右孩子，j是遍历a用的
	B1=NULL;
	l=str[j];
	while(l!='\0'){
		//总结一下：（入栈（表示这条分支的开始），）退栈（因为结束了），遇到元素就创建节点，
		//遇到逗号改k（左右孩子），见下面的注释一
		switch (l) {
			case '(':top++;st[top]=p;k=1;break;
			case ')':top--;break;
			case ',':k=2;break;
		default:
			p=new BT;
			p->data=l;
			p->lchild=p->rchild=NULL;
			if(B1==NULL)//头结点
				B1=p;
			else
			{
				switch (k) {
					case 1:st[top]->lchild=p;break;
					case 2:st[top]->rchild=p;break;
				}
			}
		}
		j++;
		l=str[j];
	}
}
//先序遍历输出该树（带“^"标志)。
void Predisplay(BT *B1)
{
	if(B1!=NULL)
	{
		cout<<B1->data;
		Predisplay(B1->lchild);
		Predisplay(B1->rchild);
	}
	else
		cout<<"^";
}
void Indisplay(BT *B1)
{
	if(B1!=NULL)
	{
		Indisplay(B1->lchild);
		cout<<B1->data;
		Indisplay(B1->rchild);
	}
	else
		cout<<"^";
}
void Postdisplay(BT *B1)
{
	if(B1!=NULL)
	{
		Postdisplay(B1->lchild);
		Postdisplay(B1->rchild);
		cout<<B1->data;
	}
	else 
		cout<<"^";
}
void Picdisplay(BT *B1)
{
	BT *p;
	queue<BT*>q;
	q.push(B1);
	while(!q.empty()){
		if(q.front()!=NULL)
		{
			p=q.front();
			q.pop();
			cout<<p->data;
		}
		else
		{
			cout<<'^';
			q.pop();
			continue;
		}
		q.push(p->lchild);
		q.push(p->rchild);
	}
	
}
//凹凸其本质就是打印的方式变了
//顺序代码还是一样的
void Pre(BT *B1,int h,int k){   //h为高度，k为左右               
	if(B1==NULL)    //常规判断                                
		return;
	for(int i=0;i<h*3;i++)   //越深空格越多，每次规定三个空格                
		cout<<" ";
	cout<<B1->data;
	for(int j=0;j<(30-3*h);j++)   //以30*30的正方形为空间，剩余填充为=         
		cout<<"=";
	if(!h)           //打印最后的字母                               
		cout<<"B";                               
	else{
		if(k)                                        
			cout<<"L";
		else
			cout<<"R"; 
	}
	cout<<endl;
	Pre(B1->lchild,h+1,1);
	Pre(B1->rchild,h+1,0);
} 
void In(BT *B1, int h, int k){
	if(B1==NULL)
		return;
	In(B1->lchild,h+1,1);
	for(int i=0; i<h*3;i++)
		cout<<" ";
	cout<<B1->data;
	for(int j=0; j<(30-3*h);j++)
		cout<<"=";
	if(!h)
		cout<<"B";
	else{
		if(k)
			cout<<"L";
		else
			cout<<"R"; 
	}
	cout<<endl;
	In(B1->rchild,h+1,0);
} 
void Post(BT *B1, int h, int k){//h为高度，k为左右
	if(B1==NULL)
		return;
	Post(B1->lchild,h+1,1);
	Post(B1->rchild,h+1,0);
	for(int i=0; i<h*3;i++)//越深空格越多，每次规定三个空格
		cout<<" ";
	cout<<B1->data;
	for(int j=0;j<(30-3*h);j++)//以30*30的正方形为空间，剩余填充为=
		cout<<"=";
	if(!h)//打印最后的字母
		cout<<"B";
	else{
		if(k)
			cout<<"L";
		else
			cout<<"R"; 
	}
	cout<<endl;
} 
//8.设计一个算法把二叉树b所有的左、右子树进行交换，并用括号表示法输出该树。（要求不破坏原二叉树）
void Exchange(BT *B1)
{
	BT *t;///temp
	if(B1==NULL)
		return;
	else if(B1->lchild!=NULL||B1->rchild!=NULL)
	{
		t=B1->lchild;
		B1->lchild=B1->rchild;
		B1->rchild=t;
	}
	Exchange(B1->lchild);
	Exchange(B1->rchild);	
}
void Displaybtree(BT *B1){
	if(B1!=NULL)
	{
		cout<<B1->data;
		if(B1->lchild!=NULL||B1->rchild!=NULL)
		{
			cout<<"(";
			Displaybtree(B1->lchild);
			if(B1->rchild!=NULL)
				cout<<",";
			Displaybtree(B1->rchild);
			cout<<")";
		}
	}
}
//我的理解
//有两种，叶子和叶子（根的左右最深的相加不就是了吗？）
//叶子和根（这个很简单，就是深度最深的那个叶子））//但其实是错的，因为左树可以很长，所以我们的算法是寻找 共同祖先，然后相减
//不过实现起来比较棘手，就会错很多，后面请教大佬才发现（/*我蒟蒻的*/）
//这个第一步是先找叶子节点
void Findleaves(BT *B1,char a[],int &i)//a用来存节点，为了找到叶子结点
{
	if(!B1)//为了高级
		return;
	else 
	{
		if(!B1->lchild&&!B1->rchild)
			a[++i]=B1->data;	
		Findleaves(B1->lchild,a,i);
		Findleaves(B1->rchild,a,i);
	}
}
//第二部
//上一题的寻找共同祖先
bool Findallparent(BT *B1,ch str,stack<ch>&s1)
{
	if(B1==NULL)
		return false;
	s1.push(B1->data);
	if(B1->data==str)//为什么这样子，根据题目提示，本身也可以是祖先，所以我们把本身也压入.
		return true;//找到了就结束
	bool flag=Findallparent(B1->lchild,str,s1);//没搜索到本点就继续
	if(flag)
		return true;//如果在左支找到了，退出
	flag=Findallparent(B1->rchild,str,s1);//否则右支
	if(flag)
		return true;
	s1.pop();//没找到就回溯
	return false;
}
ch Findsameparent(BT *B1,ch str1,ch str2)
{
	stack<ch> s1,s2;
	Findallparent(B1,str1,s1);
	Findallparent(B1,str2,s2);
	int p1=s1.size(),p2=s2.size();
	if(p1>p2)//令两栈位于同一层
	{
		int n=p1-p2;
		while(n){
			s1.pop();
			n--;
		}
	}
	else
	{
		int n=p2-p1;
		while(n){
			s2.pop();
			n--;
		}
	}
	while(s1.top()!=s2.top())
	{
		s1.pop();s2.pop();
		if(s1.top()==s2.top())
			return s1.top();
	}
	if(s1.top()==s2.top())
		return s1.top();
	return 0;
}
map<char,int>trees;//储存每个结点的深度
void treedeep(BT* B1,int deep){
	if(B1){
		trees[B1->data]= deep;//求出每个结点的深du
		treedeep(B1->lchild,deep+1);
		treedeep(B1->rchild,deep+1);
	}
}
void Displaynode(BT *B1)
{
	ch str1,str2;//存储最终答案
	char a[MAX];
	int num=0;
	Findleaves(B1,a,num);//把所有叶子记录在a中
	treedeep(B1,1);//计算所有节点的深度
	a[++num]=B1->data;//加上根节点
	int max=0;
	for(int i=1;i<=num;i++)//遍历
	{
		for(int j=1;j<=num;j++){
			if(i==j)//不和自己比
				continue;
			char lcp=Findsameparent(B1,a[i],a[j]);//两个叶子的共同祖先
			int len=trees[a[i]]+trees[a[j]]-2*trees[lcp];//计算路径长度
			if(len>max)
			{
				max=len;
				str1=a[i];
				str2=a[j];
			}
		}
	}
	cout<<str1<<" "<<str2<<endl;
}

int main()
{
	int n;BT *B1;
	B1=new BT;ch a[MAX];
	cout<<"请选择您要测试的样例（输入1或2）";
	cin>>n;cout<<endl;
	if(n==1){
		cout<<"1.括号表示法表示这个树(样例一)：A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))"<<endl<<endl;
		strcpy(a,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I))");
	}
	else if(n==2){
		cout<<"1.括号表示法表示这个树（样例二）：A(B(D(,G),),C(E,F))"<<endl<<endl;
		strcpy(a, "A(B(D(,G),),C(E,F))");
	}
	else
	{
		cout<<"WARNING:what are you doing?"<<endl<<endl<<"输入1或2，ok？"<<endl<<endl;//防伪标识
		return 1;
	}
	CreatBtree(B1,a);
	cout<<"1:先序遍历输出该树（带\"^\"标志):";Predisplay(B1);cout<<endl<<endl;
	cout<<"2:中序遍历输出该树（带\"^\"标志):";Indisplay(B1);cout<<endl<<endl;
	cout<<"3:后序遍历输出该树（带\"^\"标志):";Postdisplay(B1);cout<<endl<<endl;
	cout<<"4:层次遍历输出该树（带\"^\"标志):";Picdisplay(B1);cout<<endl<<endl;
	cout<<"5:该树的先序凹入表表示法:"<<endl;Pre(B1,0,1);cout<<endl<<endl;
	cout<<"6:该树的中序凹入表表示法:"<<endl;In(B1,0,1);cout<<endl<<endl;
	cout<<"7:该树的后序凹入表表示法:"<<endl;Post(B1,0,1);cout<<endl<<endl;
	cout<<"8:现在交换二叉树所有的左、右子树，输出为括号表示法：  ";Exchange(B1);
	Displaybtree(B1);cout<<endl<<endl;
	cout<<"9:该树相隔最远的一对结点: ";Displaynode(B1);
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

PWM 开发舵机SG90-硬件舵机实战

PWM 开发舵机SG90-硬件舵机实战

1.PWM&#xff0c;英文名Pulse Width Modulation&#xff0c;是脉冲宽度调制缩写&#xff0c;它是通过对一系列脉冲的宽度进行调制&#xff0c;等效出所需要的波形&#xff08;包含形状以及幅值&#xff09;&#xff0c;对模拟信号电平进行数字编码&#xff0c;也就是说通过调节…
阅读更多...
hadoop学习---基于Hive的数仓搭建增量信息拉链表的实现

hadoop学习---基于Hive的数仓搭建增量信息拉链表的实现

拉链表就是SCD2&#xff0c;它的优点是即满足了反应数据的历史状态&#xff0c;又能在最大程度上节省存储。 拉链表的实现需要在原始字段基础上增加两个新字段&#xff1a; start_time(表示该条记录的生命周期开始时间——周期快照时的状态)end_time(该条记录的生命周期结束时…
阅读更多...
JSP合同信息管理系统参考论文（论文 + 源码）

JSP合同信息管理系统参考论文（论文 + 源码）

【免费】JSP合同信息管理系统.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89273651JSP合同信息管理系统 摘要 随着信息科学技术的飞速发展&#xff0c;人们逐渐意识到对信息管理软件的运用可以使日常工作更加方便、快捷和高效。论文详细论述了公司合同管理系…
阅读更多...
Mysql 8.0 -- 最新版本安装（保姆级教程）

Mysql 8.0 -- 最新版本安装（保姆级教程）

Mysql 8.0 -- 最新版本安装&#xff08;保姆级教程&#xff09; ​​ 一&#xff0c;下载Mysql数据库&#xff1a; 官网链接&#xff1a;https://www.mysql.com/downloads/ 二&#xff0c;安装Mysql: 三&#xff0c;找到Mysql安装目录&#xff1a; 找到mysql安装目录&#xf…
阅读更多...
在k8s中安装Grafana并对接Prometheus，实现k8s集群监控数据的展示

在k8s中安装Grafana并对接Prometheus，实现k8s集群监控数据的展示

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《Grafana&#xff1a;让数据说话的魔术师》 &#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、引言 1、Grafana简介 2、Grafana的重要性与影响力 …
阅读更多...
C进阶--自定义类型

C进阶--自定义类型

自定义类型 1. 结构体1.1. 结构的基本知识1.2 结构的声明1.3 特殊的声明1.4 结构的自引用1.5 结构体变量的定义和初始化1.6 结构体内存对齐结构体的大小练习结构体对齐规则为什么存在内存对齐? 1.7 修改默认对齐数1.8 结构体传参 2. 位段2.1 什么是位段2.2 位段的内存分配2.3 …
阅读更多...
MWeb Pro for Mac：功能强大的Markdown博客编辑器

MWeb Pro for Mac：功能强大的Markdown博客编辑器

MWeb Pro for Mac是一款功能强大的Markdown博客编辑器&#xff0c;专为Mac用户设计&#xff0c;提供了一站式的博客写作和发布体验。这款软件不仅支持Markdown语法&#xff0c;还提供了丰富的编辑和排版功能&#xff0c;让用户能够轻松创建出精美的博客内容。 MWeb Pro的即时预…
阅读更多...
笔试强训Day16 字符串 基础算法 双指针

笔试强训Day16 字符串 基础算法 双指针

QR6 字符串替换 题目链接&#xff1a;字符串替换_牛客题霸_牛客网 (nowcoder.com) 思路&#xff1a;简单的字符串操作。 AC code&#xff1a; class StringFormat { public:string formatString(string A, int n, vector<char> arg, int m) {string ans;int pos 0;f…
阅读更多...
【Qt】按钮类控件

【Qt】按钮类控件

文章目录 1 :peach:Push Button:peach:2 :peach:Radio Buttion:peach:3 :peach:Check Box:peach:4 :peach:Tool Button:peach: 1 &#x1f351;Push Button&#x1f351; 使⽤ QPushButton 表⽰⼀个按钮&#xff0c;这也是当前我们最熟悉的⼀个控件了&#xff0c;QPushButton …
阅读更多...
论文阅读：《Sequence can Secretly Tell You What to Discard》，减少推理阶段的 kv cache

论文阅读：《Sequence can Secretly Tell You What to Discard》，减少推理阶段的 kv cache

目前各类大模型都支持长文本&#xff0c;例如 kimi chat 以及 gemini pro&#xff0c;都支持 100K 以及更高的上下文长度。但越长的上下文&#xff0c;在推理过程中需要存储的 kv cache 也越多。假设&#xff0c;数据的批次用 b 表示&#xff0c;输入序列的长度仍然用 s 表示&a…
阅读更多...
3.栈和队列（汇总版）

3.栈和队列（汇总版）

目录 1.栈&#xff08;一端插和删&#xff09; 2.队列&#xff08;一端插另一段删&#xff09; 2.1队列的概念及结构 2.2 队列的实现 队列的接口 1.初始化队列 2.销毁队列 3.插入元素 4.出队列&#xff08;头删&#xff09; 5.访问对头 6.访问队尾 7.判断队列是否为…
阅读更多...
基于springboot实现的疫情网课管理系统

基于springboot实现的疫情网课管理系统

开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven…
阅读更多...
证明力引导算法forceatlas2为什么不是启发式算法

证明力引导算法forceatlas2为什么不是启发式算法

一、基本概念 吸引力 F a ( n i ) ∑ n j ∈ N c t d ( n i ) ω i , j d E ( n i , n j ) V i , j \displaystyle \bm{F}_a(n_i) \sum_{n_j \in \mathcal{N}_{ctd}(n_i)} \omega_{i,j} \; d_E(n_i,n_j) \bm{V}_{i,j} Fa​(ni​)nj​∈Nctd​(ni​)∑​ωi,j​dE​(ni​,nj​…
阅读更多...
【StarRocks系列】 Trino 方言支持

【StarRocks系列】 Trino 方言支持

我们在之前的文章中&#xff0c;介绍了 Doris 官方提供的两种方言转换工具&#xff0c;分别是 sql convertor 和方言 plugin。StarRocks 目前同样也提供了类似的方言转换功能。本文我们就一起来看一下这个功能的实现与 Doris 相比有何不同。 一、Trino 方言验证 我们可以通过…
阅读更多...
C语言 | Leetcode C语言题解之第73题矩阵置零

C语言 | Leetcode C语言题解之第73题矩阵置零

题目&#xff1a; 题解&#xff1a; void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {int m matrixSize;int n matrixColSize[0];int flag_col0 false;for (int i 0; i < m; i) {if (!matrix[i][0]) {flag_col0 true;}for (int j 1; j < n; j…
阅读更多...
C++:多继承虚继承

C++:多继承虚继承

在C中&#xff0c;虚继承&#xff08;Virtual Inheritance&#xff09;是一种特殊的继承方式&#xff0c;用于解决菱形继承&#xff08;Diamond Inheritance&#xff09;问题。菱形继承指的是一个类同时继承自两个或更多个具有共同基类的类&#xff0c;从而导致了多个实例同一个…
阅读更多...
20240507最新 ubuntu20.04安装ros noetic

20240507最新 ubuntu20.04安装ros noetic

ubuntu20.04安装ros 主要参考博客 【ROS】在 Ubuntu 20.04 安装 ROS 的详细教程_ubuntu20.04安装ros-CSDN博客 出现问题 1.ubuntu20.04 更换清华源报错 ubuntu20.04 更换清华源报错_gvfs metadata is not supported. fallback to teplme-CSDN博客 &#xff1f;&#xff1f…
阅读更多...
汽车 - 什么是车轮抱死

汽车 - 什么是车轮抱死

车轮抱死分为两种情况&#xff0c;一种是车辆故障层面&#xff0c;另一种是驾驶过程中的物理现象。我们先来说最通俗的刹车车轮抱死吧。 刹车制动车轮抱死 车轮停止轴向转动就是抱死&#xff0c;有速度的情况下抱死车轮&#xff0c;如果车辆的惯性动能大于轮胎抓地力&#xff0…
阅读更多...
Springboot集成Mybatispuls操作mysql数据库-03

Springboot集成Mybatispuls操作mysql数据库-03

MyBatis-Plus&#xff08;简称MP&#xff09;是一个MyBatis的增强工具&#xff0c;在MyBatis的基础上只做增强而不做改变。它支持所有MyBatis原生的特性&#xff0c;因此引入MyBatis-Plus不会对现有的MyBatis构架产生任何影响。MyBatis-Plus旨在简化开发、提高效率&#xff0c;…
阅读更多...
基于FPGA的去雾算法

基于FPGA的去雾算法

去雾算法的原理是基于图像去模糊的原理&#xff0c;通过对图像中的散射光进行估计和去除来消除图像中的雾霾效果。 去雾算法通常分为以下几个步骤&#xff1a; 1. 导引滤波&#xff1a;首先使用导引滤波器对图像进行滤波&#xff0c;目的是估计图像中散射光的强度。导引滤波器…
阅读更多...
最新文章

Copyright @ 2022~2023