首页 > 试题广场 >

用三叉链表作二叉树的存储结构,当二叉树中有n个结点时,有()

[单选题]
用三叉链表作二叉树的存储结构,当二叉树中有n个结点时,有()个空指针。
  • n+1
  • n
  • n+2
  • n-1
三叉链表每个节点有三个指针域(左、亲、右),共3n个指针。
其中非空指针=亲(n-1个,因为根节点没有双亲)+左右(n-1,因为n个节点的二叉树有n-1条边)=2n-2;
所以空指针=3n-(2n-2)=n+2。
发表于 2015-10-30 16:27:35 回复(2)
三叉链表,每个节点有三个指针,左孩子,右孩子,父节点。
对于有n个节点的树结构,有n-1条边,每条边是孩子节点指向父节点的指针,也是父节点指向孩子节点的孩子指针, 所以一共是2(n-1)个指针,总的指针就是3n-2(n-1)=n+2
发表于 2015-11-02 11:09:24 回复(4)
三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在于,它的结点比二叉链表的结点多一个指针域,该域用于存储一个指向本结点双亲的指针。三叉链表的结点形式如下:
发表于 2015-10-31 21:43:57 回复(0)
n=1 时,只有根节点,空指针的个数为3   C正确
发表于 2016-07-27 11:17:52 回复(1)
根据个人理解画了一张图
发表于 2021-11-20 10:31:30 回复(0)
二叉树总的节点个数为n = n0 + n1 + n2; 其中 n0 = n2 + 1;
而空指针的个数来源🈶️3个:叶子节点 * 2 + 只有一个孩子的节点 + 根节点(根节点中无父节点)
即 m = 2 * n0 + n1 + 1; 综上可得 m = n + 2.
发表于 2018-10-10 13:35:23 回复(0)
普通二叉链表的有n个结点的二叉树,将当前二叉树中的空指针看做叶子结点,则树中原有的所有结点都成了双分支结构。因此由n0=n2+1可得空指针个数为n+1个,而三叉链表中只有根结点没有双亲结点指针为空,故空指针为n+2。
发表于 2018-08-24 01:33:06 回复(0)
三叉链表结点:左孩子,右孩子,父节点,n个结点的二叉树有n-1条边,即对应2(n-1)个指针域(即一条边对应一个孩子指针和一个父亲指针),总指针域数量为3n,故空域为n+2
编辑于 2021-12-03 12:16:18 回复(0)
高中时的特值法应该立马见效!如,3个结点的例子。
发表于 2016-09-16 18:26:03 回复(1)
中间指针是用来指向父节点的,就解释通了。
发表于 2015-10-30 19:40:04 回复(0)
这题的错因是忘了三叉链表就是加了一个指向双亲的指针,我还以为是用三叉树的结点存储二叉树,算到最后结果每一个对的,我就乱选了一个。所以解法应该是,只有根结点的双亲指针为NULL,故双亲指针非空数目为n-1,左右孩子指针非空数目=孩子的个数=树的度=n-1,因此总空指针域=3n-(n-1)-(n-1)=n+2
发表于 2022-07-25 20:32:29 回复(0)
左右指针非空:n-1,亲指针非空:n-1,总指针:3n,则,
空指针=3n-[(n-1)+(n-1)]=n+2;

发表于 2021-05-05 12:05:51 回复(0)
三叉链表每个结点有三个指针域(左、亲、右) 共3n个指针
其中非空指针=亲(n-1个,因为根节点没有双亲) + 左右 (n-1,因为n个结点的二叉树有n-1条边) = 2n-2
所以空指针为3n-(2n-2) = n+2
发表于 2021-03-19 20:03:51 回复(0)
三叉链表每个节点有三个指针:lchildrchildparent,分别指向左孩子、右孩子和父节点,因此共3n个指针;
二叉树属于简单连通图,有n-1条边,即有n-1个lchild或rchild非空;
二叉树中除了根节点外其余节点都有父节点,因此有n-1个parent非空;
所以,空指针有3n-(n-1)-(n-1)=n+2个。
发表于 2018-08-15 00:19:16 回复(0)
三叉链表原来是左右亲,我以为是左右值
发表于 2018-06-03 14:42:27 回复(0)
对于选择题,特殊法最快,对于只有一个根结点1

它的*parent *lchild *rchild   指针都是空,也就是3个空指针,
答案选n+2 
发表于 2017-07-11 16:30:40 回复(0)
n个节点,共有3n个指针
n个节点,有n-1条边,每天边都有父指针指向子,同时子指向父节点,共2(n-1)个指针
所以空指针有3n-2(n-1)=n+2
发表于 2017-06-27 16:04:39 回复(0)
1 n=n0+n1+n2 2 n0=n2+1 得 n2=n0-1 n1的节点包含一个空指针 n0的包含2个空指针 n2为0空指针 则总空指针为 2*n0+1*n1 联合1 2式 得到2n0+n1=n-1 请问我这个算的是不是有哪里不对的???
发表于 2017-06-05 15:54:39 回复(0)
选C,详情请见百度上的介绍
http://baike.baidu.com/link?url=sVc0ZF80_YtNG_Iv-LBWM4vceUGwKtahehNnVC-DIVfsucrYEVR-Cu4dZHbKM2Gz44phxE0GTT-lIdOIRV82da
发表于 2015-11-22 22:04:33 回复(0)