資料結構中的線索二叉樹

在這裡，我們將看到線索二叉樹資料結構。我們知道二叉樹節點最多可以有兩個孩子。但是如果它們只有一個孩子或沒有孩子，則連結列表表示中的連結部分仍然為空。使用線索二叉樹表示，我們可以透過建立一些執行緒來重用該空連結。

如果一個節點有一些空閒的左孩子或右孩子區域，該區域將用作執行緒。線索二叉樹有兩種型別。單線索樹或完全線索二叉樹。在單線索模式下，還有另外兩種變體。左線索和右線索。

在左線索模式下，如果某個節點沒有左孩子，則左指標將指向其中序前驅，類似地，在右線索模式下，如果某個節點沒有右孩子，則右指標將指向其中序後繼。在這兩種情況下，如果沒有後繼或前驅，則它將指向頭節點。

對於完全線索二叉樹，每個節點有五個域。三個域類似於普通二叉樹節點，另外兩個域用於儲存布林值以表示該邊的連結是實際連結還是執行緒。

以下是左線索樹和右線索樹的示例

這是完全線索二叉樹

Arnab Chakraborty

更新於： 2020 年 8 月 10 日

3K+ 瀏覽量

開啟 職業生涯

完成課程，獲得認證

開始