樹 - 線索二叉樹 （一）

　　線索二叉樹概念

　　定義

　　n個結點的二叉鏈表中含有n+個空指針域利用二叉鏈表中的空指針域存放指向結點在某種遍歷次序下的前趨和後繼結點的指

　　針(這種附加的指針稱為 線索 )

　　這種加上了線索的二叉鏈表稱為 線索鏈表 相應的二叉樹稱為 線索二叉樹 (Threaded BinaryTree)根據線索性質的不同

　　線索二叉樹可分為前序線索二叉樹中序線索二叉樹和後序線索二叉樹三種

　　注意

　　線索鏈表解決了二叉鏈表找左右孩子困難的問題出現了無法直接找到該結點在某種遍歷序列中的前趨和後繼結點的問題

　　線索鏈表的結點結構

　　線索鏈表中的結點結構為

　　

　　其中:

　　ltag和rtag是增加的兩個標志域用來區分結點的左右指針域是指向其左右孩子的指針還是指向其前趨或後繼的線索

　　

　　線索二叉樹的表示

　　【例】下面(a)圖所示的中序線索二叉樹其線索鏈表如下面(b)圖所示

　　

　　注意

　　圖中的實線表示指針虛線表示線索

　　結點C的左線索為空表示C是中序序列的開始結點無前趨;

　　結點E的右線索為空表示E是中序序列的終端結點無後繼

　　線索二叉樹中一個結點是葉結點的充要條件為左右標志均是

From:http://tw.wingwit.com/Article/program/sjjg/201311/23881.html