线索二叉树

传统的二叉链表仅能体现出一种父子关系,不能直接得到结点在遍历中的前驱或后继。引入【线索二叉树】正是为了加快查找结点前驱和后继的速度。
(1、定义

  • 前驱与后继:在二叉树的先序、中序或后序遍历序列中的两个相邻的结点
  • 线索:指向前驱或后继的结点的指针
  • 线索二叉树加上线索二叉链表二叉树
  • 线索化:对二叉树按某个遍历次序使其变为线索二叉树的过程。

(2、规定【口诀:左前右后,0孩1前后】

  • 无左子树,令lchild指向其前驱结点;
  • 无右子树,令rchild执行指向其后继结点
  • 增加两个标志域标识是指左/右孩子还是指向前驱/后继
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《线索二叉树》
文章链接:https://zhuji.vsping.com/4512.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。