首页求二叉树上结点的路径用C加加代码实现

求二叉树上结点的路径用C加加代码实现

时间: 2025-06-14 08:17:05 浏览: 4

在C++中，我们可以使用递归的方式来求解二叉树上任意两个节点之间的路径。这里提供一个基本的示例，假设我们有一个结构体`Node`表示二叉树的节点，其中包含`value`值和指向左右子节点的指针`left`和`right`。 ```cpp #include <iostream> #include <string> // 定义二叉树节点结构 struct Node { int value; Node* left; Node* right; }; // 递归函数计算从根到目标节点的路径 std::string pathToTarget(Node* root, Node* target) { if (root == nullptr || root == target) return std::to_string(root->value); std::string leftPath = pathToTarget(root->left, target); std::string rightPath = pathToTarget(root->right, target); // 如果找到目标节点或者遍历完左、右都没有找到，返回空字符串 if (leftPath.empty() && rightPath.empty()) return ""; // 否则拼接当前节点和其中一个路径 return (leftPath.size() > 0 ? root->value + " -> " + leftPath : "") + (rightPath.size() > 0 ? " -> " + rightPath : ""); } int main() { // 假设你已经构建了一个二叉树，并且有一个特定的目标节点 Node* root = ...; // 你的二叉树根节点 Node* target = ...; // 目标节点 std::string path = pathToTarget(root, target); if (!path.empty()) std::cout << "Path from root to target: " << path << std::endl; else stdots << "No path found." << std::endl; return 0; } ``` 在这个例子中，`pathToTarget`函数会返回从给定根节点到目标节点的完整路径，如果找不到路径则返回空字符串。记得在实际使用前替换`main`中的`root`和`target`为实际的二叉树节点。

阅读全文