首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在不使用递归的情况下在C中找到二叉树的高度?

在不使用递归的情况下,可以使用迭代的方式来找到二叉树的高度。具体的实现方法是使用层序遍历算法,通过队列来遍历二叉树的每一层节点,并记录层数,直到遍历完所有节点。

以下是实现的代码示例:

代码语言:txt
复制
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct QueueNode {
    TreeNode* node;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

void enqueue(Queue* queue, TreeNode* node) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

TreeNode* dequeue(Queue* queue) {
    if (queue->front == NULL) {
        return NULL;
    }
    
    TreeNode* node = queue->front->node;
    QueueNode* temp = queue->front;
    queue->front = queue->front->next;
    
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    free(temp);
    return node;
}

int getBinaryTreeHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    Queue* queue = createQueue();
    enqueue(queue, root);
    int height = 0;
    
    while (1) {
        int levelSize = queue->rear - queue->front + 1;
        if (levelSize == 0) {
            break;
        }
        
        while (levelSize > 0) {
            TreeNode* node = dequeue(queue);
            
            if (node->left != NULL) {
                enqueue(queue, node->left);
            }
            
            if (node->right != NULL) {
                enqueue(queue, node->right);
            }
            
            levelSize--;
        }
        
        height++;
    }
    
    return height;
}

int main() {
    // 构造二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->val = 5;
    
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 6;
    
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 7;
    
    // 计算二叉树的高度
    int height = getBinaryTreeHeight(root);
    printf("二叉树的高度为:%d\n", height);
    
    // 释放内存
    free(root->right->right);
    free(root->right->left);
    free(root->left->right);
    free(root->left->left);
    free(root->right);
    free(root->left);
    free(root);
    
    return 0;
}

在上述代码中,我们定义了一个队列结构和一个二叉树结构,使用队列进行层序遍历。首先创建一个队列,并将根节点入队。然后进行循环,当队列非空时,先获取当前层的节点数,依次出队并将它们的左右子节点入队。在每一层处理完之后,层数加1,直到队列为空。最后返回层数作为二叉树的高度。

这里没有提及具体的腾讯云相关产品,因为找二叉树高度是一般计算问题,与云计算平台的关系不大,因此不需要特定的云计算产品来解决。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 领券