引線二元樹

在計算機科學中，引線二元樹（或稱線索二元樹）是添加了直接指向節點的前驅和後繼的指針的二元樹。

定義

這是一個引線二元樹，有著指向父節點的特殊指針（圖中虛線所示）

引線二元樹 的定義如下:

「一個二元樹通過如下的方法「穿起來」：所有原本為空的右子節點指針改為指向該節點在中序序列中的後繼，所有原本為空的左子節點指針改為指向該節點的中序序列的前驅。」^[1]

線索二元樹能線性地走訪二元樹，從而比遞歸的中序走訪更快。使用引線二元樹也能夠方便的找到一個節點的父節點，這比顯式地使用父親節點指針或者棧效率更高。這在棧空間有限，或者無法使用存儲父節點的棧時很有作用（對於通過深度優先搜索來查找父節點而言）。 考慮這樣的例子：一個節點k有一個右子節點r，那麼r的左指針可能是指向一個子節點節點，或是一個指回k的線索。如果r有左子節點，這個左子節點同樣也應該有一個左子節點或是指回k的線索。對於所有的左子節點同理。因此沿著這些從r發出的左指針，我們最終會找到一個指回k的線索。這種特性是對稱的：當q是p的左子節點時，我們可以沿著q的右子節點找到一個指回p的線索。

傳統的二元樹一般都是以鏈式存儲的結構來表示。這樣，二元樹中的每個節點都可以用鍊表中的一個鏈節點來存儲，每個鏈節點就包含了若干個指針。但是，這種傳統的鏈式存儲結構只能表現出二元樹中節點之間的父子關係，而且不能利用空餘的指針來直接得到某個節點的在特定的走訪順序（先序，中序，後序）中的直接前驅和直接後繼。通過分析傳統的二元樹鏈式存儲結構表示的二元樹中，存在大量的空閒指針。若能利用這些空指針域來存放指向該節點的直接前驅或是直接後繼的指針，則可以進行某些更方便的運算。這些被重新利用起來的空指針就被稱為線索，加上了這些線索的二元樹就是引線二元樹。

線索化

對二元樹以某種走訪順序進行掃描並為每個節點添加線索的過程稱為二元樹的線索化，進行線索化的目的是為了加快查找二元樹中某節點的前驅和後繼的速度。 那麼在有N個節點的二元樹中需要利用N+1個空指針添加線索。這是因為在N個節點的二元樹中，每個節點有2個指針，所以一共有2N個指針，除了根節點以外每一個節點都有一個指針從它的父節點指向它，所以一共使用了N-1個指針。所以剩下2N-(N-1)個空指針。

參考文獻

1. Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1988, p. 175. ISBN 978-0-201-16116-8.