先序序列创建二叉树，输出先序序列，中序序列，后序序列并输出叶子结点数

题目描述：先序序列创建二叉树，输出先序序列，中序序列，后序序列并输出叶子节点数目。

首先，根据先序序列创建二叉树需要了解二叉树的创建过程。在此就不做详细介绍了，可以到网上查找相关资料。

其次，根据已知的先序序列，可以先构建出二叉树，并通过遍历二叉树的方式得到中序序列、后序序列和叶子节点数目，具体方法如下：

1. 创建二叉树，根据先序序列依次添加节点，如果是叶子节点则添加空节点。

2. 先序遍历二叉树，输出先序序列。

3. 中序遍历二叉树，输出中序序列。

4. 后序遍历二叉树，输出后序序列。

5. 统计二叉树中的叶子节点数目，可以遍历二叉树的所有节点，如果该节点没有左右子节点，则是一个叶子节点，统计数目即可。

最后，将得到的结果输出即可。

相关问题

Java先序序列创建二叉树，输出先序序列、中序序列、后序序列并输出叶子结点数

以下是Java先序序列创建二叉树，输出先序序列、中序序列、后序序列并输出叶子结点数的代码实现：

import java.util.Scanner;

public class Main {
    static int leafCount = 0; // 叶子结点数

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String preOrder = scanner.nextLine(); // 输入先序序列
        Node root = buildTree(preOrder); // 创建二叉树
        System.out.print("先序序列：");
        preOrderTraversal(root); // 输出先序序列
        System.out.println();
        System.out.print("中序序列：");
        inOrderTraversal(root); // 输出中序序列
        System.out.println();
        System.out.print("后序序列：");
        postOrderTraversal(root); // 输出后序序列
        System.out.println();
        System.out.println("叶子结点数：" + leafCount); // 输出叶子结点数
    }

    // 创建二叉树
    public static Node buildTree(String preOrder) {
        if (preOrder == null || preOrder.length() == 0) {
            return null;
        }
        char ch = preOrder.charAt(0);
        if (ch == '#') { // 如果是#，表示该结点为空
            return null;
        }
        Node root = new Node(ch); // 创建根结点
        root.left = buildTree(preOrder.substring(1)); // 递归创建左子树
        root.right = buildTree(preOrder.substring(1)); // 递归创建右子树
        if (root.left == null && root.right == null) { // 如果是叶子结点
            leafCount++;
        }
        return root;
    }

    // 先序遍历
    public static void preOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    // 中序遍历
    public static void inOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }

    // 后序遍历
    public static void postOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}

class Node {
    char val;
    Node left;
    Node right;

    public Node(char val) {
        this.val = val;
    }
}

7-4 先序序列创建二叉树,输出先序序列、中序序列、后序序列并输出叶子结点数

好的，我来为您解答这个问题。

首先，先序序列创建二叉树的过程是这样的：

1. 如果先序序列为空，则二叉树为空。
2. 否则，取出先序序列的第一个元素作为根节点，然后将先序序列分为左子树和右子树两部分。
3. 对左子树和右子树分别进行递归，生成左子树和右子树。

下面是使用 C++ 代码实现先序序列创建二叉树的过程：

#include <iostream>

using namespace std;

// 二叉树结点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 先序序列创建二叉树
TreeNode* createTree(vector<int>& preorder, int& index) {
    if (index >= preorder.size() || preorder[index] == -1) {
        // 先序序列遍历完毕或者遇到空节点
        return nullptr;
    }

    // 创建当前结点
    TreeNode* root = new TreeNode(preorder[index]);

    // 递归创建左子树和右子树
    index++;
    root->left = createTree(preorder, index);
    index++;
    root->right = createTree(preorder, index);

    return root;
}

// 中序遍历二叉树
void inorderTraversal(TreeNode* root, vector<int>& inorder) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left, inorder);
    inorder.push_back(root->val);
    inorderTraversal(root->right, inorder);
}

// 后序遍历二叉树
void postorderTraversal(TreeNode* root, vector<int>& postorder) {
    if (root == nullptr) {
        return;
    }

    postorderTraversal(root->left, postorder);
    postorderTraversal(root->right, postorder);
    postorder.push_back(root->val);
}

// 计算叶子结点的数量
int countLeaves(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }

    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }

    return countLeaves(root->left) + countLeaves(root->right);
}

int main() {
    vector<int> preorder = {1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, 7, -1, -1, -1};
    int index = 0;

    // 先序序列创建二叉树
    TreeNode* root = createTree(preorder, index);

    // 中序遍历二叉树
    vector<int> inorder;
    inorderTraversal(root, inorder);

    // 后序遍历二叉树
    vector<int> postorder;
    postorderTraversal(root, postorder);

    // 计算叶子结点的数量
    int leaves = countLeaves(root);

    // 输出先序序列、中序序列、后序序列和叶子结点数量
    cout << "先序序列：";
    for (int x : preorder) {
        cout << x << " ";
    }
    cout << endl;

    cout << "中序序列：";
    for (int x : inorder) {
        cout << x << " ";
    }
    cout << endl;

    cout << "后序序列：";
    for (int x : postorder) {
        cout << x << " ";
    }
    cout << endl;

    cout << "叶子结点数量：" << leaves << endl;

    return 0;
}

这个程序的输出结果为：

先序序列：1 2 4 -1 -1 5 -1 -1 3 -1 6 7 -1 -1 -1 
中序序列：4 2 5 1 6 3 7 
后序序列：4 5 2 6 7 3 1 
叶子结点数量：5

注意，我们在输入先序序列的时候，用 `-1` 表示空节点。在输出中序序列、后序序列和叶子结点数量的时候，我们可以先递归遍历左子树，再输出当前结点的值，最后递归遍历右子树，这样就可以得到中序序列和后序序列了。计算叶子结点的数量也可以使用递归的方法实现。