树和二叉树-数据结构教学幻灯片讲义.ppt

例题 选择题 5/5 5．对含有几个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A.0 B.1 C.2 D．不存在这样的二叉树 分析：该题主要考查二叉树的三种遍历次序的关系。三种遍历方式的不同点，在于访问根结点的时机不同。当一棵二叉树仅含一个根结点时，不管采用哪种遍历方式，所得到的结点序列总是相同的。 此题答案为B。 例题 判断题 1/4 1．按中序遍历二叉树时，某个结点（有右子树）的直接后继是它的右子树中第一个被访问的结点。 正确 分析：该题主要考查二叉树的中序遍历。这种说法正确。因为中序遍历按LDR的顺序进行，若以某结点为其直接后继，必须是右子树中第一个被访问的结点。 例题 判断题 2/4 2．有1个以上结点的二叉树，已知先序和后序遍历序列，能唯一确定一棵二叉树。 错误 分析：该题主要考查二叉树的遍历的性质。 这种说法不正确。如已知先序为 12 ，后序遍历为 21 ，则可以有两棵二叉树。 例题 判断题 3/5 3．用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历。 正确 分析：该题主要考查二叉树的遍历和逻辑结构。 用二叉树的先序遍历和中序遍历可以确定二叉树的逻辑结构，就可以进一步导出二叉树的后序遍历。 通常已知二叉树的先序遍历和后序遍历，无法确定一棵二叉树。 例题 判断题 4/4 4．若一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是该二叉树的先序遍历序列的最后一个结点。 正确 分析：该题主要考查二叉树的遍历。 当一个叶子结点是某二叉树中序遍历的最后一个结点，则它一定位于二叉树的右子树上最右端，无论先序遍历或中序遍历，右子树上的最右端的叶子结点肯定最后访问。 若题中的叶子结点替换成普通结点，则命题不成立。 例题 填空题 1.N个结点的二叉树按某种遍历规则对结点从1到N依次递增编号，如果 (1)任一结点的编号等于它的左子树中的最小编号减1，则为［　　　　　］遍历； (2)某结点右子树中最小编号等于左子树中的最大编号加1，则为［　　　　　］遍历。 答案：先序，后序。 分析：该题主要考查二叉树的结构和遍历。 对于先序遍历，因为首先访问根结点，再先序遍历左子树，最后先序遍历右子树，所以根结点编号等于左子树的根结点编号减1。 对于后序遍历，因为首先后序遍历左子树，然后后序遍历右子树，最后访问根结点，所以右子树中最小编号等于左子树中的最大编号加1。 例题　应用题 1/2　 1．满足下列条件的非空二叉树具有什么形状？ (1)先序和中序相同 (2)中序和后序相同 (3)先序和后序相同 分析：该题主要考察二叉树的结构和遍历性质。 (1)只有一个结点或没有左子树的二叉树 (2)只有一个结点或没有右子树的二叉树 (3)只有一个结点的二叉树 例题　应用题 2/2 2．已知二叉树左右子树都含有m个结点，当m鹅时，试构造满足如下要求的所有二叉树。 (1）左右子树的先序与中序序列相同。 (2）左子树的中序与后序序列相同，右子树的先序与中序序列相同。 分析：该题由上题引中得到，主要考查二叉树的结构和遍历的性质 如图 。 例题　算法设计题　　 １．设两棵二叉树的根结点地址分别为P及Q，采用二叉链表的形式存储这二棵树上所有的结点。请编写程序，判断它们是否相似。 分析：该题主要考查二叉树遍历算法的应用。 所谓二棵二叉树S和t相似，要求： 它们都为空或都只有一个根结点； 或它们的根结点及左右子树均相似。 Status BiLike(BiTree P,BiTree Q){ if (P==NULLQ==NULL) return TRUE; if (P==NULL||Q==NULL) return FALSE; like1=BiLike(p-lchild,q-rchild); like2=BiLike(p-rchild,q-rchild); return (like1like2); }//BiLike 习题 填空题 1 ．某二叉树的先序遍历序列和后序遍历序列正好相反，则此二叉树一定是( ) A．空或只有一个结点 B．完全二叉树 C．单支树 D．高度等于结点数 2．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )。 A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 填空题 1．有( )种不同形态的二叉树可以按照中序遍历得到相同的abc序列。 2．已知二叉树先序为ABDEGCF，中序为DBGEACF，则后序一定是( ) 判断题 1．二叉树线索化后一定不存在空指针域。 2．非空的