考研真题数据结构

【2021年山西大学真题】将二叉树中所有非终端结点的左右子树交换位置，可以得到原二叉树的

镜像二叉树，如图。假设二叉树的存储形式为（lchild，data，rchild），给出求镜像二叉树的算法:

（1）给出算法的基本思想；

（2）根据设计思想，写出算法；

（3）讨论算法的时间复杂度和空间复杂度.

---

（1）设计一个算法，将二叉树中所有非叶节点的左右子树交换位置，从而得到原二叉树的镜像二叉树。我们可以使用递归的方式来实现这个算法。
算法的基本思想如下：
1. 首先判断当前节点是否为空，如果为空则返回。
2. 交换当前节点的左右子树。
3. 对当前节点的左子树调用递归函数，实现左子树的镜像。
4. 对当前节点的右子树调用递归函数，实现右子树的镜像。

（2）下面是使用 C 语言编写的实现上述算法的代码：

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

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

void mirrorBinaryTree(Node* root) {
    if (root == NULL) {
        return; // 如果当前节点为空，直接返回
    }

    // 交换当前节点的左右子树
    Node* temp = root->left;
    root->left = root->right;
    root->right = temp;

    // 递归处理左子树和右子树
    mirrorBinaryTree(root->left);
    mirrorBinaryTree(root->right);
}

// 测试代码
void printBinaryTree(Node* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->data);
    printBinaryTree(root->left);
    printBinaryTree(root->right);
}

int main() {
    Node* root = (Node*)malloc(sizeof(Node));
    Node* node1 = (Node*)malloc(sizeof(Node));
    Node* node2 = (Node*)malloc(sizeof(Node));
    Node* node3 = (Node*)malloc(sizeof(Node));
    Node* node4 = (Node*)malloc(sizeof(Node));
    Node* node5 = (Node*)malloc(sizeof(Node));
    Node* node6 = (Node*)malloc(sizeof(Node));

    root->data = 1;
    node1->data = 2;
    node2->data = 3;
    node3->data = 4;
    node4->data = 5;
    node5->data = 6;
    node6->data = 7;

    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node1->right = node4;
    node2->left = node5;
    node2->right = node6;
    node3->left = NULL;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;
    node5->left = NULL;
    node5->right = NULL;
    node6->left = NULL;
    node6->right = NULL;

    printf("原二叉树：");
    printBinaryTree(root);
    printf("\n");

    mirrorBinaryTree(root);

    printf("镜像二叉树：");
    printBinaryTree(root);
    printf("\n");

    return 0;
}
```

在上述代码中，我们首先定义了一个 `Node` 结构体来表示二叉树的节点。然后，我们编写了一个递归函数 `mirrorBinaryTree`，用于实现二叉树节点交换的操作。通过递归调用，我们可以将二叉树中所有非叶节点的左右子树交换位置，并得到镜像二叉树。在 `main` 函数中，我们创建了一个测试用例，并分别输出原二叉树和镜像二叉树的结果。

（3）算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数。算法的空间复杂度是 O(h)，其中 h 是二叉树的高度。