考研真题数据结构

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

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

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

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

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

（1）设计一个算法，将二叉树中所有非叶节点的左右子树交换位置，从而得到原二叉树的镜像二叉树。我们可以使用递归的方式来实现这个算法。 算法的基本思想如下： 1. 首先判断当前节点是否为空，如果为空则返回。 2. 交换当前节点的左右子树。 3. 对当前节点的左子树调用递归函数，实现左子树的镜像。 4. 对当前节点的右子树调用递归函数，实现右子树的镜像。 （2）下面是使用 C 语言编写的实现上述算法的代码： 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); } （3）算法的时间复杂度是 O(n)，其中 n 是二叉树中的节点数。算法的空间复杂度是 O(h)，其中 h 是二叉树的高度。