穿線二叉樹

二叉樹(binary tree)是一種重要的非線性數據結構。

1、穿線樹：也叫線索二叉樹
在二叉鍊表存儲形式的二叉樹中，把節點中空指針利用成為週遊線索。原來為空的左指針指向結點在某種週遊序列下的前驅，原來為空的右指針指向結點在同一種週遊序列下的後繼。這樣的二叉樹稱為穿線樹。
.. 可以有中序穿線樹，前序穿線樹，後序穿線樹。每種穿線樹可以只穿一半。穿線樹的目的是利用空指針的存儲空間，建立週遊線索。為了區分線索和指針，需在每個結點中增加兩個標誌位，分別標識左右指針域是實際指針還是線索。
2、中序週遊中序穿線樹：先從穿線樹的根出發，一直沿左指針，找到“最左”(它一定是中序的第一個
結點)；然後反覆地找結點的中序後繼。一個結點的右指針如果是線索，則右指針就是下一個要週遊的結點，如果右指針不是線索，則它的中序後繼是其右子樹的“最左”結點。
3、穿線樹節點的插入：
往中序穿線樹里插入結點的算法，規定插入這樣進行：newpointer指向要插入的新結點，pointer指向穿線二叉樹里的一個結點。將新結點插進來作為pointer指向的結點的右子樹的根。pointer指向的結點的原來的右子樹現在作為新結點的右子樹(新結點的左子樹為空)。即在中序序列里，新結點剛好插到p所指向的結點的後面。pointer的新後繼結點是newpointer，newpointer的後繼是pointer->rightchild()。如果Pointer的右子樹不空，則右子樹的最左結點線索指向newpointer；若空，則pointer的右線索給newpointer繼承。