按照要求写出c语言代码1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列； 3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列； 4．求二叉树的深度/结点数目/叶结点数目； 5．将二叉树每个结点的左右子树交换位置； 6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这

个结点，最后按双序遍历它的右子树）。

以下是代码实现：

#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[1000];  // 定义队列
    int front = 0, rear = 0;
    queue[rear++] = root;  // 根结点入队列
    while (front < rear) {
        TreeNode* cur = queue[front++];
        printf("%d ", cur->val);
        if (cur->left != NULL) {  // 左孩子入队列
            queue[rear++] = cur->left;
        }
        if (cur->right != NULL) {  // 右孩子入队列
            queue[rear++] = cur->right;
        }
    }
}

// 先序遍历二叉树（非递归）
void preOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[1000];  // 定义栈
    int top = -1;
    stack[++top] = root;  // 根结点入栈
    while (top >= 0) {
        TreeNode* cur = stack[top--];
        printf("%d ", cur->val);
        if (cur->right != NULL) {  // 右孩子先入栈
            stack[++top] = cur->right;
        }
        if (cur->left != NULL) {  // 左孩子后入栈
            stack[++top] = cur->left;
        }
    }
}

// 中序遍历二叉树（非递归）
void inOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[1000];  // 定义栈
    int top = -1;
    TreeNode* cur = root;
    while (top >= 0 || cur != NULL) {
        while (cur != NULL) {  // 左孩子入栈
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top--];
        printf("%d ", cur->val);
        cur = cur->right;  // 右孩子入栈
    }
}

// 后序遍历二叉树（非递归）
void postOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[1000];  // 定义栈
    int top = -1;
    TreeNode* cur = root;
    TreeNode* lastVisited = NULL;  // 记录上一个访问的结点
    while (top >= 0 || cur != NULL) {
        while (cur != NULL) {  // 左孩子入栈
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top];
        if (cur->right == NULL || cur->right == lastVisited) {  // 右孩子为空或已经访问过
            printf("%d ", cur->val);
            lastVisited = cur;
            top--;
            cur = NULL;
        } else {  // 右孩子入栈
            cur = cur->right;
        }
    }
}

// 求二叉树的深度
int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
}

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

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

// 将二叉树每个结点的左右子树交换位置
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 main() {
    TreeNode* root = createTree();

    printf("先序遍历：");
    preOrder(root);
    printf("\n");

    printf("中序遍历：");
    inOrder(root);
    printf("\n");

    printf("后序遍历：");
    postOrder(root);
    printf("\n");

    printf("层次遍历：");
    levelOrder(root);
    printf("\n");

    printf("先序遍历（非递归）：");
    preOrderNonRecursive(root);
    printf("\n");

    printf("中序遍历（非递归）：");
    inOrderNonRecursive(root);
    printf("\n");

    printf("后序遍历（非递归）：");
    postOrderNonRecursive(root);
    printf("\n");

    printf("二叉树的深度：%d\n", maxDepth(root));
    printf("二叉树的结点数目：%d\n", countNodes(root));
    printf("二叉树的叶结点数目：%d\n", countLeaves(root));

    swapTree(root);

    printf("先序遍历：");
    preOrder(root);
    printf("\n");

    printf("双序遍历：");
    doubleOrder(root);
    printf("\n");

    return 0;
}