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

?