考研真题数据结构

【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?是二叉树的高度。

?