(关键词-编程实现)

Question

C语言编程实现求二叉树宽度。用户输入括号表示的二叉树，程序可以显示二叉树宽度。
提示：建立树、并使用层次遍历的方式求二叉树宽度。

Answer 1

【以下回答由 GPT 生成】

解决方案

首先，我们需要定义二叉树的数据结构。对于二叉树的每个节点，我们需要存储节点的值和指向左子树和右子树的指针。

typedef struct Node {
    char data;
    struct Node* left;
    struct Node* right;
} Node;

接下来，我们可以根据用户输入的括号表示的二叉树构建二叉树。具体做法是遍历输入字符串中的每个字符，如果遇到左括号，则创建一个新节点并将其作为当前节点的左子节点；如果遇到右括号，则将当前节点指向其父节点。当遍历完所有字符后，我们可以得到整个二叉树的根节点。

Node* buildTree(const char* str) {
    Node* root = NULL;
    Node* curNode = NULL;
    Node* parent = NULL;

    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(') {
            // 创建一个新节点
            Node* newNode = (Node*)malloc(sizeof(Node));
            newNode->left = NULL;
            newNode->right = NULL;

            if (root == NULL) {
                root = newNode;
            } else if (curNode != NULL) {
                if (curNode->left == NULL) {
                    curNode->left = newNode;
                } else {
                    curNode->right = newNode;
                }
            }

            curNode = newNode;
        }
        else if (str[i] == ')') {
            curNode = curNode->parent;
        }
        else {
            curNode->data = str[i];
        }
    }

    return root;
}

接下来，我们使用层次遍历的方式计算二叉树的宽度。层次遍历首先将树的根节点入队，然后从队列中循环弹出每个节点并将其非空子节点入队。在队列中的节点数量表示二叉树每一层的节点数量，取其中的最大值即为二叉树的宽度。

int getWidth(Node* root) {
    if (root == NULL) {
        return 0;
    }

    int width = 0;
    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isEmpty(queue)) {
        int levelWidth = size(queue);
        width = max(width, levelWidth);

        for (int i = 0; i < levelWidth; i++) {
            Node* node = dequeue(queue);
            if (node->left != NULL) {
                enqueue(queue, node->left);
            }
            if (node->right != NULL) {
                enqueue(queue, node->right);
            }
        }
    }

    destroyQueue(queue);
    return width;
}

最后，我们可以将上述函数组合在一起，编写一个完整的程序，读取用户输入的括号表示的二叉树，并计算并显示该二叉树的宽度。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    char data;
    struct Node* left;
    struct Node* right;
} Node;

Node* buildTree(const char* str) {
    Node* root = NULL;
    Node* curNode = NULL;
    Node* parent = NULL;

    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(') {
            // 创建一个新节点
            Node* newNode = (Node*)malloc(sizeof(Node));
            newNode->left = NULL;
            newNode->right = NULL;

            if (root == NULL) {
                root = newNode;
            } else if (curNode != NULL) {
                if (curNode->left == NULL) {
                    curNode->left = newNode;
                } else {
                    curNode->right = newNode;
                }
            }

            curNode = newNode;
        }
        else if (str[i] == ')') {
            curNode = curNode->parent;
        }
        else {
            curNode->data = str[i];
        }
    }

    return root;
}

int getWidth(Node* root) {
    if (root == NULL) {
        return 0;
    }

    int width = 0;
    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isEmpty(queue)) {
        int levelWidth = size(queue);
        width = max(width, levelWidth);

        for (int i = 0; i < levelWidth; i++) {
            Node* node = dequeue(queue);
            if (node->left != NULL) {
                enqueue(queue, node->left);
            }
            if (node->right != NULL) {
                enqueue(queue, node->right);
            }
        }
    }

    destroyQueue(queue);
    return width;
}

int main() {
    // 读取用户输入的括号表示的二叉树
    char str[100];
    printf("请输入括号表示的二叉树：");
    scanf("%s", str);

    // 构建二叉树
    Node* root = buildTree(str);

    // 计算并显示二叉树的宽度
    int width = getWidth(root);
    printf("二叉树的宽度为：%d\n", width);

    return 0;
}

【相关推荐】

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7496111
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：C语言建立二叉树的二叉链表结构，并显示二叉树
• 您还可以看一下 李飞老师的C语言开发之数据结构与算法二课程中的 树的插入、查找操作小节, 巩固相关知识点
  
• 除此之外, 这篇博客: C语言数据结构二叉树的建立并中序线索化中的 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^