用非递归算法求二叉树高度
时间: 2023-09-28 14:07:39 浏览: 89
可以使用层序遍历的方式,从根节点开始,每遍历一层就把高度加1,直到遍历完所有层即可获得二叉树的高度。以下是示例代码:
```
int getHeight(Node* root) {
if (root == nullptr) {
return 0;
}
queue<Node*> q;
q.push(root);
int height = 0;
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
Node* node = q.front();
q.pop();
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
height++; // 遍历完一层后,高度+1
}
return height;
}
```
对于二叉树的每个结点,都要访问一次,时间复杂度为 O(N),其中 N 是二叉树的结点数;空间复杂度为 O(W),其中 W 是最大的层宽。
相关问题
C语言中,借助链式队列,用非递归算法求二叉树的高度
求解二叉树的高度可以使用递归或非递归算法,下面是使用链式队列和非递归算法求解二叉树高度的步骤:
1. 定义一个结构体用于表示二叉树的结点,包含一个指向左子树的指针和一个指向右子树的指针。
```
typedef struct TreeNode {
int value;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
2. 定义一个结构体用于表示队列中的元素,包含一个指向二叉树结点的指针和一个指向下一个元素的指针。
```
typedef struct QueueNode {
TreeNode* node;
struct QueueNode* next;
} QueueNode;
```
3. 定义一个链式队列,包含一个指向队头元素的指针和一个指向队尾元素的指针。
```
typedef struct Queue {
QueueNode* front;
QueueNode* rear;
} Queue;
```
4. 定义一个函数用于创建二叉树结点。
```
TreeNode* createTreeNode(int value, TreeNode* left, TreeNode* right) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->value = value;
node->left = left;
node->right = right;
return node;
}
```
5. 定义一个函数用于计算二叉树的高度,该函数使用链式队列和非递归算法实现。
```
int calculateHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
Queue queue;
queue.front = NULL;
queue.rear = NULL;
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->node = root;
node->next = NULL;
queue.front = node;
queue.rear = node;
int height = 0;
while (queue.front != NULL) {
height++;
int levelSize = queue.rear - queue.front + 1;
for (int i = 0; i < levelSize; i++) {
QueueNode* currentNode = queue.front;
queue.front = queue.front->next;
if (currentNode->node->left != NULL) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->node = currentNode->node->left;
newNode->next = NULL;
queue.rear->next = newNode;
queue.rear = newNode;
}
if (currentNode->node->right != NULL) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->node = currentNode->node->right;
newNode->next = NULL;
queue.rear->next = newNode;
queue.rear = newNode;
}
free(currentNode);
}
}
return height;
}
```
6. 使用上述函数计算二叉树的高度。
```
int main() {
// 构建二叉树
TreeNode* root = createTreeNode(1,
createTreeNode(2,
createTreeNode(4, NULL, NULL),
createTreeNode(5, NULL, NULL)),
createTreeNode(3,
createTreeNode(6, NULL, NULL),
createTreeNode(7, NULL, NULL)));
// 计算二叉树的高度
int height = calculateHeight(root);
printf("The height of the binary tree is %d\n", height);
return 0;
}
```
输出结果为:
```
The height of the binary tree is 3
```
后序非递归算法计算二叉树高度
二叉树高度的非递归算法可以通过层次遍历实现。下面是一种基于队列的算法:
1. 初始化一个空队列,并将根节点入队。
2. 初始化一个变量 height,并将其置为 0。
3. 循环执行以下步骤,直到队列为空:
a. 获取当前队列的长度,表示当前层的节点个数。
b. 遍历当前层的所有节点:
i. 将当前节点出队。
ii. 如果当前节点有左子节点,将其入队。
iii. 如果当前节点有右子节点,将其入队。
c. 增加 height 的值。
4. 返回 height 的值作为二叉树的高度。
这种非递归算法利用了队列的先进先出特性,每层的节点按照从左到右的顺序依次入队,从而实现了按层遍历。通过记录遍历的层数,最终得到二叉树的高度。