设计二叉树，输入完全二叉树的先序序列；2、建立二叉树 3、求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

以下是解题思路：

1. 先序遍历序列：二叉树遍历的方式之一，按照“根结点-左子树-右子树”的顺序遍历。
2. 中序遍历序列：二叉树遍历的方式之一，按照“左子树-根结点-右子树”的顺序遍历。
3. 后序遍历序列：二叉树遍历的方式之一，按照“左子树-右子树-根结点”的顺序遍历。
4. 层次遍历序列：二叉树遍历的方式之一，按照从上到下、从左到右的顺序遍历。

在建立二叉树之前，需要了解一下完全二叉树的特点：

1. 完全二叉树的最后一层是满二叉树；
2. 完全二叉树的非最后一层的结点数都是最大值，最后一层的结点数不一定是最大值；
3. 完全二叉树的结点按照从上到下、从左到右的顺序编号，根结点编号为1，其余结点编号为其父结点编号乘2或乘2再加1。

接下来，我们可以根据完全二叉树的特点来建立二叉树和求解各种遍历序列。

代码实现如下：

相关问题

C语言设计二叉树，输入完全二叉树的先序序列；2、建立二叉树 3、求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

下面是C语言实现：

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

#define MAXSIZE 100

// 定义二叉树结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建二叉树
TreeNode *createBinaryTree(int *arr, int index, int len) {
    if (index >= len || arr[index] == -1) return NULL; // 空节点返回NULL
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = arr[index];
    root->left = createBinaryTree(arr, index * 2 + 1, len);
    root->right = createBinaryTree(arr, index * 2 + 2, len);
    return root;
}

// 先序遍历
void preOrder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

// 按层次遍历
void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    TreeNode *queue[MAXSIZE];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode *node = queue[front++];
        printf("%d ", node->data);
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
}

// 计算叶子节点数目和总结点数目
void countNodes(TreeNode *root, int *leafCount, int *nodeCount) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) (*leafCount)++;
    (*nodeCount)++;
    countNodes(root->left, leafCount, nodeCount);
    countNodes(root->right, leafCount, nodeCount);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7}; // 完全二叉树的先序序列
    int len = sizeof(arr) / sizeof(arr[0]);
    TreeNode *root = createBinaryTree(arr, 0, len);
    printf("先序遍历：");
    preOrder(root);
    printf("\n中序遍历：");
    inOrder(root);
    printf("\n后序遍历：");
    postOrder(root);
    printf("\n按层次遍历：");
    levelOrder(root);
    int leafCount = 0, nodeCount = 0;
    countNodes(root, &leafCount, &nodeCount);
    printf("\n叶子节点数目：%d，总结点数目：%d\n", leafCount, nodeCount);
    return 0;
}

输出结果：

先序遍历：1 2 4 5 3 6 7 
中序遍历：4 2 5 1 6 3 7 
后序遍历：4 5 2 6 7 3 1 
按层次遍历：1 2 3 4 5 6 7 
叶子节点数目：3，总结点数目：7

其中，完全二叉树的先序序列是按照“根-左子树-右子树”的顺序存储的，空节点用-1表示。在创建二叉树时，如果节点为空，则返回NULL；如果节点不为空，则创建一个新的节点，并递归创建左右子树。求叶子节点数目和总结点数目时，采用递归方式遍历整个二叉树，如果节点的左右子树为空，则该节点为叶子节点，叶子节点数目加1，总结点数目加1。

设计一个算法，根据二叉树的后序遍历序列和中序遍历序列求其先序遍历序列

设计这样一个算法，可以按照以下步骤来实现：

1. 后序遍历序列（LNR），表示根节点->左子树->右子树。
2. 中序遍历序列（LRN），表示左子树->根节点->右子树。

**步骤1**: 首先，我们需要从后序遍历序列找到根节点。由于后序遍历的特性，最后一个元素一定是根节点，因为它是最后处理的。

**步骤2**: 然后，在中序遍历序列中找到根节点的位置。由于中序遍历根节点前的部分是左子树，之后是右子树，所以根节点在左右两部分之间，即它的索引 = (左子树长度 + 1)。

**步骤3**: 接下来，我们可以分别构建左子树和右子树的先序遍历序列。对于左子树，我们取后序遍历序列中从第一个元素到找到的根节点位置的子序列，然后递归地对这部分序列进行同样的操作。对于右子树，我们从根节点之后开始取后序遍历序列，直到序列结束。

**步骤4**: 将找到的左子树先序遍历和右子树先序遍历拼接在一起，就得到了整个二叉树的先序遍历序列。

下面是伪代码示例：

function buildPreorder(后序遍历 LNR, 中序遍历 LRN):
    root_index = len(LRN)
    root_value = LNR[root_index - 1]
    
    # 找到根节点在中序遍历中的位置
    left_size = findLeftSize(LRN, root_value)
    
    # 分别构建左子树和右子树的先序遍历
    left_preorder = buildPreorder(LNR[:root_index], LRN[:left_size])
    right_preorder = buildPreorder(LNR[root_index:], LRN[left_size:])
    
    # 返回先序遍历
    return [root_value] + left_preorder + right_preorder

function findLeftSize(LRN, value):
    for i in range(len(LRN)):
        if LRN[i] == value:
            return i