1. 基于二叉链表的存储结构，按先序遍历构建二叉树（输入“#”表示空节 点）；采用递归方法分别实现前序、中序、后序遍历算法（遍历过程中打印输出结 点数据）；同时统计二叉树的基本结构信息

Question

1. 基于二叉链表的存储结构，按先序遍历构建二叉树（输入“#”表示空节
   点）；采用递归方法分别实现前序、中序、后序遍历算法（遍历过程中打印输出结
   点数据）；同时统计二叉树的基本结构信息：包括总节点个数、叶子节点个数、度
   为 1 的节点个数以及度为 2 的节点个数。

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题分析

基于二叉链表的存储结构，需要实现以下功能：

1. 按先序遍历构建二叉树
2. 采用递归方法分别实现前序、中序、后序遍历算法
3. 统计二叉树的基本结构信息：包括总节点个数、叶子节点

解决方案

二叉链表结构定义

struct Node {
    int data;
    Node* left;
    Node* right;
};

构建二叉树

Node* buildTree(char** str, int* len) {
    if (*len == 0 || str[*len - 1] == '#') {
        return nullptr;
    }
    Node* node = new Node();
    node->data = str[*len - 1][0] - '0';
    *len -= 1;
    node->left = buildTree(str, len);
    node->right = buildTree(str, len);
    return node;
}

前序遍历

void preOrder(Node* node) {
    if (node == nullptr) {
        return;
    }
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

中序遍历

void inOrder(Node* node) {
    if (node == nullptr) {
        return;
    }
    inOrder(node->left);
    printf("%d ", node->data);
    inOrder(node->right);
}

后序遍历

void postOrder(Node* node) {
    if (node == nullptr) {
        return;
    }
    postOrder(node->left);
    postOrder(node->right);
    printf("%d ", node->data);
}

统计二叉树的基本结构信息

int countNodes(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + countNodes(node->left) + countNodes(node->right);
}

int countLeafNodes(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    if (node->left == nullptr && node->right == nullptr) {
        return 1;
    }
    return countLeafNodes(node->left) + countLeafNodes(node->right);
}

测试代码

int main() {
    char* str[] = {"1", "2", "3", "#", "4", "#", "5", "#", "#", "6", "#", "#"};
    int len = sizeof(str) / sizeof(str[0]);
    Node* root = buildTree(str, &len);
    printf("前序遍历:");
    preOrder(root);
    printf("\n");
    printf("中序遍历:");
    inOrder(root);
    printf("\n");
    printf("后序遍历:");
    postOrder(root);
    printf("\n");
    printf("总节点个数:%d\n", countNodes(root));
    printf("叶子节点个数:%d\n", countLeafNodes(root));
    return 0;
}

注意: 该代码使用 C++ 语言实现，使用二叉链表结构来存储二叉树。构建二叉树使用递归方法，分别实现前序、中序、后序遍历算法。同时统计二叉树的基本结构信息，包括总节点个数和叶子节点个数。