数据结构中的线索二叉树

在这里，我们将看到线索二叉树数据结构。我们知道二叉树节点最多可以有两个孩子。但是如果它们只有一个孩子或没有孩子，则链接列表表示中的链接部分仍然为空。使用线索二叉树表示，我们可以通过建立一些线程来重用该空链接。

如果一个节点有一些空闲的左孩子或右孩子区域，该区域将用作线程。线索二叉树有两种类型。单线索树或完全线索二叉树。在单线索模式下，还有另外两种变体。左线索和右线索。

在左线索模式下，如果某个节点没有左孩子，则左指针将指向其中序前驱，类似地，在右线索模式下，如果某个节点没有右孩子，则右指针将指向其中序后继。在这两种情况下，如果没有后继或前驱，则它将指向头节点。

对于完全线索二叉树，每个节点有五个域。三个域类似于普通二叉树节点，另外两个域用于存储布尔值以表示该边的链接是实际链接还是线程。

以下是左线索树和右线索树的示例

这是完全线索二叉树

Arnab Chakraborty

更新于： 2020 年 8 月 10 日

3K+ 浏览量

开启 职业生涯

完成课程，获得认证

开始