数据结构二叉树练习.pptVIP

* 判断： 1.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。 2.若一个结点是某二叉树子树的中序遍历序列的第一个结点，则它必是该子树的后序遍历中的第一个结点。 3.前序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。 4.完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。 5.满二叉树一定是完全二叉树。 6.由前序序列和后序序列能唯一确定一棵二叉树。 F F F F T F 选择： 1.后序遍历序列为dabec，中序遍历序列为debac，则前序遍历序列为（ ） A cbeda B decab C deabc D cedba D 2.下列说法正确的是（ ） A 二叉树中任何一个结点的度都为2 B 二叉树的度为2 C 一棵二叉树的度可小于2 D 任何一棵二叉树中至少有一个结点的度为2 C 3.某二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ ） A 空树或只有一个结点 B 完全二叉树 C 满二叉树 D 高度等于其结点数减1 D A 4.在一非空二叉树的中序遍历序列中，根结点的右边（ ） A 只有右子树上的所有结点 B 只有右子树上的部分结点 C 只有左子树上的部分结点 D 只有左子树上的所有结点 1 2 3 4 5.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（ ） A 不发生改变 B 发生改变 C 不能确定 D 以上都不对 A A B C D E F G H 前序遍历序列：ABDEGCFH 中序遍历序列：DBGEAFHC 后序遍历序列：DGEBHFCA 6.设n,m为一棵二叉树上的两个结点，在中序遍历时， n在m前的条件是（ ） A n在m右方 B n是m祖先 C n在m左方 D n是m子孙 C C 7.一棵二叉树的前序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG，则该二叉树根结点的右孩子为（ ） A. E B. F C. G D. H A B C D E G F H I J K 8.二叉树的前序序列和中序序列相同的条件是什么？ 答：前序遍历的遍历顺序为根左右，中序遍历的顺序为左根右，只有左为空或左右均为空时，两者相等。所以答案为：任何结点至多只有右子树。 9.二叉树的后序序列和中序序列相同的条件是什么？ 答：后序遍历的遍历顺序为左右根，中序遍历的顺序为左根右，只有右为空或左右均为空时，两者相等。所以答案为：任何结点至多只有左子树。 算法设计 1.假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有结点数。 public static int Nodes(BiTreeNode t){ int num1,num2; if(t==null) return 0; else if(t.getLeft()==nullt.getRight()==null) return 1; else{ num1=Nodes(t.getLeft()); num2=Nodes(t.getRight()); return(num1+num2+1); } } A B C D E F 2.假设二叉树采用二叉链存储结构存储，试设计一个算法，计算一棵给定二叉树的所有叶子结点个数。 public static int leafNodes(BiTreeNode t){ int num1,num2; if(t==null) return 0; else if(t.getLeft()==nullt.getRight()==null) return 1; else{ num1=leafNodes(t.getLeft()); num2=leafNodes(t.getRight()); return(num1+num2); } } A B C D E F 3.假设二叉树采用二叉链存储结构存储，试设计一个算法，求一棵给定二叉树的高度。 public static int BTNodeDepth(BiTreeNode t){ int lchilddep,rchilddep; if(t==null) return -1; else{ lchilddep=BTNodeDepth(t.getLeft()); rchilddep=BTNodeDepth(t.getRight());