设森林F对应的二叉树B有m个结点。B的根为t,若t的右子树有n个结点,则森林 F中第一棵树具有多少个结点。
时间: 2024-03-29 14:36:01 浏览: 76
DS树和二叉树线索二叉树树和森林PPT学习教案.pptx
由森林到二叉树的转换可以得到:森林中树的个数 = 二叉树中度为2的结点个数 + 1。因此,森林中第一棵树的结点个数等于二叉树中度为1的结点个数加1。
我们知道二叉树中所有结点的度数之和为2m-1,因为每个结点的度数要么是1,要么是2。又因为t的度数为2,且右子树有n个结点,所以t的左子树中有m-n-1个结点。
因此,二叉树中度为1的结点个数为m-(m-n-1)-1=n+1,所以森林中第一棵树的结点个数为n+2。
阅读全文