[工学]数据结构6树.pptVIP

软件水平考试有关试题 2007-1 2002 假设一棵二叉树的后序遍历序列为 D G J H E B I F C A，中序遍历序列为 D B G E H J A C I F，则其前序遍历序列 为 。 A）A B C D E F G H I J B）A B D E G H J C F I C）A B D E G H J F I C D）A B D E G J H C F I A B D E G H J C F I 2006-2 若某二叉树的先序遍历序列和中序遍历序列分别为 PBECD、BEPCD，则该二叉树的后序遍历序列为 （38） 。　　A. PBCDE　　　 B. DECBP 　　 C. EBDCP　　　 D. EBPDC 1999试题2 二叉树的查找有深度优先和广度优先二类，深度优先包括_C_。当一棵二叉树的前序序列和中序序列分别是 H G E D B F C A 和 E G B D H F A C时，其后序序列必是_D_,层次序列为_E_. C: (1)前序遍历 后序遍历 中序遍历 (2)前序遍历 后序遍历 层次遍历 (3)前序遍历 中序遍历 层次遍历 (4)中序遍历 后序遍历 层次遍历 D: (1) B D E A G F H C (2) E B D G A C F H (3) H G F E D C B A (4) H F G D E A B C H G E D B F C A E: (1) B D E A C G F H (2) E B D G A C F H (3) H G F E D C B A (4) H F G C D E A B 软件设计师 2004上半年 设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。 A．x是y的左兄弟 B．x是y的右兄弟 C．x是y的祖先 D．x是y的后裔 三、遍历的递归算法 1 . 先序遍历（DLR） 2 . 中序遍历（LDR） 3. 后序遍历（RDL） 先序遍历（DLR）的递归算法 void preorder（btree *t） { 若二叉树t非空，则： 访问根结点t 前序遍历t的左子树 前序遍历t的右子树 if (t) { putchar(t-data); preorder(t-lchild); preorder(t-rchild); } } 中序遍历、后序遍历的递归算法 中序遍历 void inorder（bitree *t） { if ( t ) { inorder(t-lchild); putchar(t-data); inorder(t-rchild); } } 后序遍历 void postorder（bitree *t） { if ( t ) { postorder(t-lchild); postorder(t-rchild); putchar(t-data); } } 四、遍历的非递归算法 提问： 二叉树遍历算法的递归版本简洁而又好懂，既然有这么好的算法，为何还要去改成非递归版本呢？ 回答： 因为在有些场和，出于性能和条件的考虑，无法使用递归机制，这就必须借助非递归来实现相应的递归算法。 实现递归与非递归的换转原理分析 1.函数的调用、返回机制 一个函数在调用另一个函数之前，要作三件事： a)将实在参数，返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区; c)将控制转移到被调函数的入口。 从被调用函数返回调用函数之前，要做三件事： a)保存被调函数的计算结果; b)释放被调函数的数据区; c)依照被调函数保存的返回地址将控制转移到调用函数。 两个问题： 数据保存在哪里？（不论是变量还是地址，本质上来说都是”数据” ） 如何实现“控制转移”？ 结论1： 递归调用时数据都是保存在栈中的，有多少个数据需要保存就要设置多少个栈，而且最重要的一点是：控制所有这些栈的栈顶指针都是相同的，否则无法实现同步。 因此：在非递归算法中定义相应的栈来做为辅助的存储空间。 结论2： 递归调用时是通过函数的入口地址实现“控制转移”的。 因此：在非递归中，程序需要知道到底要转移到哪个部分继续执行，即找到控制变换的因素或条件。 例如：二叉树的遍历 二叉树的三种遍历方