数据结构ch4作业(共5页).doc

精选优质文档-倾情为你奉上第四章习题4.3如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。解：设结点总数为n，叶子数n0，1度节点数n1，2度节点数n2。由题意得：n0=20 n1=10+15=25有由二叉树性质得：n2=n0-1=20-1=19所以，总结点数 n= n0+ n1+ n2=20+25+19=644.10证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：先序：ABCDEFGHI 先序：ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF 解：ABCDEFGHIABCDEFGHIJ 对应二叉树 对应二叉树 ABCDEFG