数据结构OJ实验6-二叉树的遍历以及应用

A. DS二叉树—二叉树构建与遍历(不含框架)

题目描述

给定一颗二叉树的逻辑结构如下图,(先序遍历的结果,空树用字符‘#’表示,例如AB#C##D##),建立该二叉树的二叉链式存储结构,并输出该二叉树的先序遍历、中序遍历和后序遍历结果。

输入

第一行输入一个整数t,表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果,空树用字符‘#’表示,连续输入t行。

输出

输出每个二叉树的先序遍历、中序遍历和后序遍历结果。

样例查看模式 

正常显示查看格式

输入样例1

2
AB#C##D##
AB##C##

输出样例1

ABCD
BCAD
CBDA
ABC
BAC
BCA


AC代码

#include<iostream>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用!
	{
		char ch;
		cin >> ch;
		if (ch == '#')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new!
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.preorder();
		tt.midorder();
		tt.posorder();
	}
	return 0;
}

B. DS二叉树--叶子数量

题目描述

计算一颗二叉树包含的叶子结点数量。

提示:叶子是指它的左右孩子为空。

建树方法采用“先序遍历+空树用0表示”的方法,即给定一颗二叉树的先序遍历的结果为AB0C00D00,其中空节点用字符‘0’表示。则该树的逻辑结构如下图。

输入

第一行输入一个整数t,表示有t个测试数据

第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

输出

逐行输出每个二叉树的包含的叶子数量

样例查看模式 

正常显示查看格式

输入样例1 

3
AB0C00D00
AB00C00
ABC00D00E00

输出样例1

2
2
3

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        int index=0;
        int cnt=0;
        while(index<(int)s.length()-2)//注意长度范围
        {
            //使用左右两边都无来判断是不是叶子
            if(s[index]!='0'&&s[index+1]=='0'&&s[index+2]=='0')
            {
                index+=2;
                cnt++;
            }
            else index++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

C. DS二叉树——二叉树之父子结点

题目描述

给定一颗二叉树的逻辑结构如下图,(先序遍历的结果,空树用字符‘0’表示,例如AB0C00D00),建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点

输入

第一行输入一个整数t,表示有t个二叉树

第二行起,按照题目表示的输入方法,输入每个二叉树的先序遍历,连续输入t行

输出

第一行按先序遍历,输出第1个示例的叶子节点

第二行输出第1个示例中与叶子相对应的父亲节点

以此类推输出其它示例的结果

样例查看模式 

正常显示查看格式

输入样例1 

3
AB0C00D00
AB00C00
ABCD0000EF000

输出样例1

C D 
B A 
B C 
A A 
D F 
C E 

AC代码

#include<iostream>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用!
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new!
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		//按照先序遍历
		if (!n->l &&!n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		//按照后序遍历
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		//左右节点的父亲相同
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.child();
		tt.father();
	}
	return 0;
}

D. DS二叉树--层次遍历

题目描述

层次遍历二叉树,是从根结点开始遍历,按层次次序“自上而下,从左至右”访问树中的各结点。

建树方法采用“先序遍历+空树用0表示”的方法

建议使用队列结构实现,算法框架如下:

定义一个空白队列和一个树结点指针p

设T是指向根结点的指针变量,若二叉树为空,则返回;否则,令p=T,p入队,执行以下循环:

(1)队首元素出队到p;

(2)访问p所指向的结点; 

(3)p所指向的结点的左、右子结点依次入队。

(4)跳转步骤1循环,直到队列空为止

例如把上述算法中的访问操作定义为输出,算法结果就是把二叉树按层次遍历输出

输入

第一行输入一个整数t,表示有t个测试数据

第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

输出

逐行输出每个二叉树的层次遍历结果

样例查看模式 

正常显示查看格式

输入样例1 

2
AB0C00D00
ABCD00E000FG00H0I00

输出样例1

ABDC
ABFCGHDEI

AC代码

#include<iostream>
#include<queue>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用!
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new!
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		//按照先序遍历
		if (!n->l &&!n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		//按照后序遍历
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		//左右节点的父亲相同
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;//注意判断非空
			cout << t->data;
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.lerorder();
	}
	return 0;
}

E. DS树--二叉树高度

题目描述

给出一棵二叉树,求它的高度。

注意,二叉树的层数是从1开始

输入

第一行输入一个整数t,表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果,空树用字符‘0’表示,连续输入t行

输出

每行输出一个二叉树的高度

样例查看模式 

正常显示查看格式

输入样例1 

1
AB0C00D00

输出样例1

3

AC代码

#include<iostream>
#include<queue>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用!
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new!
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		//按照先序遍历
		if (!n->l &&!n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		//按照后序遍历
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		//左右节点的父亲相同
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
	int high(node* n)
	{
		if (!n)return 0;
		int lefth = high(n->l);
		int righth = high(n->r);
		return max(lefth, righth) + 1;
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;//注意判断非空
			cout << t->data;
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
	void gethigh()
	{
		cout << high(root) << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.gethigh();
	}
	return 0;
}

F. DS二叉树——二叉树之数组存储

题目描述

二叉树可以采用数组的方法进行存储,把数组中的数据依次自上而下,自左至右存储到二叉树结点中,一般二叉树与完全二叉树对比,比完全二叉树缺少的结点就在数组中用0来表示。,如下图所示

从上图可以看出,右边的是一颗普通的二叉树,当它与左边的完全二叉树对比,发现它比完全二叉树少了第5号结点,所以在数组中用0表示,同样它还少了完全二叉树中的第10、11号结点,所以在数组中也用0表示。

结点存储的数据均为非负整数

输入

第一行输入一个整数t,表示有t个二叉树

第二行起,每行输入一个数组,先输入数组长度,再输入数组内数据,每个数据之间用空格隔开,输入的数据都是非负整数

连续输入t行

输出

每行输出一个示例的先序遍历结果,每个结点之间用空格隔开

样例查看模式 

正常显示查看格式

输入样例1 

3
3 1 2 3
5 1 2 3 0 4
13 1 2 3 4 0 5 6 7 8 0 0 9 10

输出样例1

1 2 3 
1 2 4 3 
1 2 4 7 8 3 5 9 10 6 

提示

注意从数组位置和二叉树深度、结点位置进行关联,或者父子结点在数组中的位置存在某种管理,例如i, i+1, i/2,  i+1/2........或者2i, 2i+1.......仔细观察哦

AC代码

#include<iostream>
#include<vector>
using namespace std;
class tree
{
	vector<int>node;
	void pre(int idx)
	{
		if (idx>=node.size()||node[idx]==0)return;
		cout << node[idx] << " ";
		pre(2 * idx + 1);//左
		pre(2 * idx + 2);//右
	}
public:
	tree()
	{
		int n;
		cin >> n;
		node.resize(n);
		for (int i = 0; i < n; i++)cin >> node[i];
	}
	void preorder()
	{
		pre(0);//下标从0开始
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.preorder();
	}
	return 0;
}

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

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

相关文章

H266/VVC多样化视频编码工具概述

全景视频编码 全景视频&#xff1a; 具有360度全包围视角的球面视频。 全景视频编码&#xff1a; 包括H266在内的视频编码算法都是以平面视频为对象的&#xff0c;为了采用传统的视频编码编码算法&#xff0c;全景视频需要转换为平面视频&#xff0c;其中经纬图等角映射&#…

适用于 Windows 的免费U盘数据恢复方法详解

笔式驱动器&#xff08;Pen Drive&#xff09;是一种方便、小巧、便于携带的数据存储设备&#xff0c;也称为U盘、拇指驱动器、U盘等。“笔式驱动器”的名称来源于其外观&#xff0c;即体积小、体积小、方便携带。与传统笔相似&#xff0c;尽管它实际上并不能书写。 有几个功能…

如何把硬盘(分区)一分为二?重装系统的小伙伴不可不看

注意事项&#xff1a;本教程操作不当会导致数据丢失 请谨慎操作 请谨慎操作 请谨慎操作 前言 相信各位小伙伴都会切土豆吧&#xff0c;本教程就是教大家如何切土豆切得好的教程。 啊哈哈哈&#xff0c;开玩笑的。 比如你有一个D盘是200GB&#xff0c;想要把它变成两个100G…

3D空间漫游技术的日趋成熟,让博物馆数字化大放异彩!

随着科技的飞速发展&#xff0c;互联网已经成为人们生活中不可或缺的一部分。在这个数字化时代&#xff0c;博物馆也紧跟时代潮流&#xff0c;将传统的实体博物馆与现代科技相结合&#xff0c;诞生了一种全新的博物馆形式——3D线上博物馆。这种新型博物馆凭借其独特的魅力&…

vue组件scoped的作用 目的: 解决多个组件样式名相同, 冲突问题

在style上加入scoped属性, 就会在此组件的标签上加上一个随机生成的data-v开头的属性&#xff0c;下面一起来看一下&#xff0c;希望对大家有帮助。 vue组件-scoped作用 需求: p标签名选择器, 设置背景色 问题: 发现组件里的p和外面的p都生效了 解决: 给Pannel.vue组件里sty…

设计模式之单例模式的懒饿汉

懒汉式 说白了就是你不叫我我不动&#xff0c;你叫我我才动。 类初始化模式&#xff0c;也叫延迟占位模式。在单例类的内部由一个私有静态内部类来持有这个单例类的实例。因为在 JVM 中&#xff0c;对类的加载和类初始化&#xff0c;由虚拟机保证线程安全。 public class Singl…

一个H3C交换机周期性断网并自动恢复的排查案例

一个朋友发我一个H3C日志&#xff0c;这个交换机是汇聚层交换机&#xff0c;1和2口是trunk口&#xff0c;其它接口是access接口&#xff0c;17-21口据说接的都是监控、终端。日志里面看到大量的拓朴改变&#xff0c;好几个网口up、down的日志&#xff0c;怀疑是环路&#xff0c…

Vue3——element-plus表格组件怎样得到当前行的id

实现方法&#xff1a; <el-table-column property"address" label"操作" show-overflow-tooltip header-align"center" v-slot"scope"><el-button type"success" click"editBtn(scope.row.id)">编辑…

视频转音频软件哪个好? 11 个高效的视频转音频转换器分享

网络上拥有数百个值得观看和聆听的音乐视频。但要聆听喜爱的音乐&#xff0c;用户必须观看整个视频&#xff0c;即使只有音乐让他们兴奋。那么&#xff0c;如何从视频中提取音频呢&#xff1f;简单的答案是使用视频到音频转换器将视频转换为音频格式并将其保存在您的设备上以供…

pyqt6 + pycharm 搭建+使用入门

首先安装PyQt6和PyQt6-tools。使用如下命令&#xff1a; pip install PyQt6 PyQt6-tools 但是运行后会报如下错误&#xff1a; 这个时候按照提示执行命令升级pip即可 python.exe -m pip install --upgrade pip 配置pycharm&#xff1a; 打开pycharm&#xff0c;进入setting&am…

创建专业电子邮件签名:提升个人与品牌形象的实用指南

电子邮件签名乃是品牌建设中常被忽略的一环。试想一下&#xff0c;若名片只是普通的、手工切割的复印纸&#xff0c;上面用黑体打印着你的联系方式&#xff0c;那将是多么平凡无奇。这将显得廉价、乏味且不专业——这正是人们不愿如此的原因。相反&#xff0c;他们渴望让自己的…

每日一博 - 多租户技术及其三种数据存储策略

文章目录 概述应用程序隔离数据隔离小结 概述 多租户技术&#xff08;Multi-Tenant Technology&#xff09;是软件即服务&#xff08;SaaS&#xff09;架构中的一项核心技术&#xff0c;允许单一软件应用或服务同时服务于多个客户&#xff08;即“租户”&#xff09;&#xff…

[每周一更]-(第81期):PS抠图流程(扭扭曲曲的身份证修正)

应朋友之急&#xff0c;整理下思路&#xff0c;分享一下~~ 分两步走&#xff1a;先用磁性套索工具圈出要处理的图&#xff1b;然后使用透视剪裁工具&#xff0c;将扭曲的图片拉平即可&#xff1b;(macbook pro) 做事有规则&#xff0c;才能更高效;用什么工具&#xff0c;先列举…

大模型日报-20240105

骁龙888实时运行&#xff0c;美团、浙大等打造全流程移动端多模态大模型MobileVLM https://mp.weixin.qq.com/s/-KnewDBeCN7a1XPk22u9Pw MobileVLM 是一款专为移动设备设计的快速、强大和开放的视觉语言助手。它结合了面向移动设备的架构设计和技术&#xff0c;包括从头开始训练…

【激活函数】PReLU 激活函数

1、介绍 PReLU&#xff08;Parametric Rectified Linear Unit&#xff09;激活函数是ReLU&#xff08;Rectified Linear Unit&#xff09;激活函数的一种改进。它是由 He et al. 在 2015 年提出的&#xff0c;旨在解决ReLU激活函数的一些局限性。 # 定义 PReLU 激活函数 prelu…

从vue小白到高手,从一个内容管理网站开始实战开发第六天,登录功能后台功能设计--API项目中的登录实现(二),工厂模式创建数据库连接

一、回顾 在第五天的时候我们开始创建后台所以需项目,并创建项目所需要的相关实体类,具体内容没有掌握的小伙伴可以看点击下面的链接去学习。 从vue小白到高手,从一个内容管理网站开始实战开发第六天,登录功能后台功能设计--API项目中的登录实现(一)-CSDN博客文章浏览阅读…

记一次实战云渗透总结

点击星标&#xff0c;即时接收最新推文 云渗透思路 所谓的云渗透通常指SaaS或PaaS渗透&#xff0c;即将服务器端的某些服务搭建在云服务器上&#xff0c;源代码的开发、升级、维护等工作都由提供方进行。从原理上看&#xff0c;云渗透思路与传统渗透思路相差无几。站点必须由底…

竞赛练一练 第24期:NOC大赛每日一练,scratch题目刷题第3天,包含答案解析

023年NOC大赛创客智慧编程赛项图形化复赛模拟题一,包含答案解析 本次题目来源:NOC 大赛创客智慧编程赛项图形化复赛模拟题(一) 第一题: 制作一个生日贺卡小程序. 1.点击绿旗后蛋糕出现在 (0,-80) 的位置,大小为 100,造型为 cake-b2.当碰到鼠标指针时,将造型切换为 cak…

MyBatis 源码分析(四):反射模块

前言 上一篇我们了解了Mybatis解析器模块&#xff0c;MyBatis 源码分析&#xff08;三&#xff09;&#xff1a;解析器模块 本篇我们来了解反射模块。相比 parsing 包来说&#xff0c;reflection 包的代码量大概是 2-3 倍。当然&#xff0c;不要慌&#xff0c;都是比较简单的代…

CAN通信的基本原理与实现方法

一. CAN协议概念 1.1 CAN 协议简介 CAN 是控制器局域网络 (Controller Area Network) 的简称&#xff0c;它是由研发和生产汽车电子产品著称的德国 BOSCH 公司开发的&#xff0c;并最终成为国际标准(ISO11519以及ISO11898),是国际上应用最广泛的现场总线之一。差异点如下&…