二叉链存储结构存储二叉树

Question

采用二叉链存储结构存储二叉树，假设一棵二叉树的前序序列为2 3 4 5 6 7 9，中序序列为5 3 2 4 7 6 9，根据要求完成相应的操作。
1、根据前序和中序，建立该二叉树。
2、输出该二叉树。
3、输出后序序列。
4、计算二叉树的结点个数。
5、计算所有叶子结点个数

Answer 1

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

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

// 根据前序和中序，建立二叉树
TreeNode* CreateTree(int* preorder, int* inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = preorder[preStart];
    int rootIndex = inStart;
    while (inorder[rootIndex] != root->data) {
        rootIndex++;
    }
    int leftSize = rootIndex - inStart;
    root->left = CreateTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
    root->right = CreateTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
    return root;
}

// 输出二叉树
void printTree(TreeNode* root, int depth) {
    if (root == NULL) {
        return;
    }
    printTree(root->right, depth + 1);
    for (int i = 0; i < depth; i++) {
        printf("    ");
    }
    printf("%d\n", root->data);
    printTree(root->left, depth + 1);
}

// 输出后序序列
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->data);
}

// 计算二叉树的结点个数
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 计算所有叶子结点个数
int countLeaves(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

int main() {
    int preorder[] = {2, 3, 4, 5, 6, 7, 9};
    int inorder[] = {5, 3, 2, 4, 7, 6, 9};
    TreeNode* root = CreateTree(preorder, inorder, 0, 6, 0, 6);
    printf("二叉树：\n");
    printTree(root, 0);
    printf("后序序列：");
    postorderTraversal(root);
    printf("\n结点个数：%d\n", countNodes(root));
    printf("叶子结点个数：%d\n", countLeaves(root));
    return 0;
}