使用c++计算二叉树最大的宽度
时间: 2023-11-29 09:02:00 浏览: 48
计算二叉树最大宽度的一种常见方法是使用层次遍历,即逐层遍历二叉树并记录每一层的节点数和位置,然后计算每一层的最大宽度。
以下是一个示例代码,可以计算二叉树的最大宽度:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct QueueNode {
TreeNode *t;
int pos;
struct QueueNode *next;
} QueueNode;
typedef struct Queue {
QueueNode *head;
QueueNode *tail;
} Queue;
Queue *createQueue() {
Queue *q = (Queue *)malloc(sizeof(Queue));
q->head = NULL;
q->tail = NULL;
return q;
}
void enQueue(Queue *q, TreeNode *t, int pos) {
QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
node->t = t;
node->pos = pos;
node->next = NULL;
if (q->head == NULL) {
q->head = node;
q->tail = node;
} else {
q->tail->next = node;
q->tail = node;
}
}
QueueNode *deQueue(Queue *q) {
if (q->head == NULL) {
return NULL;
}
QueueNode *node = q->head;
q->head = q->head->next;
if (q->head == NULL) {
q->tail = NULL;
}
return node;
}
int maxWidth(TreeNode *root) {
if (root == NULL) {
return 0;
}
Queue *q = createQueue();
enQueue(q, root, 1);
int maxWidth = 0;
while (q->head != NULL) {
int size = q->tail->pos - q->head->pos + 1;
if (size > maxWidth) {
maxWidth = size;
}
int i;
for (i = 0; i < size; i++) {
QueueNode *node = deQueue(q);
if (node->t->left != NULL) {
enQueue(q, node->t->left, node->pos * 2);
}
if (node->t->right != NULL) {
enQueue(q, node->t->right, node->pos * 2 + 1);
}
free(node);
}
}
return maxWidth;
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 3;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 2;
root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->left->val = 5;
root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
root->left->right->val = 3;
root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->right->val = 9;
printf("Max width: %d\n", maxWidth(root));
return 0;
}
```
在上面的示例代码中,我们使用了一个队列来记录每个节点及其位置,然后逐层遍历二叉树。在每一层中,我们记录该层的节点数和最左节点的位置,计算该层的宽度,并将左右子节点加入队列中以便下一层的遍历。最终返回最大宽度即可。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)