设森林F由n棵树组成,它的第一棵树,第二棵树,…,第n棵树分

[填空题]

设森林F由n棵树组成,它的第一棵树,第二棵树,…,第n棵树分别有t1 ,t2, ... ,tn个节点,则与森林F对应的二叉树中,根节点的左子树有1个节点。

查看答案及解析

乌鲁鲁

t1-1

解：Forest = {T1，T2，... ，Tn}

Forest transformed to Binary Tree：

（1）、先将所有树转成一种特殊的树

（兄弟节点连线，断开除该层左第一个节点外的兄弟节点与parent的连线）

（2）、该特殊的树，根节点只有左子树

（3）、for all Ti belongs to Forest:

Ti -> right child = T(i+1) -> root

这样，整个森林转成的二叉树的根节点的左子树就是T1去掉根节点的子树，所以该森林二叉树根节点的左子树节点数量为t1 - 1

编辑于 2018-12-18 17:14:26 回复(0)

牛客169280127号

发表于 2018-12-10 18:41:07 回复(0)

提交观点

问题信息

树

上传者：小小

难度：

2条回答 3收藏 2364浏览

扫一扫，把题目装进口袋