首页 > 试题广场 >

n个结点的线索二叉树上含有的线索数为 。

[单选题]

n个结点的线索二叉树上含有的线索数为 。 


  • 2n
  • n＋l
  • n－l
查看正确选项
添加回答
Bick小魔王头像 Bick小魔王
无论是什么样的二叉链表，空线索数由度为1和度为0的节点所提供，其中一个度为1的节点提供1个空线索数，一个度为0的节点提供2个空线索数，即总的空线索数为2*n0+n1，又因为n0=n2+1，所以2*n0+n1=n0+n1+n2+1=n+1。
发表于 2018-05-10 10:29:14 回复(1)
Minygd头像 Minygd
含n个节点的二叉树共有n-1条边，而n个节点共2n个指针域。
所以线索数 = 2n - (n - 1) = n+1
发表于 2019-01-04 19:11:38 回复(0)
eraios头像 eraios

通过考察各种二叉链表，不管二叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。因此线索二叉树的线索数为二叉链表中的空链域的值

编辑于 2017-07-21 17:08:32 回复(1)
oylp头像 oylp
有n-1个用于放子节点，所以有n+1放线索 
发表于 2017-07-10 18:17:06 回复(0)
sunlight_run头像 sunlight_run
《大话数据结构》例子中，有10个节点，共有11个空指针被用来当线索。至于公式推导不会~哈哈
发表于 2017-06-27 15:44:09 回复(0)
不做人了头像 不做人了
有n-1个用于放子节点，所以有n+1放线索 
发表于 2020-06-11 10:41:23 回复(0)
Linny_mm头像 Linny_mm
x0个度为0的节点，x1个度为1的节点，x2个度为2的节点
x0+x1+x2=n=节点个数
x1+2*x2=n-1=边的个数
线索数=2*x0+x1=2*n-(n-1)=n+1

发表于 2023-03-23 21:05:38 回复(0)
牛客2817416号头像 牛客2817416号
二叉树的节点个数 n = 分支总数加+1
即  n = x+1    =====>所以求得分支总数为 x = n-1，
然后如果一棵树是线索树，那么分支总数为  2*n。
所以说线索分支:y+原有分支 = 应该等于 2*n
所以 2 * n = y+n-1
所以 y = n+1
发表于 2019-08-20 09:31:26 回复(0)
提交观点

问题信息

树
上传者：娃哈哈呀~
难度：
8条回答 6918浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号