北邮22信通:二叉树显示路径的两种方法 递归函数保存现场返回现场的实例

北邮22信通一枚~                           

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

获取更多文章  请访问专栏~

北邮22信通_青山如墨雨如画的博客-CSDN博客

一.讲解

要想实现二叉树的路径显示,我们要按照先后顺序做这样几件事:

1.判断是否能够找到路径;

2.如果能找到路径,则将路径存储起来,如果不能找到路径,则返回查询失败的信息;

3.将路径按照一定的方法打印出来;

1.递归详解:是否能够找到路径并将找到的可行路径存储起来的实现函数

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (stl_search_path(target, r->leftchild, stk))
		return true;
	else if (stl_search_path(target, r->rightchild, stk))
		return true;
	stk.pop();
	return false;
}

         首先我们向这个函数中传入3个参数,分别是待查找的目标,二叉树的根节点,一个空栈(用来存储路径);实现的具体过程运用了递归思想:对整个查找过程中的某次查找如果父节点数据域就是要查找的目标,返回真值;如果沿着他的左孩子找下去能找到目标,返回真值,如果沿着他的右孩子找下去能找到目标,返回真值。如果父节点不是目标并且沿着左孩子右孩子都找不到目标的话,弹出父节点返回假值。

这里用例子重新讲解递归函数保存现场返回现场的运行过程:

如上图,我们要查找到结点6的路径:

按照函数编写顺序:

1首先入栈,判断1不是6(函数第5、6行),继续执行;

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)//现在是1,不是9
		return true;//执行完毕,继续向下执行;
}

执行到第7行,需要判断沿着1的左孩子2能不能找到合适路径,保存现场;

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (stl_search_path(target, r->leftchild, stk))
		return true;
    /*
    执行到这一步,需要重新判断stl_search_path(target, r->leftchild, stk)
    是否为真值;
    函数保存现场不继续向下执行,将r->leftchild==2作为参数替代r==1,重新开始执行函数;
    */
}

重新从第一行开始执行函数,2入栈,2不是6,向下执行;

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;//r==2不是9,继续向下执行;
}

执行到第7行,需要判断沿着2的左孩子4能不能找到合适路径,保存现场;

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (stl_search_path(target, r->leftchild, stk))
		return true;
    /*
    执行到这一步,需要重新判断stl_search_path(target, r->leftchild, stk)
    是否为真值;
    函数保存现场不继续向下执行,将r->leftchild->leftchild==4作为参数
    替代r->leftchild==2,重新开始执行函数;
    */
}

重新从第一行开始执行函数,4入栈,4不是6,向下执行;

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (stl_search_path(target, r->leftchild, stk))
		return true;
    /*
    执行到这一步,需要重新判断stl_search_path(target, r->leftchild, stk)
    是否为真值;
    函数保存现场不继续向下执行,
    将r->leftchild->leftchild->leftchild==NULL作为参数
    替代r->leftchild->leftchild==4,重新开始执行函数;
    */
}

发现4的左孩子是空,返回假值;

返回上一级现场,执行函数第8、9行,需要判断沿着4的右孩子能不能找到合适路径,保存现场;

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, 
    stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (stl_search_path(target, r->leftchild, stk))
		return true;
	else if (stl_search_path(target, r->rightchild, stk))
		return true;
    /*
    执行到这一步,需要重新判断stl_search_path(target, r->leftchild, stk)
    是否为真值;
    函数保存现场不继续向下执行,
    将r->leftchild->leftchild->rightchild==NULL作为参数
    替代r->leftchild->leftchild==4,重新开始执行函数;
    */
}

右孩子为空;

返回上一级现场,判断沿着2的右孩子5能不能找到可行的路径,保存现场,以此类推……

示意图如下:

2.打印路径的函数

template<class temp>
void bintree<temp>::stl_node_root_path(temp target)
{
	stack<binnode<temp>>stk;
	stl_search_path(target, this->root, stk);
	if (stk.empty())
		cout << target << "未能找到目标" << endl;
	else
	{
		cout << target << "结点到根节点的路径为:" << endl;
		binnode<temp>out;
		while (!stk.empty())
		{
			out = stk.top();
			if (stk.size() == 1)
				cout << out.data;
			else
				cout << out.data << "->";
			stk.pop();
		}
		cout << endl;
	}
}

 对于给定的二叉树,首先调用上面讲解过的函数,如果有可行路径就将可行路径通过函数存储到本函数的栈空间中,然后通过控制条件输出,最终可以实现打印的效果。

 3.另一种存储方式

使用模板类定义的栈存储也未尝不可。

代码如下:

template<class temp>
void bintree<temp>::linkstack_node_root_path(temp target)
{
	linkstack<binnode<temp>>stk;
	linkstack_search_path(target, this->root, stk);
	if (stk.empty())
		cout << target << "未能找到目标" << endl;
	else
	{
		cout << target << "结点到根节点的路径为:" << endl;
		binnode<temp>out;
		while (!stk.empty())
		{
			out = stk.gettop();
			if (stk.getsize() == 1)
				cout << out.data;
			else
				cout << out.data << "->";
			stk.pop();
		}
		cout << endl;
	}
}
template<class temp>
bool bintree<temp>::linkstack_search_path(temp target, binnode<temp>*& r, linkstack<binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (linkstack_search_path(target, r->leftchild, stk))
		return true;
	else if (linkstack_search_path(target, r->rightchild, stk))
		return true;
	stk.pop();
	return false;
}

二.完整代码:

2.1使用STL栈实现:

#include<iostream>
#include<stack>
using namespace std;

class student
{
private:
	int ID;
	string name;
public:
	int existence;
	student()
	{
		this->ID = 0;
		this->name = "unknown name";
		this->existence = 0;
	}
	student(int ID, string name)
	{
		this->ID = ID;
		this->name = name;
		this->existence = 1;
	}
	bool operator == (student& s)
	{
		return ((this->ID == s.ID) && (this->name == s.name)) ? true : false;
	}
	friend ostream& operator<<(ostream& output, student& s)
	{
		output << "\"" << s.ID << " " << s.name << "\"";
		return output;
	}
};

template<class temp>
struct binnode
{
	temp data;
	binnode* leftchild;
	binnode* rightchild;
};

template<class temp>
class bintree
{
private:
	void create(binnode<temp>*& r, temp data[], int i, int n);
	void release(binnode<temp>* r);
public:
	binnode<temp>* root;
	bintree(temp data[], int n);
	void stl_node_root_path(temp target);
	bool stl_search_path(temp target, binnode<temp>*& r, stack <binnode<temp>>& stk);
	~bintree();
};

template<class temp>
void bintree<temp>::create(binnode<temp>*& r, temp data[], int i, int n)
{
	if (i <= n && data[i - 1].existence != 0)
	{
		r = new binnode<temp>;
		r->data = data[i - 1];
		r->leftchild = NULL;
		r->rightchild = NULL;
		create(r->leftchild, data, 2 * i, n);
		create(r->rightchild, data, 2 * i + 1, n);

	}
}

template<class temp>
bintree<temp>::bintree(temp data[], int n)
{
	create(this->root, data, 1, n);
}

template<class temp>
void bintree<temp>::release(binnode<temp>* r)
{
	if (r != NULL)
	{
		release(r->leftchild);
		release(r->rightchild);
		delete r;
	}
}

template<class temp>
bintree<temp>::~bintree()
{
	release(this->root);
}

template<class temp>
void bintree<temp>::stl_node_root_path(temp target)
{
	stack<binnode<temp>>stk;
	stl_search_path(target, this->root, stk);
	if (stk.empty())
		cout << target << "未能找到目标" << endl;
	else
	{
		cout << target << "结点到根节点的路径为:" << endl;
		binnode<temp>out;
		while (!stk.empty())
		{
			out = stk.top();
			if (stk.size() == 1)
				cout << out.data;
			else
				cout << out.data << "->";
			stk.pop();
		}
		cout << endl;
	}
}

template<class temp>
bool bintree<temp>::stl_search_path(temp target, binnode<temp>*& r, stack <binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (stl_search_path(target, r->leftchild, stk))
		return true;
	else if (stl_search_path(target, r->rightchild, stk))
		return true;
	stk.pop();
	return false;
}

int main()
{
	system("color 0A");
	student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };
	bintree<student>tree(stu, 5);

	student stu1(1, "zhang"), stu2(5, "liu"), stu3(6, "cao");
	tree.stl_node_root_path(stu1);
	tree.stl_node_root_path(stu2);
	tree.stl_node_root_path(stu3);

	return 0;
}

2.2使用模板类定义的栈实现:

#include<iostream>
using namespace std;

class student
{
private:
	int ID;
	string name;
public:
	int existence;
	student()
	{
		this->ID = 0;
		this->name = "unknown name";
		this->existence = 0;
	}
	student(int ID, string name)
	{
		this->ID = ID;
		this->name = name;
		this->existence = 1;
	}
	bool operator == (student& s)
	{
		return ((this->ID == s.ID) && (this->name == s.name)) ? true : false;
	}
	friend ostream& operator<<(ostream& output, student& s)
	{
		output << "\"" << s.ID << " " << s.name << "\"";
		return output;
	}
};
//二叉树声明部分
template<class temp>
struct binnode;
//栈
template <class temp>
struct node
{
	temp data;
	node<temp>* next;
};

template <class temp>
class linkstack
{
public:
	binnode<temp>* r;
	int tag;
	linkstack() { top = NULL; }
	~linkstack();
	void push(temp x);
	temp pop();
	temp gettop();
	int getsize();
	bool empty()
	{
		return top == NULL ? true : false;
	}
private:
	node<temp>* top;
};

template <class temp>
void linkstack<temp>::push(temp x)
{
	node<temp>* p = new node<temp>;
	p->data = x;
	p->next = this->top;
	this->top = p;
}

template<class temp>
temp linkstack<temp>::pop()
{
	if (empty())throw "下溢";
	temp x = this->top->data;
	node<temp>* p = this->top;
	this->top = this->top->next;
	delete p;
	return x;
}

template<class temp>
linkstack<temp>::~linkstack()
{
	while (this->top != NULL)
	{
		node<temp>* p = this->top;
		this->top = this->top->next;
		delete p;
	}
}

template<class temp>
temp linkstack<temp>::gettop()
{
	if (empty())throw"下溢";
	return this->top->data;
}

template<class temp>
int linkstack<temp>::getsize()
{
	int num = 0;
	node<temp>* p = this->top;
	while (p != NULL)
	{
		num++;
		p = p->next;
	}
	return num;
}


template<class temp>
struct binnode
{
	temp data;
	binnode* leftchild;
	binnode* rightchild;
};

template<class temp>
class bintree
{
private:
	void create(binnode<temp>*& r, temp data[], int i, int n);
	void release(binnode<temp>* r);
public:
	binnode<temp>* root;
	bintree(temp data[], int n);
	void linkstack_node_root_path(temp target);
	bool linkstack_search_path(temp target, binnode<temp>*& r, linkstack<binnode<temp>>& stk);
	~bintree();
};

template<class temp>
void bintree<temp>::create(binnode<temp>*& r, temp data[], int i, int n)
{
	if (i <= n && data[i - 1].existence != 0)
	{
		r = new binnode<temp>;
		r->data = data[i - 1];
		r->leftchild = NULL;
		r->rightchild = NULL;
		create(r->leftchild, data, 2 * i, n);
		create(r->rightchild, data, 2 * i + 1, n);

	}
}

template<class temp>
bintree<temp>::bintree(temp data[], int n)
{
	create(this->root, data, 1, n);
}

template<class temp>
void bintree<temp>::release(binnode<temp>* r)
{
	if (r != NULL)
	{
		release(r->leftchild);
		release(r->rightchild);
		delete r;
	}
}

template<class temp>
bintree<temp>::~bintree()
{
	release(this->root);
}

template<class temp>
void bintree<temp>::linkstack_node_root_path(temp target)
{
	linkstack<binnode<temp>>stk;
	linkstack_search_path(target, this->root, stk);
	if (stk.empty())
		cout << target << "未能找到目标" << endl;
	else
	{
		cout << target << "结点到根节点的路径为:" << endl;
		binnode<temp>out;
		while (!stk.empty())
		{
			out = stk.gettop();
			if (stk.getsize() == 1)
				cout << out.data;
			else
				cout << out.data << "->";
			stk.pop();
		}
		cout << endl;
	}
}

template<class temp>
bool bintree<temp>::linkstack_search_path(temp target, binnode<temp>*& r, linkstack<binnode<temp>>& stk)
{
	if (r == NULL)
		return false;
	stk.push(*r);
	if (r->data == target)
		return true;
	else if (linkstack_search_path(target, r->leftchild, stk))
		return true;
	else if (linkstack_search_path(target, r->rightchild, stk))
		return true;
	stk.pop();
	return false;
}

int main()
{
	system("color 0A");
	student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };
	bintree<student>tree(stu, 5);

	student stu1(1, "zhang"), stu2(5, "liu"), stu3(6, "cao");

	tree.linkstack_node_root_path(stu1);
	tree.linkstack_node_root_path(stu2);
	tree.linkstack_node_root_path(stu3);
	return 0;
}

2.3运行效果:

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

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

相关文章

每日一题——三数之和(双指针)

每日一题 三数之和 题目链接 思路 解析函数原型 首先我们来看一下题目给的函数原型&#xff1a; int** threeSum(int* nums, int numsSize, int* returnSize, int**returnColumnSizes)题目要求我们返回一个二维数组&#xff0c;数组的行数代表着存在多少个满足条件的三元组&…

基于SVM的鸢尾花数据集回归分析

目录 1. 作者介绍2. SVM支持向量机算法2.1 鸢尾花数据集2.2 鸢尾花数据集可视化2.2.1 散点图2.2.2 箱型图2.2.3 三维散点图&#xff08;3D&#xff09; 3. SVM算法实现3.1 完整代码3.2 运行结果3.3 问题与分析 1. 作者介绍 张佳伦&#xff0c;男&#xff0c;西安工程大学电子信…

Cuda | Cudnn安装及其配置

文章目录 &#x1f449;引言&#x1f48e;一、Cuda安装1 选择Cuda版本2下载及运行安装程序3 测试 二、Cudnn安装1、进入官网下载对应cuda版本的cudnn2、下载好相应版本并进行解压安装3、解压完成后4、测试 &#x1f449;引言&#x1f48e; 学习的最大理由是想摆脱平庸&#xf…

stable diffusion图片资源分享和模型推荐,好用的模型有哪些呢?

前言 这篇文章主要是分享我的图片和推荐一些好用的模型&#xff0c;模型不在多在于精&#xff0c;基于几个好的大模型适当下载一下LORA模型&#xff0c;就能画出非常好的图片&#xff0c;多话不说 图片分享 简单展示 详情请看&#xff1a;https://space.bilibili.com/109890…

Linux基础篇 Ubuntu 22.04的环境安装-02

目录 一、资料的获取 二、安装虚拟机 三、安装Ubuntu过程 四、注意事项 一、资料的获取 1.通过官方网站下载 Ubuntu系统下载 | Ubuntuhttps://cn.ubuntu.com/download2.下载桌面板即可 3.选择下载的版本 二、安装虚拟机 1.创建新的虚拟机 2.选择自定义安装 3.硬件兼容性选…

Es elasticsearch 十九 kibana 可视化配置图表 及功能 集群部署

目录 Es kibana 可视化 下载zip 解压 bin/kibana.bat 启动 管理索引管理 吧logstash 存进来的数据 按照 xxx-* 方式 保存索引模式 通过 discove 配置可视化界面 图表数据实时刷新 时序图配置 饼图配置 表格数据配置 添加仪表盘 图表样例 使用后模拟绘制方法好看些 …

pandas数据预处理

pandas数据预处理 pandas及其数据结构pandas简介Series数据结构及其创建DataFrame数据结构及其创建 利用pandas导入导出数据导入外部数据导入数据文件 导出外部数据导出数据文件 数据概览及预处理数据概览分析利用DataFrame的常用属性利用DataFrame的常用方法 数据清洗缺失值处…

什么是Odoo ERP:部署方式、业务集成、成本投入、发展与未来

ERP部署的类型 如何部署ERP 系统&#xff1f;通过多年的发展&#xff0c;ERP系统的部署方式更加多样化&#xff0c;包括公有云或私有云部署、本地部署或整合不同环境的混合部署场景&#xff0c;企业可根据自身条件与应用场景加以选择。下面介绍了每种部署模式的主要优势&#…

动态规划-硬币排成线

动态规划-硬币排成线 1 描述2 样例2.1 样例 1:2.2 样例 2:2.3 样例 3: 3 算法解题思路及实现3.1 算法解题分析3.1.1 确定状态3.1.2 转移方程3.1.3 初始条件和边界情况3.1.4 计算顺序 3.2 算法实现3.2.1 动态规划常规实现3.2.2 动态规划滚动数组 该题是lintcode的第394题&#x…

在简历上写了“精通”后,我差点被面试官问到窒息....

前言 如果有真才实学&#xff0c;写个精通可以让面试官眼前一亮&#xff01; 如果是瞎写&#xff1f;基本就要被狠狠地虐一把里&#xff01; 最近在面试&#xff0c;我现在十分后悔在简历上写了“精通”二字… 先给大家看看我简历上的技能列表&#xff1a; 熟悉软件测试理…

基于相位共轭法的散射聚焦成像研究-Matlab代码

▒▒本文目录▒▒ 一、引言二、相位共轭法散射聚焦成像Matlab仿真三、参考文献四、Matlab程序开发与实验指导 一、引言 一直以来&#xff0c;研究人员致力于分析造成散射的原因、随机介质性质以及各种散射光的特征&#xff0c;并且研究透过散射介质成像。1990年&#xff0c;I.…

基于VMD-SSA-LSTM的多维时序光伏功率预测

目录 1 主要内容 变分模态分解(VMD) 麻雀搜索算法SSA 长短期记忆网络LSTM 2 部分代码 3 程序结果 4 下载链接 1 主要内容 之前分享了预测的程序基于LSTM的负荷和可再生能源出力预测【核心部分复现】&#xff0c;该程序预测效果比较好&#xff0c;并且结构比较清晰&#x…

新能源汽车充电桩的建设及优化分析

安科瑞虞佳豪 新能源汽车充电桩在经历了几年的发展之后&#xff0c;总体情况是在持续走好的&#xff0c;并且充电桩的建设相较于以往有了很大的普及度和安全度&#xff0c;这对新能源汽车车主是一个好事&#xff0c;也鼓励了更多人选择买新能源汽车&#xff0c;但这并不是说新…

如何通过控制点或地物点生产地方坐标系的倾斜摄影三维模型数据?

如何通过控制点或地物点生产地方坐标系的倾斜摄影三维模型数据&#xff1f; 要生成地方坐标系的倾斜摄影三维模型数据&#xff0c;需要进行以下步骤&#xff1a; 1、收集影像数据 首先需要采集大量的航空影像和地面影像&#xff0c;以构建真实世界中的物体模型。这些影像可以…

一文让你明白软件测试该怎样入门?

我认为入门软件测试需要四个方面的知识or技能&#xff0c;它们是&#xff1a;业务知识、职业素养、基础知识、技术知识。 职业素养是一切的根基&#xff0c;因为人在职场就必须拥有必要的职业素养&#xff0c;软件测试工程师也不例外。基础知识和技术知识是两大支柱&#xff0…

使用外部工具横向移动

Smbexe、Psexec Psexec PsExec是一种轻巧的telnet代替品&#xff0c;可让您在其他系统上执行进程&#xff0c;并为控制台应用提供完整的交互性&#xff0c;无需手动安装客户端软件。 原理&#xff1a; 1、ipc$连接&#xff0c;释放Psexesvc.exe 2、OpenSCManager打开受害者…

不甘做小弟,JS时间对象又在搞事情!(上)

关注“大前端私房菜”微信公众号&#xff0c;回复暗号【面试宝典】即可免费领取107页前端面试题。 Date Date 是 js 的一个内置对象&#xff0c;也叫内置构造函数。提供了一堆的方法帮助我们更方便的操作时间 创建时间对象&#xff1a;new Date() 获取时间对象&#xff1a;ne…

Flask-蓝图

1、使用步骤&#xff1a; 创建蓝图 blue Blueprint("myblue01", __name__) 使用蓝图装饰视图函数 blue.route(/) def index():return index 将蓝图注册到app中 from appdemo_blueprint import blue app.register_blueprint(blue) 2、以包的形式使用蓝图 <…

Java版企业电子招标采购系统源代码Spring Boot + 二次开发 + 前后端分离 构建企业电子招采平台之立项流程图

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及…

2023年4月和5月随笔

1. 回头看 为了不耽误学系列更新&#xff0c;4月随笔合并到5月。 日更坚持了151天&#xff0c;精读完《SQL进阶教程》&#xff0c;学系统集成项目管理工程师&#xff08;中项&#xff09;系列更新完成。 4月和5月两月码字114991字&#xff0c;日均码字数1885字&#xff0c;累…