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

    北邮22信通一枚~                           

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

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

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

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

    目录

    一.讲解

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

    2.打印路径的函数

     3.另一种存储方式

    二.完整代码：

    2.1使用STL栈实现：

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

    2.3运行效果：

     

    一.讲解

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

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

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

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

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

    1. template<class temp>
    2. bool bintree::stl_search_path(temp target, binnode*& r, 
    3.     stack >& stk)
    4. {
    5. 	if (r == NULL)
    6. 		return false;
    7. 	stk.push(*r);
    8. 	if (r->data == target)
    9. 		return true;
    10. 	else if (stl_search_path(target, r->leftchild, stk))
    11. 		return true;
    12. 	else if (stl_search_path(target, r->rightchild, stk))
    13. 		return true;
    14. 	stk.pop();
    15. 	return false;
    16. }

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

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

    如上图，我们要查找到结点6的路径：

    按照函数编写顺序：

    1首先入栈，判断1不是6（函数第5、6行），继续执行；

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

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

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

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

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

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

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

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

    1. template<class temp>
    2. bool bintree::stl_search_path(temp target, binnode*& r, 
    3.     stack >& stk)
    4. {
    5. 	if (r == NULL)
    6. 		return false;
    7. 	stk.push(*r);
    8. 	if (r->data == target)
    9. 		return true;
    10. 	else if (stl_search_path(target, r->leftchild, stk))
    11. 		return true;
    12.     /*
    13.     执行到这一步，需要重新判断stl_search_path(target, r->leftchild, stk)
    14.     是否为真值；
    15.     函数保存现场不继续向下执行，
    16.     将r->leftchild->leftchild->leftchild==NULL作为参数
    17.     替代r->leftchild->leftchild==4，重新开始执行函数；
    18.     */
    19. }

    发现4的左孩子是空，返回假值；

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

    1. template<class temp>
    2. bool bintree::stl_search_path(temp target, binnode*& r, 
    3.     stack >& stk)
    4. {
    5. 	if (r == NULL)
    6. 		return false;
    7. 	stk.push(*r);
    8. 	if (r->data == target)
    9. 		return true;
    10. 	else if (stl_search_path(target, r->leftchild, stk))
    11. 		return true;
    12. 	else if (stl_search_path(target, r->rightchild, stk))
    13. 		return true;
    14.     /*
    15.     执行到这一步，需要重新判断stl_search_path(target, r->leftchild, stk)
    16.     是否为真值；
    17.     函数保存现场不继续向下执行，
    18.     将r->leftchild->leftchild->rightchild==NULL作为参数
    19.     替代r->leftchild->leftchild==4，重新开始执行函数；
    20.     */
    21. }

    右孩子为空；

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

    示意图如下：

    2.打印路径的函数

    1. template<class temp>
    2. void bintree::stl_node_root_path(temp target)
    3. {
    4. 	stack>stk;
    5. 	stl_search_path(target, this->root, stk);
    6. 	if (stk.empty())
    7. 		cout << target << "未能找到目标" << endl;
    8. 	else
    9. 	{
    10. 		cout << target << "结点到根节点的路径为:" << endl;
    11. 		binnodeout;
    12. 		while (!stk.empty())
    13. 		{
    14. 			out = stk.top();
    15. 			if (stk.size() == 1)
    16. 				cout << out.data;
    17. 			else
    18. 				cout << out.data << "->";
    19. 			stk.pop();
    20. 		}
    21. 		cout << endl;
    22. 	}
    23. }

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

     3.另一种存储方式

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

    代码如下：

    1. template<class temp>
    2. void bintree::linkstack_node_root_path(temp target)
    3. {
    4. 	linkstack>stk;
    5. 	linkstack_search_path(target, this->root, stk);
    6. 	if (stk.empty())
    7. 		cout << target << "未能找到目标" << endl;
    8. 	else
    9. 	{
    10. 		cout << target << "结点到根节点的路径为:" << endl;
    11. 		binnodeout;
    12. 		while (!stk.empty())
    13. 		{
    14. 			out = stk.gettop();
    15. 			if (stk.getsize() == 1)
    16. 				cout << out.data;
    17. 			else
    18. 				cout << out.data << "->";
    19. 			stk.pop();
    20. 		}
    21. 		cout << endl;
    22. 	}
    23. }
    1. template<class temp>
    2. bool bintree::linkstack_search_path(temp target, binnode*& r, linkstack>& stk)
    3. {
    4. 	if (r == NULL)
    5. 		return false;
    6. 	stk.push(*r);
    7. 	if (r->data == target)
    8. 		return true;
    9. 	else if (linkstack_search_path(target, r->leftchild, stk))
    10. 		return true;
    11. 	else if (linkstack_search_path(target, r->rightchild, stk))
    12. 		return true;
    13. 	stk.pop();
    14. 	return false;
    15. }

    二.完整代码：

    2.1使用STL栈实现：

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. class student
    6. {
    7. private:
    8. 	int ID;
    9. 	string name;
    10. public:
    11. 	int existence;
    12. 	student()
    13. 	{
    14. 		this->ID = 0;
    15. 		this->name = "unknown name";
    16. 		this->existence = 0;
    17. 	}
    18. 	student(int ID, string name)
    19. 	{
    20. 		this->ID = ID;
    21. 		this->name = name;
    22. 		this->existence = 1;
    23. 	}
    24. 	bool operator == (student& s)
    25. 	{
    26. 		return ((this->ID == s.ID) && (this->name == s.name)) ? true : false;
    27. 	}
    28. 	friend ostream& operator<<(ostream& output, student& s)
    29. 	{
    30. 		output << "\"" << s.ID << " " << s.name << "\"";
    31. 		return output;
    32. 	}
    33. };
    34.  
    35. template<class temp>
    36. struct binnode
    37. {
    38. 	temp data;
    39. 	binnode* leftchild;
    40. 	binnode* rightchild;
    41. };
    42.  
    43. template<class temp>
    44. class bintree
    45. {
    46. private:
    47. 	void create(binnode*& r, temp data[], int i, int n);
    48. 	void release(binnode* r);
    49. public:
    50. 	binnode* root;
    51. 	bintree(temp data[], int n);
    52. 	void stl_node_root_path(temp target);
    53. 	bool stl_search_path(temp target, binnode*& r, stack >& stk);
    54. 	~bintree();
    55. };
    56.  
    57. template<class temp>
    58. void bintree::create(binnode*& r, temp data[], int i, int n)
    59. {
    60. 	if (i <= n && data[i - 1].existence != 0)
    61. 	{
    62. 		r = new binnode;
    63. 		r->data = data[i - 1];
    64. 		r->leftchild = NULL;
    65. 		r->rightchild = NULL;
    66. 		create(r->leftchild, data, 2 * i, n);
    67. 		create(r->rightchild, data, 2 * i + 1, n);
    68.  
    69. 	}
    70. }
    71.  
    72. template<class temp>
    73. bintree::bintree(temp data[], int n)
    74. {
    75. 	create(this->root, data, 1, n);
    76. }
    77.  
    78. template<class temp>
    79. void bintree::release(binnode* r)
    80. {
    81. 	if (r != NULL)
    82. 	{
    83. 		release(r->leftchild);
    84. 		release(r->rightchild);
    85. 		delete r;
    86. 	}
    87. }
    88.  
    89. template<class temp>
    90. bintree::~bintree()
    91. {
    92. 	release(this->root);
    93. }
    94.  
    95. template<class temp>
    96. void bintree::stl_node_root_path(temp target)
    97. {
    98. 	stack>stk;
    99. 	stl_search_path(target, this->root, stk);
    100. 	if (stk.empty())
    101. 		cout << target << "未能找到目标" << endl;
    102. 	else
    103. 	{
    104. 		cout << target << "结点到根节点的路径为:" << endl;
    105. 		binnodeout;
    106. 		while (!stk.empty())
    107. 		{
    108. 			out = stk.top();
    109. 			if (stk.size() == 1)
    110. 				cout << out.data;
    111. 			else
    112. 				cout << out.data << "->";
    113. 			stk.pop();
    114. 		}
    115. 		cout << endl;
    116. 	}
    117. }
    118.  
    119. template<class temp>
    120. bool bintree::stl_search_path(temp target, binnode*& r, stack >& stk)
    121. {
    122. 	if (r == NULL)
    123. 		return false;
    124. 	stk.push(*r);
    125. 	if (r->data == target)
    126. 		return true;
    127. 	else if (stl_search_path(target, r->leftchild, stk))
    128. 		return true;
    129. 	else if (stl_search_path(target, r->rightchild, stk))
    130. 		return true;
    131. 	stk.pop();
    132. 	return false;
    133. }
    134.  
    135. int main()
    136. {
    137. 	system("color 0A");
    138. 	student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };
    139. 	bintreetree(stu, 5);
    140.  
    141. 	student stu1(1, "zhang"), stu2(5, "liu"), stu3(6, "cao");
    142. 	tree.stl_node_root_path(stu1);
    143. 	tree.stl_node_root_path(stu2);
    144. 	tree.stl_node_root_path(stu3);
    145.  
    146. 	return 0;
    147. }

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

    1. #include
    2. using namespace std;
    3.  
    4. class student
    5. {
    6. private:
    7. 	int ID;
    8. 	string name;
    9. public:
    10. 	int existence;
    11. 	student()
    12. 	{
    13. 		this->ID = 0;
    14. 		this->name = "unknown name";
    15. 		this->existence = 0;
    16. 	}
    17. 	student(int ID, string name)
    18. 	{
    19. 		this->ID = ID;
    20. 		this->name = name;
    21. 		this->existence = 1;
    22. 	}
    23. 	bool operator == (student& s)
    24. 	{
    25. 		return ((this->ID == s.ID) && (this->name == s.name)) ? true : false;
    26. 	}
    27. 	friend ostream& operator<<(ostream& output, student& s)
    28. 	{
    29. 		output << "\"" << s.ID << " " << s.name << "\"";
    30. 		return output;
    31. 	}
    32. };
    33. //二叉树声明部分
    34. template<class temp>
    35. struct binnode;
    36. //栈
    37. template <class temp>
    38. struct node
    39. {
    40. 	temp data;
    41. 	node* next;
    42. };
    43.  
    44. template <class temp>
    45. class linkstack
    46. {
    47. public:
    48. 	binnode* r;
    49. 	int tag;
    50. 	linkstack() { top = NULL; }
    51. 	~linkstack();
    52. 	void push(temp x);
    53. 	temp pop();
    54. 	temp gettop();
    55. 	int getsize();
    56. 	bool empty()
    57. 	{
    58. 		return top == NULL ? true : false;
    59. 	}
    60. private:
    61. 	node* top;
    62. };
    63.  
    64. template <class temp>
    65. void linkstack::push(temp x)
    66. {
    67. 	node* p = new node;
    68. 	p->data = x;
    69. 	p->next = this->top;
    70. 	this->top = p;
    71. }
    72.  
    73. template<class temp>
    74. temp linkstack::pop()
    75. {
    76. 	if (empty())throw "下溢";
    77. 	temp x = this->top->data;
    78. 	node* p = this->top;
    79. 	this->top = this->top->next;
    80. 	delete p;
    81. 	return x;
    82. }
    83.  
    84. template<class temp>
    85. linkstack::~linkstack()
    86. {
    87. 	while (this->top != NULL)
    88. 	{
    89. 		node* p = this->top;
    90. 		this->top = this->top->next;
    91. 		delete p;
    92. 	}
    93. }
    94.  
    95. template<class temp>
    96. temp linkstack::gettop()
    97. {
    98. 	if (empty())throw"下溢";
    99. 	return this->top->data;
    100. }
    101.  
    102. template<class temp>
    103. int linkstack::getsize()
    104. {
    105. 	int num = 0;
    106. 	node* p = this->top;
    107. 	while (p != NULL)
    108. 	{
    109. 		num++;
    110. 		p = p->next;
    111. 	}
    112. 	return num;
    113. }
    114.  
    115.  
    116. template<class temp>
    117. struct binnode
    118. {
    119. 	temp data;
    120. 	binnode* leftchild;
    121. 	binnode* rightchild;
    122. };
    123.  
    124. template<class temp>
    125. class bintree
    126. {
    127. private:
    128. 	void create(binnode*& r, temp data[], int i, int n);
    129. 	void release(binnode* r);
    130. public:
    131. 	binnode* root;
    132. 	bintree(temp data[], int n);
    133. 	void linkstack_node_root_path(temp target);
    134. 	bool linkstack_search_path(temp target, binnode*& r, linkstack>& stk);
    135. 	~bintree();
    136. };
    137.  
    138. template<class temp>
    139. void bintree::create(binnode*& r, temp data[], int i, int n)
    140. {
    141. 	if (i <= n && data[i - 1].existence != 0)
    142. 	{
    143. 		r = new binnode;
    144. 		r->data = data[i - 1];
    145. 		r->leftchild = NULL;
    146. 		r->rightchild = NULL;
    147. 		create(r->leftchild, data, 2 * i, n);
    148. 		create(r->rightchild, data, 2 * i + 1, n);
    149.  
    150. 	}
    151. }
    152.  
    153. template<class temp>
    154. bintree::bintree(temp data[], int n)
    155. {
    156. 	create(this->root, data, 1, n);
    157. }
    158.  
    159. template<class temp>
    160. void bintree::release(binnode* r)
    161. {
    162. 	if (r != NULL)
    163. 	{
    164. 		release(r->leftchild);
    165. 		release(r->rightchild);
    166. 		delete r;
    167. 	}
    168. }
    169.  
    170. template<class temp>
    171. bintree::~bintree()
    172. {
    173. 	release(this->root);
    174. }
    175.  
    176. template<class temp>
    177. void bintree::linkstack_node_root_path(temp target)
    178. {
    179. 	linkstack>stk;
    180. 	linkstack_search_path(target, this->root, stk);
    181. 	if (stk.empty())
    182. 		cout << target << "未能找到目标" << endl;
    183. 	else
    184. 	{
    185. 		cout << target << "结点到根节点的路径为:" << endl;
    186. 		binnodeout;
    187. 		while (!stk.empty())
    188. 		{
    189. 			out = stk.gettop();
    190. 			if (stk.getsize() == 1)
    191. 				cout << out.data;
    192. 			else
    193. 				cout << out.data << "->";
    194. 			stk.pop();
    195. 		}
    196. 		cout << endl;
    197. 	}
    198. }
    199.  
    200. template<class temp>
    201. bool bintree::linkstack_search_path(temp target, binnode*& r, linkstack>& stk)
    202. {
    203. 	if (r == NULL)
    204. 		return false;
    205. 	stk.push(*r);
    206. 	if (r->data == target)
    207. 		return true;
    208. 	else if (linkstack_search_path(target, r->leftchild, stk))
    209. 		return true;
    210. 	else if (linkstack_search_path(target, r->rightchild, stk))
    211. 		return true;
    212. 	stk.pop();
    213. 	return false;
    214. }
    215.  
    216. int main()
    217. {
    218. 	system("color 0A");
    219. 	student stu[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"liu"} };
    220. 	bintreetree(stu, 5);
    221.  
    222. 	student stu1(1, "zhang"), stu2(5, "liu"), stu3(6, "cao");
    223.  
    224. 	tree.linkstack_node_root_path(stu1);
    225. 	tree.linkstack_node_root_path(stu2);
    226. 	tree.linkstack_node_root_path(stu3);
    227. 	return 0;
    228. }

    2.3运行效果：

  • 相关阅读:
    QT发送Get请求并返回内容
    基于树莓派的智能门禁及3D外壳打印设计
    linux系统向github传文件
    在条码软件中如何制作ISBT-128条码
    【Harmony OS】【ArkUI】ets开发 简易视频播放器
    为什么您的公司应该进行脉动调查以及如何正确进行
    高级IO—多路转接
    View的事件分发机制
    金蝶云星空与旺店通·企业奇门对接集成盘盈单查询打通创建盘点单
    JAVA家教管理系统毕业设计 开题报告
  • 原文地址：https://blog.csdn.net/bc202205/article/details/130842838