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

news/2024/11/25 14:03:09/

北邮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，不是9return 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;elsecout << 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;elsecout << 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;elsecout << 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;elsecout << 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运行效果：


http://www.ppmy.cn/news/82986.html

相关文章

深入理解 go sync.Waitgroup

深入理解 go sync.Waitgroup

本文基于 Go 1.19。 go 里面的 WaitGroup 是非常常见的一种并发控制方式&#xff0c;它可以让我们的代码等待一组 goroutine 的结束。 比如在主协程中等待几个子协程去做一些耗时的操作&#xff0c;如发起几个 HTTP 请求&#xff0c;然后等待它们的结果。 WaitGroup 示例 下面…
阅读更多...
msvcr110.dll丢失的解决方法，多种方法助你解决msvcr110.dll丢失

msvcr110.dll丢失的解决方法，多种方法助你解决msvcr110.dll丢失

当您在尝试打开某个程序或游戏时&#xff0c;可能会看到一个错误消息&#xff0c;提示您的计算机缺少msvcr110.dll文件。这是因为该文件是Microsoft Visual C Redistributable库的一部分&#xff0c;缺少它可能会导致应用程序无法正常运行。在本文中&#xff0c;我们将详细介绍…
阅读更多...
TS入门（TS类型有哪些？怎么使用？）

TS入门（TS类型有哪些？怎么使用？）

TS简介 TS&#xff08;TypeScript&#xff09;是一种由微软开发的开源编程语言&#xff0c;它是 JavaScript 的超集&#xff0c;能够为 JavaScript 添加静态类型检查和面向对象编程的特性。TS 可以在编译时进行类型检查&#xff0c;从而提高代码的可读性、可维护性和可靠性&am…
阅读更多...
LeetCode高频算法刷题记录7

LeetCode高频算法刷题记录7

文章目录 1. 下一个排列【中等】1.1 题目描述1.2 解题思路1.3 代码实现 2. 两数相加【中等】2.1 题目描述2.2 解题思路2.3 代码实现 3. 括号生成【中等】3.1 题目描述3.2 解题思路3.3 代码实现 4. 滑动窗口最大值【困难】4.1 题目描述4.2 解题思路4.3 代码实现 5. 最小覆盖子串…
阅读更多...
Go语言面试题--必会语法(1)

Go语言面试题--必会语法(1)

文章目录 1.下面这段代码输出什么&#xff1f;2.下面代码输出什么&#xff1f;3.同级文件的包名不允许有多个&#xff0c;是否正确&#xff1f;4.下面的代码有什么问题&#xff0c;请说明。 1.下面这段代码输出什么&#xff1f; func main() {count : 0for i : range [256]str…
阅读更多...
实车获取CANlog并回放分析-操作方法

实车获取CANlog并回放分析-操作方法

一、连接线束 1、找到obd接口&#xff0c;连接CAN盒子&#xff08;这里用的VN1639A&#xff09;&#xff0c;分别链接CANH 和CANL 2、CAN盒上的usb线连接电脑 二、 连接CANoe 1、新建一个CANoe工程 点击Logging 文件夹&#xff0c;修改log存放路径和名称&#xff0c;log格式…
阅读更多...
抖音seo源码开发，技术交付及故障。服务等响应

抖音seo源码开发，技术交付及故障。服务等响应

抖音seo源码开发、抖音seo源码部署、抖音seo源码开源交付及故障响应 什么是抖音SEO&#xff1f; 抖音SEO主要是指通过一系列优化措施&#xff0c;提高抖音短视频在抖音搜索结果页的排名&#xff0c;从而增加短视频曝光量和观看量的过程。SEO的实现需要涉及多个方面&#xff0c…
阅读更多...
Ansys Speos 2023 R1新功能 | Texture可视化纹理提升视觉感知

Ansys Speos 2023 R1新功能 | Texture可视化纹理提升视觉感知

Ansys Speos 2023 R1 新功能介绍 Ansys Speos 持续推动创新&#xff0c;为光学设计人员提供精确、高性能的仿真功能。2023 R1 新版本提供强大的功能&#xff0c;可加快结果生成速度、提高仿真精度并扩展与其他 Ansys 产品的互操作性。 更新Texture映射预览&#xff0c;为textur…
阅读更多...
最新文章

Copyright @ 2022~2023