数据结构的问题本人小白..看了都觉得晕晕..1.已知某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG,请画出该二叉树，并写出该二叉树的后序序列..2.写出把两个有序表A[0….n-1],B[0….n-1]合并成

Question

数据结构的问题 本人小白..看了都觉得晕晕..
1.已知某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG,请画出该二叉树，并写出该二叉树的后序序列..
2.写出把两个有序表A[0….n-1],B[0….n-1]合并成一个有序表C[0….2n-1]的算法.
3.写出层次遍历二叉树的算法。（提示：可以利用队列作为辅助工具)

Answer 1

1.知道前序和中序推导树的形状有固定的方法：前序的第一个字母是D。找D在中序的位置，D左面有ABC，右面有EFG，那么这个树的根就是D，左子树的结点有ABC，右子树的结点有EFG。然后再看前序第二个字母B，再看B在中序的位置，左面有A，后面有C，这样就可以推断出结点B是D的左孩子，B的左孩子是A，右孩子是C。以此类推。后序序列为acbegfd
2.排序算法中的归并算法(merge sort)你记得吗？里面就有将两个有序表合成一个大有序表的算法。
3.第一步：根节点入队；第二步：这步是一个循环，从队中取出一个结点并输出该结点的字母，然后将该结点的左右孩子分别插入队列中（如果没有则不用插入），如此循环以致队列为空