Question

两个二叉树遍历选择题

1.二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适
A 前序 B 中序 C 后序 D 层次
解析上说层次遍历和后序遍历都能实现，但后序更好，具体是怎么实现的？

2.二叉树线索化后，仍不能有效求解的问题是（ ）
A 前序线索二叉树中求前序后继 B 中序线索二叉树中求中序后继
C 中序线索二叉树中求中序前驱 D 后序线索二叉树中求后序后继
补充两个数据结构问题，分数加到200
3.对于一个线性表，以下即能快速查找，又能适应动态变化的查找方式是（ ）
A 顺序查找 B 折半查找 C 分块查找 D 哈希查找
答案是C，分块查找也就是索引查找，时间复杂度介于顺序和折半之间，
但是怎么适应动态变化的我不理解？

4.对于一个二叉树，除叶子结点外，其余所有结点都大于中序遍历的前驱结点，小于中序遍历的后继结点，该二叉树是不是二叉排序树？为什么？举出反例

Answer 1

第一个题目我觉得后序遍历比较的说法比较牵强，有耐性的可以看看我的说法，欢迎交流，呵呵。
我是这么想：按题目的要求，互换左右子树的位置，要么从根开始，逐层互换，这当然就层次遍历了，在每一层将该层结点的左右子树位置都互换，这个不难理解，但是你想想，一层互换完了，下一层怎么开始互换呢？这就需要每层的结点的交换操作完毕后，记录该层所有的结点的地址，将他们保存起来(因为是二叉链表，保存地址是必要的)，要不然下一层互换就没法开始吧？！每一层的要开始互换，都要上一层的某个地址来获得到当前需要互换的结点地址，然后这个进行互换的结点的地址也要暂存，如此循环咯；

另外一种方法自然就是从叶子开始，自下而上了，采用前序遍历，这种属于自下而上交换的做法了，一定需要堆栈递归，抽象地说，访问二叉树的时候，把根压栈，继续访问左子树，直到碰到左叶子，之前路径上的结点都压栈嘛，这时左叶子就不压栈了，返回左叶子的双亲结点后访问它的右孩子为根的子树，做法同上，递归返回上一层的时候发现左右孩子都访问过了，进行一次位置的互换，然后再继续递归的返回(这个过程就是前序遍历啦，别看题目说什么后序遍历，二叉链表哦，分明就是要先把根结点压栈，先访问根结点，才能访问左右嘛，什么后序遍历，扯蛋)。当然题目才告诉我二叉树，我还分不出哪个方法最优，哥觉得题目比较扯蛋，关键还是楼主你自己要理解做法，多动脑筋而别去迷信题目答案。

第二个题目，只有中序遍历线索可以找到直接前驱和直接后继，这也是线索化的目的所在，但是前序线索化无法仅通过线索找到直接前驱，后序线索化无法通过仅通过线索找到直接后继，试想一下某个有左孩子又有右孩子的非根的中间结点就明白了。

Answer 2

1、实现：一般来说二叉树的递归操作都需要内外两层函数接力，如下。
void BinaryTree::change()//交换左右子树主函数
{
change_child(root);
}
void BinaryTree::change_child(node*root)//交换左右子树核心函数
{
if(root)
{
if(root->lchild)//左子树不为空则行递归
change_child(root->lchild);
if(root->rchild)//同上
change_child(root->rchild);
if(root->lchild||root->rchild)//左右子树不全为空则行交换
{
node*temp=root->lchild;
root->lchild=root->rchild;
root->rchild=temp;
}
}
}
我们必须彻底的理解交换的含义，方能做出正确的行为。交换左右子树并非交换某一根的左右儿子结点，而是以左右儿子为根的整棵树都要交换，并且任意结点都按同样方式行事。后序更能胜任的原因，在于其是自下而上逐步实现交换左右子树的，使得交换完美而又彻底。如果是其他序，比如前序的话，无法简单通过以上程序将左子树与右子树彻底交换，仅仅是交换左右儿子结点，所以其他方法需要更为复杂的对待。
2、本人理解不够深刻，所以答不随便。

Answer 3

3.分块查找流程如下：
step1 先选取各块中的最大关键字构成一个索引表；
step2 查找分两个部分：
①先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
②然后，在已确定的块中用顺序法进行查找。
适应动态变化就是说：如果你在这个集合中插入元素的话可以先找到刚好大于新元素的关键字所在的块，比如有如下块：
10,20,30,40
如果插入14的话就把14插入到关键字为20的块中，因为关键字是有序的，所以仍然可以用折半查找，而在块内使用顺序查找由于块的跨度不大所以开销也不大。
4.二叉排序树的定义：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；
对于叶子节点来说是否大于前驱小于后继不需要去判断，因为如果它不大于前驱A说明它的前驱A不小于它(A的后继)，如果不小于后继B说明后继不大于它(B的后继)。而且不会有两个叶子互为前驱后继。

Answer 4

1。后序之后其左右子树相对位置在其根节点之前，层序之后其左右子树相对位置在其根节点之后，在没有为指针情况下后序比层序查找起来简单。且后序相同根节点下左右节点位置相邻，交换起来比较简单
2。选D，严蔚敏的数据结构P133上说过，后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论