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

以下是二叉树基本操作的C语言代码实现：

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

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

// 创建二叉树
TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

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

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

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

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

// 非递归先序遍历
void preOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        TreeNode* node = stack[top--];
        printf("%d ", node->val);
        if (node->right != NULL) {
            stack[++top] = node->right;
        }
        if (node->left != NULL) {
            stack[++top] = node->left;
        }
    }
}

// 非递归中序遍历
void inOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    TreeNode* node = root;
    while (node != NULL || top >= 0) {
        while (node != NULL) {
            stack[++top] = node;
            node = node->left;
        }
        node = stack[top--];
        printf("%d ", node->val);
        node = node->right;
    }
}

// 非递归后序遍历
void postOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    TreeNode* node = root;
    TreeNode* lastVisit = NULL;
    while (node != NULL || top >= 0) {
        while (node != NULL) {
            stack[++top] = node;
            node = node->left;
        }
        node = stack[top];
        if (node->right == NULL || node->right == lastVisit) {
            printf("%d ", node->val);
            lastVisit = node;
            top--;
            node = NULL;
        } else {
            node = node->right;
        }
    }
}

// 求二叉树深度
int treeDepth(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 treeNodeCount(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return treeNodeCount(root->left) + treeNodeCount(root->right) + 1;
}

// 求二叉树叶结点数目
int treeLeafCount(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return treeLeafCount(root->left) + treeLeafCount(root->right);
}

// 交换二叉树每个结点的左右子树
void swapTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    swapTree(root->left);
    swapTree(root->right);
}

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

// 计算二叉树最大宽度
int maxTreeWidth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    TreeNode* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int maxWidth = 1;
    while (front != rear) {
        int size = rear - front;
        maxWidth = maxWidth > size ? maxWidth : size;
        while (size--) {
            TreeNode* node = queue[front++];
            if (node->left != NULL) {
                queue[rear++] = node->left;
            }
            if (node->right != NULL) {
                queue[rear++] = node->right;
            }
        }
    }
    return maxWidth;
}

// 求二叉树中第一条最长的路径长度，并输出此路径上各结点
void maxPath(TreeNode* root, int* maxLen, int* pathLen, int* path) {
    if (root == NULL) {
        return;
    }
    path[pathLen++] = root->val;
    if (root->left == NULL && root->right == NULL) {
        if (pathLen > *maxLen) {
            *maxLen = pathLen;
            for (int i = 0; i < pathLen; i++) {
                printf("%d ", path[i]);
            }
            printf("\n");
        }
    } else {
        maxPath(root->left, maxLen, pathLen, path);
        maxPath(root->right, maxLen, pathLen, path);
    }
    pathLen--;
}

int main() {
    TreeNode* root = createTree();
    printf("先序遍历：");
    preOrder(root);
    printf("\n中序遍历：");
    inOrder(root);
    printf("\n后序遍历：");
    postOrder(root);
    printf("\n层次遍历：");
    levelOrder(root);
    printf("\n非递归先序遍历：");
    preOrderNonRecursive(root);
    printf("\n非递归中序遍历：");
    inOrderNonRecursive(root);
    printf("\n非递归后序遍历：");
    postOrderNonRecursive(root);
    printf("\n树的深度：%d\n", treeDepth(root));
    printf("结点数目：%d\n", treeNodeCount(root));
    printf("叶结点数目：%d\n", treeLeafCount(root));
    swapTree(root);
    printf("交换左右子树后的先序遍历：");
    preOrder(root);
    printf("\n双序遍历：");
    doubleOrder(root);
    printf("\n最大宽度：%d\n", maxTreeWidth(root));
    int maxLen = 0, pathLen = 0;
    int path[100];
    printf("最长路径：");
    maxPath(root, &maxLen, &pathLen, path);
    return 0;
}