二叉树的宽度c语言,以二叉链表为存储结构,写出求二叉树高度和宽度的算法
时间: 2024-05-01 22:23:38 浏览: 10
求二叉树高度的算法:
```
int height(BiTree root) {
if (root == NULL) {
return 0;
} else {
int leftHeight = height(root->lchild);
int rightHeight = height(root->rchild);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
}
```
求二叉树宽度的算法:
```
int width(BiTree root) {
if (root == NULL) {
return 0;
} else {
int maxWidth = 0;
int currentWidth = 0;
Queue queue;
initQueue(&queue);
enQueue(&queue, root);
enQueue(&queue, NULL);
while (!isEmpty(&queue)) {
BiTree node = deQueue(&queue);
if (node == NULL) {
if (currentWidth > maxWidth) {
maxWidth = currentWidth;
}
currentWidth = 0;
if (!isEmpty(&queue)) {
enQueue(&queue, NULL);
}
} else {
currentWidth++;
if (node->lchild != NULL) {
enQueue(&queue, node->lchild);
}
if (node->rchild != NULL) {
enQueue(&queue, node->rchild);
}
}
}
return maxWidth;
}
}
```
其中,`BiTree` 表示二叉树节点的结构体,`Queue` 表示队列的结构体,`initQueue` 表示初始化队列,`enQueue` 表示入队列,`deQueue` 表示出队列,`isEmpty` 判断队列是否为空。