摘要
- 定義和資料結構
- 線索化
- 遍歷
一、定義和資料結構
1. 定義
??結點結構中含有線索的的二叉樹稱為線索二叉樹，
??若結點有左子樹，則其lchild域指示其左子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右子，否則令rchild域指示其后繼，
??為了避免混淆，需要增加兩個標志域LTag和RTag，標志域為0表示結點后接指標，標志位為1表示結點后接線索，
2. 資料結構
typedef struct BiThrNode
{
ElemType data;
struct BiThrNode *lchild, *rchild;
PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;
??其中，PointerTag的定義為
typedef enum PointerTag
{
Link,
Thread
} PointerTag;
??Link == 0 表示指標，Thread == 1表示線索，
二、線索化
??線索化的實質是將二叉鏈表中的空指標改為指向前驅或后繼的線索，而前驅或后繼的資訊只能在遍歷時得到，所以線索化的程序即為在遍歷程序中修改空指標的程序，所以為了記錄遍歷程序中訪問結點的先后關系，附設一個指標pre始終指向剛剛訪問過的結點，即若指標p指向當前訪問的結點，則pre指向它的剛訪問過的結點，
void InThreading(BiThrTree p, BiThrTree *pre)
{
if (p)
{
// 左子樹線索化.
InThreading(p->lchild, pre);
// 前驅線索.
// 若當前結點無左子，則修改標志域并使得 lchild 指向 p 的前驅.
if (!(p->lchild))
{
p->LTag = Thread;
p->lchild = (*pre);
}
// 后繼線索.
if (!((*pre)->rchild))
{
(*pre)->RTag = Thread;
// 將前驅結點的后繼結點設定為當前結點.
(*pre)->rchild = p;
}
// 更新 pre, 使其始終指向剛訪問過的結點.
(*pre) = p;
// 右子樹線索化.
InThreading(p->rchild ,pre);
}
return;
} // InThreading
??我這里在學習的時候遇到一個問題：剛訪問過的結點pre的后繼線索設定失敗，書中的偽代碼未說明pre是否為全域變數，而資料結構中也沒有存盤pre，所以我先將pre作為一個區域變數定義并值傳遞給了InThreading，乍一看沒什么問題，但是仔細debug之后發現，在呼叫這個遞回形式的演算法時，系統會維護一個函式呼叫堆疊，每進入一層新的遞回，系統就會保存當前呼叫的回傳地址，并壓入新的呼叫的回傳地址，在執行完子函式后，子函式的回傳地址會被彈出堆疊，此時，之前做的一切修改就都不見了，pre也不會得到更新，
??改進方法有兩個：
????1. 將pre設定為全域變數；
????2. 將值傳遞改為指標傳遞，
??本文采用了第二種方法，
三、遍歷
??線索化之后，可以很方便地得到結點在遍歷所得線性序列中的前驅和后繼，也可以很方便地得到線性序列，
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType e))
{
// p 指向根結點.
BiThrNode *p = T->lchild;
// 空樹或遍歷結束時.
while (p != T)
{
while (p->LTag != Thread)
{
p = p->lchild;
}
if (!Visit(p->data))
{
return ERROR;
}
// 訪問后繼結點.
// 找到最左葉結點, 就可以輕松地訪問其后繼結點.
while ((p->RTag == Thread) && (p->rchild != T))
{
p = p->rchild;
Visit(p->data);
}
p = p->rchild;
}
return OK;
} // InOrderTraverse_Thr
參考文獻
- 資料結構:C語言版/嚴蔚敏,吳偉民編著. ——北京：清華大學出版社，2007
- 線索二叉樹詳解 https://blog.csdn.net/s_999999/article/details/86157532
- 線索二叉樹原理及前序、中序線索化（Java版）https://blog.csdn.net/UncleMing5371/article/details/54176252
- 關于函式呼叫堆疊(call stack)的個人理解 https://blog.csdn.net/VarusK/article/details/83031643
代碼倉庫
- https://github.com/tianshihao/data-structure/tree/master/chapter_6
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63645.html
標籤：其他