数据结构考研分类复习真题 第六章 答案 (四)[19]

数据结构考研分类复习真题 第六章 答案 (四)[19]  

　　 ．M叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应

　　 ．前序遍历是 根左右 中序遍历是 左根右 后序遍历是 左右根 若将 根 去掉 三种遍历就剩 左右 三种遍历中的差别就是访问根结点的时机不同 二叉树是递归定义的 对左右子树均是按左右顺序来遍历的 因此所有叶子结点间的先后关系都是相同的

　　 ．本题的核心是三种遍历的顺序 根左右 左根右 左右根 但对本题的解答必须先定义结点间相互关系的 左右 本解答中将N是M的左子女 当作N在M 的左边 而N是M的右子女 当作N在M 的右边 若定义P是M和N的最近公共祖先 N在P的左子树中 M在P的右子树中 称N在M 的左边 那时的答案是不一样的

　　 ．HIDJKEBLFGCA