设 F 是一个森林,B 是由 F 变换得到的二叉树。若 F 中有 n 个非终端,则 B 中右指针域为空的结点有( )个。A.n-1B.nC.n+1D.n+2
时间: 2024-03-31 22:37:58 浏览: 47
首先,森林中的每棵树都可以变换成一棵二叉树。对于一棵有 $n$ 个结点的二叉树,有 $n+1$ 个空指针域。因为每个结点有两个指针域,而叶结点的指针域都为空,所以 $n$ 个非终端结点会有 $2n$ 个指针域,而一棵二叉树共有 $n+1$ 个空指针域,因此,空指针域的数量为 $2n-(n+1) = n-1$,选项 $\mathbf{A}$ 正确。
相关问题
设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有( )个。
### 回答1:
由F变换得的二叉树B具有以下性质:
1. F中的每个非终端结点在B中对应一个度为2的结点。
2. F中的每个叶子结点在B中对应一个度为1的结点。
3. F中的每个孩子兄弟结构在B中对应一个度为3的结点。
因此,B中总的结点数为2n(每个非终端结点对应一个度为2的结点,每个叶子结点对应一个度为1的结点),除了根节点外,每个结点都有一个左孩子和一个右孩子。而根据二叉树的性质,B中的叶子结点的右指针域为空。
因此,B中右指针域为空的结点数为n-1。
### 回答2:
设F中有n个非终端结点,则B中的二叉树有n+1个结点(包括非终端结点和终端结点)。
二叉树的性质是每个结点的右指针指向其右兄弟结点,如果没有右兄弟结点,则右指针为空。而F是一个森林,说明结点之间没有兄弟关系,因此B中只能有n个结点有右指针域。
所以,B中右指针域为空的结点有n个。
### 回答3:
设F中有n个非终端结点,那么根据二叉树的性质,B中的非空结点数为2n-1,其中根结点的右指针域为空。
对于其它非根结点,每个非终端结点有两个子结点,包括一个左子结点和一个右子结点。而对于右子结点来说,由于变换得到的B是二叉树,所以右子结点的右指针域为空。
综上所述,除了根结点外,B中的非终端结点都有一个右指针域为空,所以B中右指针域为空的结点个数为n-1。
答:B中右指针域为空的结点有(n-1)个。
9. 设 F 是一个森林,B 是由 F 变换得到的二叉树。若 F 中有 n 个非终端,则 B 中右指针域为空的结点有( )个。 A.n-1 B.n C.n+1 D.n+2
在一个二叉树中,右指针域为空的结点是指没有右儿子的结点。由于二叉树是由森林变换而来,因此在 F 中有 $n$ 个非终端时,B 中就有 $n+1$ 个结点。设 B 中有 $m$ 个右指针域为空的结点,则每个非叶结点都有一个右儿子,因此 B 中共有 $2n-m$ 个结点。又因为 B 是一棵二叉树,有 $n+1$ 个结点,因此有 $2n-m=n+1$,解得 $m=n+1$,即 B 中右指针域为空的结点有 $\textbf{(C)} n+1$ 个。
阅读全文