数据结构 设F是森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中的右指针为空的结点有__
作者&投稿：晨古 （若有异议请与网页底部的电邮联系）
3个
C.n+1
森林转换为二叉树,遵循"左儿子右兄弟"的说法.
举个例子.树:根节点有三个儿子A,B,C.那么转换为二叉树后,根节点只有一个儿子A,然后A的兄弟B成为A的"儿子"(或者可以说是右指针域),C成为B的右指针域,此时C已经没有兄弟了,所以到此的一个右指针域为空.(你可以画图体会一下.)
题目中说F有n个非终端节点,所以转换为二叉树后所有的空的右指针域(right)就是n个.
根节点没有兄弟,所以该右指针域也为空.(注:这里根节点也是一个有指针域.上文中根节点属于非终端节点,那里它所指向的右指针域不是它本身而是它的最右边的儿子.)
所以综上,二叉树中右指针域为空的节点有(n+1)个.
楼主,这个我也是初学,有些语言不标准之处见谅.
ok, F是个森林，有n个非叶结点。现在设它有f个叶子结点。这（n+f）个结点转化成二叉树之后，一共会有（n+f+1）个指针。为什么？因为对每一个结点（根结点除外），都有一个指针指向它。再来，n个非叶结点到二叉树里，可能有两种形式，形式a:左右结点都有；形式b:只有左结点。f个叶结点到二叉树里，也可能有两种形式，形式c：只有右结点；形式d：左右结点都没有。形式为a的有a 个，b的有b个....列式：2a+b+c=n+f-1 a+b=b c+d=f 能解得b+d=n+1
答案是n + 1个，可以用归纳法证明的
蔽旭益母：[选项] A. n-1 B. n C. n+1 D. n+2 求详解
新乡市13391766881： 设F是一个森林,B是由F按自然对应关系转换而得到的二叉树,F中有n个非终端节点,则B中的右子树为空的节点有几个? - ？
蔽旭益母：[答案] 我感觉你说的不全呢?如果有图的话,那就拆掉右边的线,兄弟之间连线,旋转45度.其中拆掉的右节点即为你的要求.
新乡市13391766881： 请教数据结构一题？
蔽旭益母： 把森林F中的n个非终端结点分为两类:度为1的结点和度大于1的结点.度为1的结点 只有一个孩子,这个孩子在得到的二叉树B中必定没有右指针域;度大于1的结点 有两个或更多孩子,则最后一个孩子必定在B中没有右指针域;以上是由上一代的度的数量来判断下一代在B中的情况,这就漏掉了森林中的根结点(因为根结点没有父亲),而根结点在组成二叉树时右指针域为空的结点是必定会出现一个的,所以答案是 n+1
新乡市13391766881： 数据结构 二叉树设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是? (在这边根结点有算在内吗... - ？
蔽旭益母：[答案] m-n,根结点算在内. 二叉树的根结点是第一棵树的根结点,它的左子结点是第一棵树的最左子结点,右子结点是下一棵树(相当于兄弟结点).一棵树对应的二叉树的根结点右子结点总是为空.
新乡市13391766881： 设F是由T1,T2和T3三棵树组成的森林 - ？
蔽旭益母： 根据森林和二叉树之间的转换关系,二叉树的左子树是其根节点对应的孩子,二叉树的右子树是其根节点对应的兄弟.所以答案有三个: 1、如若二叉树B选择T1的根节点为它的根节点,则其左子树的个数就是T1去除根节点的个数,即n1-1个;...
新乡市13391766881： 有关二叉树的数据结构题...(请说明原因,谢谢,会增加悬赏)？
蔽旭益母： 选C. 定量理解,左孩子,右兄弟: F中n个非终叶节点,所有n棵势大于1的子树,任何一n个非终叶节点,都构成一棵子树,所有在B中有n组“右兄弟”,每组有一个尽头(叶节点),一定没有右孩子,另外F森林的所有根节点连成兄弟,右多出一个尽头(叶节点),所以总共n+1个.
新乡市13391766881： 数据结构,两颗树组成的森林转换成二叉树,如果两棵树本来就是二叉树,是直接把根节点连起来还是按照书上 - ？
蔽旭益母： 数据结构,两颗树组成的森林转换成二叉树,如果两棵树本来就是二叉树,是直接把根节点连起来还是按照书上的方法,把每个树转换成二叉树,在把第一个树的根节点的右指针指向第二个树的右指针? 【回答】:应先把每个树转换成二叉树,在把第一个树的根节点的右指针指向第二个树的根.你这个图中画的都不对正确的应是: ..... A / ...... \ B........ D .\........ / ....C.... E ............. \ ..................F (点请无视之,不知道,最近空格不知为何不起作用了)
新乡市13391766881： 已知二叉树的前序序列和中序序列,编写递归算法构造该二叉树,以广义表形式输出结果.速求 - ？
蔽旭益母： #include＂stdio.h＂#include <string.h>#include＂stdlib.h＂ char pre[] ={'A','B','D','H','L','E','K','C','F','G'}; char mid[] ={'H','L','D','B','E','K','A','F','C','G'}; typedef struct _Node { char v; struct _Node *left; struct _Node *right; }Node,*PNode; int Position(char ...
