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

很好，这是一道非常经典的二叉树操作题目。让我们来一一实现这些操作。

1. 构造二叉树

先定义二叉树的结构体类型和节点结构体类型：

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

typedef TreeNode* Tree;

然后我们可以使用先序遍历的方式构建二叉树：

Tree createTree() {
    int data;
    scanf("%d", &data);
    if (data == -1) {
        return NULL;
    }
    Tree root = (Tree)malloc(sizeof(TreeNode));
    root->data = data;
    root->left = createTree();
    root->right = createTree();
    return root;
}

这里我们规定输入 `-1` 表示空节点。

2. 递归遍历

我们可以使用递归的方式实现二叉树的先序、中序、后序和层次遍历：

void preOrder(Tree root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(Tree root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

void postOrder(Tree root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

void levelOrder(Tree root) {
    if (root == NULL) {
        return;
    }
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        Tree node = dequeue(&q);
        printf("%d ", node->data);
        if (node->left != NULL) {
            enqueue(&q, node->left);
        }
        if (node->right != NULL) {
            enqueue(&q, node->right);
        }
    }
}

其中 `Queue` 是一个队列结构体类型，需要实现队列的基本操作。这里不再赘述。

3. 非递归遍历

非递归遍历需要用到栈，分别对先序、中序和后序遍历进行实现：

void iterativePreOrder(Tree root) {
    Stack s;
    initStack(&s);
    push(&s, root);
    while (!isEmptyStack(&s)) {
        Tree node = pop(&s);
        printf("%d ", node->data);
        if (node->right != NULL) {
            push(&s, node->right);
        }
        if (node->left != NULL) {
            push(&s, node->left);
        }
    }
}

void iterativeInOrder(Tree root) {
    Stack s;
    initStack(&s);
    Tree node = root;
    while (!isEmptyStack(&s) || node != NULL) {
        if (node != NULL) {
            push(&s, node);
            node = node->left;
        } else {
            node = pop(&s);
            printf("%d ", node->data);
            node = node->right;
        }
    }
}

void iterativePostOrder(Tree root) {
    Stack s1, s2;
    initStack(&s1);
    initStack(&s2);
    push(&s1, root);
    while (!isEmptyStack(&s1)) {
        Tree node = pop(&s1);
        push(&s2, node);
        if (node->left != NULL) {
            push(&s1, node->left);
        }
        if (node->right != NULL) {
            push(&s1, node->right);
        }
    }
    while (!isEmptyStack(&s2)) {
        Tree node = pop(&s2);
        printf("%d ", node->data);
    }
}

4. 求树的深度、节点数目和叶节点数目

求树的深度可以使用递归的方式：

int getHeight(Tree root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

求节点数目也可以使用递归的方式：

int getNodeNum(Tree root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + getNodeNum(root->left) + getNodeNum(root->right);
}

求叶节点数目同样可以使用递归的方式：

int getLeafNum(Tree root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return getLeafNum(root->left) + getLeafNum(root->right);
}

5. 左右子树交换

这个操作很简单，只需要递归地交换每个节点的左右子树即可：

void swap(Tree root) {
    if (root == NULL) {
        return;
    }
    Tree temp = root->left;
    root->left = root->right;
    root->right = temp;
    swap(root->left);
    swap(root->right);
}

6. 双序遍历

按照定义，双序遍历需要先访问节点，然后先序遍历左子树，再次访问节点，最后先序遍历右子树。可以写出如下递归函数：

void doubleOrder(Tree root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    doubleOrder(root->left);
    printf("%d ", root->data);
    doubleOrder(root->right);
}

7. 计算二叉树最大宽度

这个问题可以使用层次遍历和队列来解决，统计每一层的节点数目，取最大值即可：

int getMaxWidth(Tree root) {
    if (root == NULL) {
        return 0;
    }
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    int maxWidth = 1;
    while (!isEmpty(&q)) {
        int levelWidth = q.size;
        maxWidth = levelWidth > maxWidth ? levelWidth : maxWidth;
        while (levelWidth--) {
            Tree node = dequeue(&q);
            if (node->left != NULL) {
                enqueue(&q, node->left);
            }
            if (node->right != NULL) {
                enqueue(&q, node->right);
            }
        }
    }
    return maxWidth;
}

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

这个问题可以使用递归来解决。我们需要找到一条路径，使得它的长度最长。这条路径有两种可能的情况：

1. 通过根节点，并且在左子树中找到最长的路径。
2. 通过根节点，并且在右子树中找到最长的路径。

我们可以递归地求出这两种情况的路径长度，并取较大值。同时，我们需要记录下这条最长路径，方便输出。可以使用一个数组记录路径经过的节点。

int findLongestPath(Tree root, int path[], int curLen, int* maxLen, int longestPath[]) {
    if (root == NULL) {
        return 0;
    }
    path[curLen++] = root->data;
    if (root->left == NULL && root->right == NULL) {
        if (curLen > *maxLen) {
            *maxLen = curLen;
            memcpy(longestPath, path, curLen * sizeof(int));
        }
    }
    int leftLen = findLongestPath(root->left, path, curLen, maxLen, longestPath);
    int rightLen = findLongestPath(root->right, path, curLen, maxLen, longestPath);
    return leftLen > rightLen ? leftLen + 1 : rightLen + 1;
}

最后，我们可以使用以下代码来测试这些函数的正确性：

int main() {
    Tree root = createTree();

    printf("Pre-order traversal (recursive): ");
    preOrder(root);
    printf("\n");

    printf("In-order traversal (recursive): ");
    inOrder(root);
    printf("\n");

    printf("Post-order traversal (recursive): ");
    postOrder(root);
    printf("\n");

    printf("Level-order traversal: ");
    levelOrder(root);
    printf("\n");

    printf("Pre-order traversal (iterative): ");
    iterativePreOrder(root);
    printf("\n");

    printf("In-order traversal (iterative): ");
    iterativeInOrder(root);
    printf("\n");

    printf("Post-order traversal (iterative): ");
    iterativePostOrder(root);
    printf("\n");

    printf("Height of the tree: %d\n", getHeight(root));
    printf("Number of nodes in the tree: %d\n", getNodeNum(root));
    printf("Number of leaf nodes in the tree: %d\n", getLeafNum(root));

    printf("Max width of the tree: %d\n", getMaxWidth(root));

    int maxLen = 0;
    int path[100];
    int longestPath[100];
    findLongestPath(root, path, 0, &maxLen, longestPath);
    printf("Longest path (%d): ", maxLen);
    for (int i = 0; i < maxLen; i++) {
        printf("%d ", longestPath[i]);
    }
    printf("\n");

    swap(root);

    printf("Pre-order traversal after swapping: ");
    preOrder(root);
    printf("\n");

    printf("Double order traversal: ");
    doubleOrder(root);
    printf("\n");

    return 0;
}