用c++代码计算一棵树的深度
时间: 2023-03-12 17:38:42 浏览: 63
如果使用C语言计算一棵树的深度,可以使用递归函数来计算树的最大深度。具体的实现方法可以参考下面的代码:int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
相关问题
已知一棵二叉排序树,如何计算其ASL?用c++代码实现
计算二叉排序树的ASL,可以按照上面提到的公式进行计算。具体实现可以使用递归方式遍历整棵树,计算每个节点的深度和被查找到的概率,然后根据公式进行累加求和。以下是一个示例代码:
```c++
// 定义二叉树节点结构体
struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(NULL), right(NULL) {}
};
// 计算二叉排序树的ASL
double calculateASL(Node* root, int depth, int n) {
if (root == NULL) {
return 0;
}
double p = 1.0 / n; // 计算概率
int d = depth - 1; // 计算深度
double sum = p * d;
sum += calculateASL(root->left, depth + 1, n);
sum += calculateASL(root->right, depth + 1, n);
return sum;
}
// 测试代码
int main() {
// 构建一棵二叉排序树
Node* root = new Node(4);
root->left = new Node(2);
root->left->left = new Node(1);
root->left->right = new Node(3);
root->right = new Node(6);
root->right->left = new Node(5);
root->right->right = new Node(7);
// 计算ASL并输出结果
int n = 7; // 节点数
double asl = calculateASL(root, 1, n);
cout << "ASL = " << asl << endl;
return 0;
}
```
在示例代码中,我们首先定义了一个二叉树节点的结构体,然后编写了一个递归函数calculateASL来计算二叉排序树的ASL。在测试代码中,我们构建了一棵二叉排序树,并计算了其ASL。
c++代码实现逆推树结构
逆推树结构的实现一般需要借助栈或递归等数据结构,以下是一个简单的C++代码示例:
```
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int MAXN = 100010; // 最大节点数
vector<int> G[MAXN]; // 存储树的邻接表
int depth[MAXN]; // 存储每个节点的深度
int parent[MAXN]; // 存储每个节点的父节点
int n; // 节点总数
// 递归遍历树结构,计算每个节点的深度和父节点
void dfs(int u, int p, int d) {
depth[u] = d;
parent[u] = p;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != p) dfs(v, u, d + 1);
}
}
// 根据每个节点的深度和父节点信息,逆推出树结构
void reverse_tree() {
stack<int> st;
st.push(1); // 从根节点开始逆推
while (!st.empty()) {
int u = st.top(); st.pop();
cout << u << " ";
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != parent[u]) st.push(v);
}
}
}
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1, 0); // 从根节点开始递归遍历
reverse_tree(); // 逆推树结构
return 0;
}
```
以上代码中,我们首先读入节点总数和每个节点的父子关系,并构建出一棵树的邻接表存储。然后,我们从根节点开始递归遍历树结构,计算出每个节点的深度和父节点信息。接着,我们利用栈来逆推出树结构,具体来说,我们从根节点开始,依次将其子节点压入栈中,然后弹出栈顶节点,并将其输出。对于每个节点,我们只需要将其非父节点的子节点压入栈中即可。最后输出的序列即为逆推出的树结构。
需要注意的是,以上代码假定根节点为1,如果根节点不为1,则需要修改dfs函数中的参数。此外,以上代码只实现了逆推树结构的功能,如果需要求解其他问题,比如节点之间的距离等,还需要进行相应的修改。