设计C++算法,输出二叉树每个结点到根结点之间路径上的所有结点的值.
时间: 2023-06-09 21:08:41 浏览: 143
c++实现在二叉检索树中删除一个结点的算法
5星 · 资源好评率100%
好的,针对您的问题,我可以提供一个C语言算法实现。具体实现思路如下:
1. 给定二叉树的根节点,设计一个递归函数,每次遍历到一个节点,就将该节点的值添加进列表中,并将它的左右子树作为参数传递给递归函数。
2. 当遍历到叶子节点时,将列表中的所有节点值按顺序输出即可。
3. 根据二叉树的性质,可以从任意节点开始递归,因此只需要设计一个函数就能输出任意节点到根节点路径上的所有节点值。
具体的C语言实现代码如下:
```
#include<stdio.h>
#include<stdlib.h>
// 定义二叉树的节点结构
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
}Node;
// 初始化二叉树,返回根节点指针
Node* initTree() {
Node* root = (Node*)malloc(sizeof(Node));
root->data = 1;
Node* left_child = (Node*)malloc(sizeof(Node));
left_child->data = 2;
left_child->left = NULL;
left_child->right = NULL;
Node* right_child = (Node*)malloc(sizeof(Node));
right_child->data = 3;
right_child->left = NULL;
right_child->right = NULL;
root->left = left_child;
root->right = right_child;
return root;
}
// 递归输出节点到根节点路径上的所有节点值
void printPath(Node* root) {
if (root == NULL) {
return;
}
// 将当前节点的值添加到列表中
printf("%d ", root->data);
// 如果当前节点是叶子节点,输出整个列表中的节点值
if (root->left == NULL && root->right == NULL) {
printf("\n");
return;
}
// 遍历左子树
printPath(root->left);
// 遍历右子树
printPath(root->right);
}
int main() {
Node* root = initTree();
printPath(root->left);
return 0;
}
```
这段代码输出的是根节点的左子树中,每个节点到根节点路径上的所有节点值。如果需要输出其他节点到根节点路径上的值,只需要修改`printPath(root->left)`中的参数即可。希望对您有所帮助。
阅读全文