采用双亲存储结构t存储,用c++语言设计一个完整的能够运行的算法求其高度。
时间: 2024-02-24 08:56:09 浏览: 54
x是双亲的左孩子双亲有右孩子-C++版数据结构-张宏
好的,下面是一个基于双亲存储结构的C++算法,用于求解树的高度:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000; // 树的最大节点数
struct TreeNode {
int parent;
vector<int> children;
} tree[MAXN];
int getHeight(int node) {
if (tree[node].children.empty()) {
return 0;
} else {
int maxHeight = 0;
for (int i = 0; i < tree[node].children.size(); i++) {
int child = tree[node].children[i];
int height = getHeight(child);
maxHeight = max(maxHeight, height);
}
return maxHeight + 1;
}
}
int main() {
int n; // 树的节点数
cin >> n;
// 读入树的信息,构建树
for (int i = 0; i < n; i++) {
int parent;
cin >> parent;
if (parent != -1) {
tree[i].parent = parent;
tree[parent].children.push_back(i);
}
}
// 计算树的高度
int height = 0;
for (int i = 0; i < n; i++) {
if (tree[i].parent == -1) {
int h = getHeight(i);
height = max(height, h);
}
}
cout << height << endl;
return 0;
}
```
此算法首先读入树的信息,构建树,并计算树的高度。其中,getHeight()函数用于递归计算节点的高度。对于一个节点,如果它没有任何子节点,则它的高度为0;否则,它的高度等于它的所有子节点中高度最大的那个加1。
这个算法的时间复杂度为O(n^2),其中n为树的节点数。如果采用其他存储结构,如孩子-兄弟存储结构,可以将时间复杂度降为O(n)。
阅读全文