首页 > 试题广场 >

二叉树在线索化后，仍不能有效求解的问题是( ).

[单选题]

二叉树在线索化后，仍不能有效求解的问题是( ). 


  • 先序线索二叉树中求先序后继
  • 中序线索二叉树中求中序后继
  • 中序线索二叉树中求中序前驱
  • 后序线索二叉树中求后序后继
添加回答
推荐
白驹之过隙头像 白驹之过隙
选D。考察的二叉链表线索化相关的概念
线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程。
  • 前序遍历（根左右）最后访问的节点都有空的右指针域，以指向后继
  • 中序遍历（左根右）最后访问的节点都有空的右指针域，以指向后继
  • 后续遍历（左右根）最后访问的子树的根节点，子树根节点的两个指针域都指向子树了，所以不能空出来存放线索信息。
编辑于 2019-09-11 14:15:06 回复(0)
August-us2020头像 August-us2020
不能解决的是先序求先驱和后序求后继，因为这两种都要找父节点，而如果左右指针都是存在的，就找不到到父节点的线索
发表于 2019-09-10 21:42:02 回复(0)
天尊墨宇头像 天尊墨宇
选D。考察的二叉链表线索化相关的概念
线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程。
  • 前序遍历（根左右）最后访问的节点都有空的右指针域，以指向后继
  • 中序遍历（左根右）最后访问的节点都有空的右指针域，以指向后继
  • 后续遍历（左右根）最后访问的子树的根节点，子树根节点的两个指针域都指向子树了，所以不能空出来存放线索信息。
发表于 2020-07-06 12:34:52 回复(0)
提交观点

问题信息

树
上传者：zsw3
难度：
3条回答 3247浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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