求树的各个节点的深度可以自上而下统计信息。起初,我们已知根节点的的深度为0.若节点x的深度为d[x],则它的子节点y的深度为d[y]=d[x]+1,现在给你一棵树,让你输出每个节点的深度。需要具体代码
时间: 2023-03-26 17:03:10 浏览: 66
可以使用深度优先搜索(DFS)来遍历整棵树,同时记录每个节点的深度。具体代码如下:
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN]; // 存储树的邻接表
int depth[MAXN]; // 存储每个节点的深度
void dfs(int u, int d) {
depth[u] = d; // 记录当前节点的深度
for (int v : adj[u]) {
dfs(v, d + 1); // 递归遍历子节点
}
}
int main() {
int n;
cin >> n; // 输入节点数
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v; // 输入一条边
adj[u].push_back(v);
}
dfs(1, ); // 从根节点开始遍历
for (int i = 1; i <= n; i++) {
cout << depth[i] << " "; // 输出每个节点的深度
}
cout << endl;
return ;
}
相关问题
C语言求二叉树以元素值为x的节点为根的子树深度
很高兴回答您的问题。对于这个问题,我们可以先遍历整个二叉树,找到以元素值为x的节点为根的子树,并计算该子树的深度。具体算法如下:
1. 遍历整个二叉树,如果遇到当前节点的值等于x,就将该节点作为根节点进行深度计算。
2. 计算深度的方法可以使用递归算法,即将当前节点的左右子节点深度中的较大值加1作为当前节点的深度。
3. 重复执行以上两个步骤,直到遍历完整个二叉树。
希望能够帮助您解决问题。如果您有其他问题,请随时提问。
C语言求二叉树以元素值为x的节点为根的子树深度代码
以下是 C 语言代码实现求二叉树以元素值为 x 的节点为根的子树深度:
```
// 定义二叉树结点
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 求以 root 为根节点的二叉树深度
int depth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);
}
// 求二叉树以元素值为 x 的节点为根的子树深度
int subTreeDepth(struct TreeNode* root, int x) {
if (root == NULL) {
return 0;
}
if (root->val == x) {
return depth(root);
} else {
int leftDepth = subTreeDepth(root->left, x);
int rightDepth = subTreeDepth(root->right, x);
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}
```
注意:以上代码实现的二叉树不一定是完全二叉树。