若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树

[单选题]

若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。

```
先序
```
```
中序
```
```
后序
```
```
按层次
```

友好的母单花在喝茶

在《算法与数据结构第三版》中，第6章第55题为此题。故将书上解析书写如下：

ac均可，若二叉树非空，先交换左右子树，再先序递归交换左子树，先序递归交换右子树

若二叉树非空，后序递归交换左子树，在后序递归交换右子树，最后交换左右子树

发表于 2022-04-09 14:23:51 回复(1)

天尊墨宇

选C

用二叉链表存储结构也就是左孩子右兄弟的存储结构。

后序遍历比较合理。正常的逻辑应该就是：做好当前结点子树内部的交换，然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。
1、交换好左子树

2、交换好右子树

3、交换左子树与右子树

其他算法如先序和按层次其逻辑都差不多，即访问当前结点时交换其左右子树。从逻辑上来看稍显别扭一点点。因此说最合适应该是后序遍历，但是从实现上来说先序和按层次都是可以的。

1、交换左子树与右子树

2、遍历左子树

3、遍历右子树

按层次遍历

1、根结点入队列

2、出队列，交换其左右子树，将子树的根入队列

3、重复2直到队列为空

中序遍历相对较难实现一些。

发表于 2020-06-29 10:46:06 回复(1)