给定顺序存储的二叉树,求二叉树的高度。 二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点元素(一般二叉树则将其每个结点与完全二叉树上的结点对照)。
时间: 2024-02-15 12:03:57 浏览: 65
顺序存储的二叉树可以通过数组来实现,数组的下标表示节点的编号,数组中存储的元素就是节点的值。假设数组的长度为n,那么节点编号范围为1到n,节点i的左子节点编号为2i,右子节点编号为2i+1,父节点编号为i/2(向下取整)。具有顺序存储结构的二叉树的高度可以通过以下步骤求得:
1. 如果数组为空,则返回0。
2. 否则,树的高度为根节点的高度。根节点的编号为1,其高度为1加上左右子树高度的较大值。因此,可以递归计算左右子树的高度,然后返回1加上左右子树高度的较大值即可。
下面是一个示例代码,用来计算顺序存储的二叉树的高度:
```c++
int getHeight(int* arr, int n, int i) {
if (i > n || arr[i] == 0) {
return 0;
}
int leftHeight = getHeight(arr, n, i * 2);
int rightHeight = getHeight(arr, n, i * 2 + 1);
return 1 + max(leftHeight, rightHeight);
}
int main() {
int arr[] = {0, 1, 2, 3, 4, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]) - 1;
int height = getHeight(arr, n, 1);
cout << "Height of the binary tree is: " << height << endl;
return 0;
}
```
在这个示例代码中,getHeight函数接受三个参数:arr表示顺序存储的二叉树,n表示数组的长度,i表示当前节点的编号。如果当前节点的编号超出了数组范围,或者当前节点为空节点(值为0),则返回0。否则,使用递归的方式计算左右子树的高度,并返回1加上左右子树高度的较大值。在main函数中,我们创建了一个包含7个元素的数组,表示一个完全二叉树,并计算了它的高度。
阅读全文