c++ - 如何在bst中迭代地找到两个节点之间的路径?
问题描述
假设这是节点类。
class Node{
string name;
int key; // the value to determine where to go left or right
Node* lChild;
Node* rChild;
}
我知道如何递归查找。但是,您对如何迭代地找到两个节点之间的路径有什么建议吗?
vector<string> find_path(string a, string b){
vector<string> tmp;
Node* head_node = head;
return tmp;
}
解决方案
要在 BST 中找到持有键 x 和 y 的节点之间的路径,可以使用以下过程:
- 沿着树向下走,搜索 x 和 y,直到 (1) 遇到 x,(2) 遇到 y,或 (3) 遇到 x 在一侧而 y 在另一侧的节点。
- 如果您在上一步中找到了 x 或 y,只需沿着树向下搜索另一个,写下您遇到的节点序列,然后返回该序列。
- 否则,假设您停在 x 和 y 位于相反两侧的节点 z。从 z 走到 x 再从 z 走到 y,像你一样写下路径。然后,将从 x 到 z 的路径和从 z 到 y 的路径粘合在一起,以获得您想要的路径。
这种方法可以迭代地完成——你只需要在写下你所走的路径时迭代地下降一棵树的能力。
推荐阅读
- c++ - 如何在 GET 请求中包含 ESP8266 mac 作为 arg?
- javascript - 如何以随机时间间隔进行倒计时,停在零?
- yii2 - 如何在 YII restful GET api 上实现过滤?
- error-handling - How do I fix "may not be safely transferred across an unwind boundary" for VaList?
- php - 如何传入建立数据库();进入 PHP 中的函数
- c++ - 如何在 C++ 中从头到尾写入文件
- javascript - Aframe Text 看屏幕
- android - 生成签名 APK 失败
- android - 显示带有字母数字切换选项的数字键盘
- python - 如何在Django中使用注册的电话号码和密码登录