text: 在計算機科學中，引線二元樹是添加了直接指向節點的前驅和後繼的指標的二叉樹。定義.線索二叉樹 的定義如下:“一個二叉樹透過如下的方法“穿起來”：所有原本為空的右子節點指標改為指向該節點在中序序列中的後繼，所有原本為空的左子節點指標改為指向該節點的中序序列的前驅。”線索二叉樹能線性地遍歷二叉樹，從而比遞迴的中序遍歷更快。使用線索二叉樹也能夠方便的找到一個節點的父節點，這比顯式地使用父親節點指標或者棧效率更高。這在棧空間有限，或者無法使用儲存父節點的棧時很有作用。考慮這樣的例子：一個節點"k"有一個右子節點"r"，那麼"r"的左指標可能是指向一個子節點節點，或是一個指回"k"的線索。如果"r"有左子節點，這個左子節點同樣也應該有一個左子節點或是指回"k"的線索。對於所有的左子節點同理。因此沿著這些從"r"發出的左指標，我們最終會找到一個指回"k"的線索。這種特性是對稱的：當"q"是"p"的左子節點時，我們可以沿著"q"的右子節點找到一個指回"p"的線索。傳統的二叉樹一般都是以鏈式儲存的結構來表示。這樣，二叉樹中的每個節點都可以用連結串列中的一個鏈節點來儲存，每個鏈節點就包含了若干個指標。但是，這種傳統的鏈式儲存結構只能表現出二叉樹中節點之間的父子關係，而且不能利用空餘的指標來直接得到某個節點的在特定的遍歷順序中的直接前驅和直接後繼。透過分析傳統的二叉樹鏈式儲存結構表示的二叉樹中，存在大量的空閒指標。若能利用這些空指標域來存放指向該節點的直接前驅或是直接後繼的指標，則可以進行某些更方便的運算。這些被重新利用起來的空指標就被稱為線索，加上了這些線索的二叉樹就是線索二叉樹。線索化.對二叉樹以某種遍歷順序進行掃描併為每個節點新增線索的過程稱為二叉樹的線索化，進行線索化的目的是為了加快查詢二叉樹中某節點的前驅和後繼的速度。那麼在有N個節點的二叉樹中需要利用N+1個空指標新增線索。這是因為在N個節點的二叉樹中，每個節點有2個指標，所以一共有2N個指標，除了根節點以外每一個節點都有一個指標從它的父節點指向它，所以一共使用了N-1個指標。所以剩下2N-(N-1)個空指標。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 線索二叉樹
metadata: https://zh.wikipedia.org/wiki?curid=3121241