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

若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次
为什么选c不选d 有人说消耗大为什么？？？？？？

Soucula · 2018-4-30 01:52:52

显然后序遍历比较合理。正常的逻辑应该就是：做好当前结点子树内部的交换，然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。
1. 交换好左子树
2. 交换好右子树
3. 交换左子树与右子树
其他算法如先序和按层次其逻辑都差不多，即访问当前结点时交换其左右子树。从逻辑上来看稍显别扭一点点。因此说最合适应该是后序遍历，但是从实现上来说先序和按层次都是可以的。
1. 交换左子树与右子树
2. 遍历左子树
3. 遍历右子树
按层次遍历
1. 根结点入队列
2. 出队列，交换其左右子树，将子树的根入队列
3. 重复2直到队列为空
中序遍历相对较难实现一些。

头上长草小精灵 · 2018-4-30 01:52:53

从现实上来说先序是不可以的吧！

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

2 个回复

浏览过的版块