使用C语言完成 要求： 1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列； 3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列； 4．求二叉树的深度/结点数目/叶结点数目； 5．将二叉树每个结点的左右子树交换位置； 6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）； 7. 计算二叉树最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）； 8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点。 给出具体代码

1. 按先序序列构造一棵二叉链表表示的二叉树T

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void createTree(struct TreeNode **root) {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        *root = NULL;
    } else {
        *root = malloc(sizeof(struct TreeNode));
        (*root)->val = val;
        createTree(&(*root)->left);
        createTree(&(*root)->right);
    }
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    return 0;
}

2. 对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void preOrder(struct TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->val);
        preOrder(root->left);
        preOrder(root->right);
    }
}

void inOrder(struct TreeNode *root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->val);
        inOrder(root->right);
    }
}

void postOrder(struct TreeNode *root) {
    if (root != NULL) {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->val);
    }
}

void levelOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct TreeNode *temp = queue[front++];
        printf("%d ", temp->val);
        if (temp->left != NULL) {
            queue[rear++] = temp->left;
        }
        if (temp->right != NULL) {
            queue[rear++] = temp->right;
        }
    }
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    printf("preOrder: ");
    preOrder(root);
    printf("\n");
    printf("inOrder: ");
    inOrder(root);
    printf("\n");
    printf("postOrder: ");
    postOrder(root);
    printf("\n");
    printf("levelOrder: ");
    levelOrder(root);
    printf("\n");
    return 0;
}

3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void preOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[1000];
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        struct TreeNode *temp = stack[top--];
        printf("%d ", temp->val);
        if (temp->right != NULL) {
            stack[++top] = temp->right;
        }
        if (temp->left != NULL) {
            stack[++top] = temp->left;
        }
    }
}

void inOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[1000];
    int top = -1;
    struct TreeNode *temp = root;
    while (top >= 0 || temp != NULL) {
        while (temp != NULL) {
            stack[++top] = temp;
            temp = temp->left;
        }
        temp = stack[top--];
        printf("%d ", temp->val);
        temp = temp->right;
    }
}

void postOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *stack[1000];
    int top = -1;
    struct TreeNode *prev = NULL;
    stack[++top] = root;
    while (top >= 0) {
        struct TreeNode *temp = stack[top];
        if ((temp->left == NULL && temp->right == NULL) || (prev != NULL && (prev == temp->left || prev == temp->right))) {
            printf("%d ", temp->val);
            top--;
            prev = temp;
        } else {
            if (temp->right != NULL) {
                stack[++top] = temp->right;
            }
            if (temp->left != NULL) {
                stack[++top] = temp->left;
            }
        }
    }
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    printf("preOrder: ");
    preOrder(root);
    printf("\n");
    printf("inOrder: ");
    inOrder(root);
    printf("\n");
    printf("postOrder: ");
    postOrder(root);
    printf("\n");
    return 0;
}

4. 求二叉树的深度/结点数目/叶结点数目

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int treeDepth(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = treeDepth(root->left);
    int rightDepth = treeDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

int nodeCount(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return nodeCount(root->left) + nodeCount(root->right) + 1;
}

int leafCount(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return leafCount(root->left) + leafCount(root->right);
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    printf("tree depth: %d\n", treeDepth(root));
    printf("node count: %d\n", nodeCount(root));
    printf("leaf count: %d\n", leafCount(root));
    return 0;
}

5. 将二叉树每个结点的左右子树交换位置

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void swap(struct TreeNode **p, struct TreeNode **q) {
    struct TreeNode *temp = *p;
    *p = *q;
    *q = temp;
}

void mirror(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    mirror(root->left);
    mirror(root->right);
    swap(&root->left, &root->right);
}

void levelOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode *queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct TreeNode *temp = queue[front++];
        printf("%d ", temp->val);
        if (temp->left != NULL) {
            queue[rear++] = temp->left;
        }
        if (temp->right != NULL) {
            queue[rear++] = temp->right;
        }
    }
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    mirror(root);
    levelOrder(root);
    printf("\n");
    return 0;
}

6. 设计二叉树的双序遍历算法

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void doubleOrder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    doubleOrder(root->left);
    printf("%d ", root->val);
    doubleOrder(root->right);
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    doubleOrder(root);
    printf("\n");
    return 0;
}

7. 计算二叉树最大宽度

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

#define MAX(a, b) ((a) > (b) ? (a) : (b))

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int treeWidth(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    struct TreeNode *queue[1000];
    int front = 0, rear = 0, max = 0;
    queue[rear++] = root;
    while (front < rear) {
        int count = rear - front;
        max = MAX(max, count);
        while (count--) {
            struct TreeNode *temp = queue[front++];
            if (temp->left != NULL) {
                queue[rear++] = temp->left;
            }
            if (temp->right != NULL) {
                queue[rear++] = temp->right;
            }
        }
    }
    return max;
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    printf("tree width: %d\n", treeWidth(root));
    return 0;
}

8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点

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

#define MAX(a, b) ((a) > (b) ? (a) : (b))

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct Result {
    int depth;
    struct TreeNode *node;
};

struct Result *maxPath(struct TreeNode *root) {
    if (root == NULL) {
        return NULL;
    }
    struct Result *leftResult = maxPath(root->left);
    struct Result *rightResult = maxPath(root->right);
    struct Result *result = malloc(sizeof(struct Result));
    result->depth = 0;
    result->node = root;
    if (leftResult != NULL && leftResult->depth > result->depth) {
        result->depth = leftResult->depth;
        result->node = leftResult->node;
    }
    if (rightResult != NULL && rightResult->depth > result->depth) {
        result->depth = rightResult->depth;
        result->node = rightResult->node;
    }
    result->depth++;
    return result;
}

int main() {
    struct TreeNode *root = NULL;
    createTree(&root);
    struct Result *result = maxPath(root);
    printf("max path length: %d\n", result->depth - 1);
    printf("max path: ");
    while (result->node != NULL) {
        printf("%d ", result->node->val);
        result = maxPath(result->node->left);
        if (result == NULL) {
            result = maxPath(result->node->right);
        }
    }
    printf("\n");
    return 0;
}