请使用一种程序设计语言改写二叉树的一种深度优先遍历算法,要求能够计算出每个顶点的深度。使用C++
时间: 2023-06-09 12:05:16 浏览: 204
Sure! 这是用C语言实现二叉树的深度优先遍历算法,同时计算出每个顶点的深度:
```
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int value;
int depth;
struct node* left_child;
struct node* right_child;
}Node;
void dfs(Node* node){
if(node == NULL){
return;
}
printf("当前节点的值是: %d, 深度是 %d\n", node->value, node->depth);
if(node->left_child != NULL){
node->left_child->depth = node->depth + 1;
dfs(node->left_child);
}
if(node->right_child != NULL){
node->right_child->depth = node->depth + 1;
dfs(node->right_child);
}
}
int main(){
Node* root = NULL;
root = (Node*)malloc(sizeof(Node));
root->value = 1;
root->depth = 0;
root->left_child = (Node*)malloc(sizeof(Node));
root->left_child->value = 2;
root->left_child->depth = 1;
root->right_child = (Node*)malloc(sizeof(Node));
root->right_child->value = 3;
root->right_child->depth = 1;
root->left_child->left_child = (Node*)malloc(sizeof(Node));
root->left_child->left_child->value = 4;
root->left_child->left_child->depth = 2;
root->left_child->right_child = (Node*)malloc(sizeof(Node));
root->left_child->right_child->value = 5;
root->left_child->right_child->depth = 2;
root->right_child->left_child = (Node*)malloc(sizeof(Node));
root->right_child->left_child->value = 6;
root->right_child->left_child->depth = 2;
root->right_child->right_child = (Node*)malloc(sizeof(Node));
root->right_child->right_child->value = 7;
root->right_child->right_child->depth = 2;
dfs(root);
return 0;
}
```
这段代码使用了一个有 `value`, `left_child`, 和 `right_child` 字段的 `Node` 结构体来表示每个节点。在 `dfs` 函数中,它会首先打印出当前节点的值和深度。然后,分别遍历左子树和右子树,并为每个子节点的深度加上一来计算子节点的深度。在 `main` 函数中,我们手动构建了一个二叉树,并将根节点深度设置为0,然后调用了 `dfs(root)` 来启动遍历算法。
阅读全文