線索二叉樹（中序遍歷版）

中序遍歷找到對應結點的前驅（土方法）

typedef struct BiNode{int data;BiNode *lchild, *rchild;
}BiNode, *BiTree;BiNode *p;  // 指向目標節點
BiNode *pre = NULL; // 指向當前訪問節點的前驅
BiNode *final = NULL; // 記錄最終結果void InOrder(BiTree T){if(T != NULL){InOrder(T -> lchild);visit(T);InOrder(T -> rchild);}
}// 找到目標節點的前驅節點
void visit(BiNode *q){  // q代表當前訪問節點if(p == q)final = pre;   // 如果當前訪問節點和目標節點一致了，那么pre就是我們需要找的前驅elsepre = q;       // 如果不一致，那么更新前驅節點
}

由上述代碼我們可以知道，如果使用土方法來尋找目標節點的前驅節點，那么每找一次，就需要對二叉樹進行一次遍歷，這樣對資源的浪費是不言而喻的，所以我們需要采用線索二叉樹來更加快速地尋找對應節點的前驅后繼，通過線索二叉樹，我們可以實現對二叉樹的隨機訪問。

問題1：為什么在visit函數中不需要對q進行迭代？

回答1：因為$q$的迭代是在$InOrder$中進行的，在每一次對$InOrder$的遞歸中，傳入$visit$的節點會不會·不斷變化，也就實現了對$q$的迭代。

線索二叉樹實際就是用空的 n + 1 個空指針指向直接前驅和直接后繼。如果一個節點的左孩子為空，則左孩子指針指向當前節點的前驅，改$ltag$為1；如果一個節點的右孩子為空，則用右孩子指針指向當前節點的后繼，改$rtag$為1。

lchild	ltag	data	rtag	rchild
指示左孩子	0		0	指示右孩子
指示直接前驅	1		1	指示直接后繼

// 線索二叉樹的存儲結構
typedef struct ThreadTree{int data;struct ThreadTree *lchild, *rchild;int ltag, rtag;
}ThreadNode, *ThreadTree;

構造線索二叉樹

通過中序遍歷對二叉樹線索化

void InThread(ThreadTree &p, ThreadTree &pre){ // p是當前訪問節點，pre為當前訪問節點的前驅if(p != NULL){InThread(p -> lchild);if(p -> lchild == NULL){  // 如果左孩子為空，則更新左孩子為前驅，ltag為1p -> lchild = pre;ltag = 1;}if(pre != NULL && pre -> rchild == NULL){ // 若前驅節點非空且其右子樹為空，則更新其右孩子為后繼，rtag為1pre -> rchild = p;pre -> rtag = 1;}pre = p;InThread(p -> rchild);}
}
void CreateInThread(ThreadTree T){Thread pre = NULL;if(T != NULL){InThread(T, pre);pre -> rchild = NULL; // 處理最后一個節點pre -> rtag = 1;}
}

問題2：為什么在創建二叉樹的時候需要判斷pre是否為空？

回答2：為了避免空指針引用，我們在創建線索二叉樹的時候，會把pre初始化為NULL（也就是其實并沒有這個節點），因為第一個節點沒有直接的前驅，而如果我們不對空指針進行判斷的話，那么pre的后繼就會是當前節點p，那么究竟誰才是第一個節點呢？運行起來就會導致程序崩潰。只有當pre不為空時，才有意義去判斷其右子樹是否為空，為它建立線索二叉樹才有意義。

構造雙向線索鏈表

但是這樣的線索二叉樹還是存在一些問題，比如沒有辦法從第一個節點直接遍歷到最后一個節點，為此我們可以建立一個頭節點，讓其lchild指向二叉樹的根節點，其rchild指向中序遍歷時訪問的最后一個節點。令中序遍歷的第一個節點的lchild指向頭節點，也就是第一個節點的前驅不再是NULL，而是head；令中序遍歷的最后一個節點的rchild指向頭節點，也就是最后一個節點的后繼也不再是NULL，而是head。這樣一來，我們就獲得了一個雙向線索鏈表。

void InThread(ThreadTree &p, ThreadTree &pre){ // p是當前訪問節點，pre為當前訪問節點的前驅if(p != NULL){InThread(p -> lchild);if(p -> lchild == NULL){  // 如果左孩子為空，則更新左孩子為前驅，ltag為1p -> lchild = pre;ltag = 1;}if(pre != NULL && pre -> rchild == NULL){ // 若前驅節點非空且其右子樹為空，則更新其右孩子為后繼，rtag為1pre -> rchild = p;pre -> rtag = 1;}pre = p;InThread(p -> rchild);}
}
void CreateInThread(ThreadTree T){ThreadNode *head = (ThreadTree*)malloc(sizeof(ThreadTree));if(head == NULL)return ;head -> ltag = 0; // 指向根節點head -> rtag = 1; // 指向最后一個節點head -> rchild = head; // 初始化右指針指向自己if(T == NULL){head -> lchild = head;}else {head -> lchild = T;ThreadTree pre = head;InTread(T, pre);// 處理最后一個節點pre -> rchild = head;pre -> rtag = 1;// 處理第一個節點ThreadNode *first = head -> lchild; // 初始化第一個節點為根節點，方便找到第一個節點// 尋找中序遍歷的第一個節點while(first -> ltag == 0) // 如果lchild是指向左孩子則迭代first = first -> lchild;first -> lchild = head;}
}

遍歷中序線索二叉樹

只要先找到序列中的第一個節點，然后依次找節點的后繼，直到其后繼為空便可完成遍歷；

1. 求第一個節點

ThreadNode *FirstNode(ThreadNode *p){while(p -> ltag == 0) p = p -> lchild;return p;
}

2. 求中序線索二叉樹中節點p在中序序列下的后繼

ThreadNode *NextNode(ThreadNode *p){if(p -> rtag == 0) return FirstNode(p -> rchild); // 右子樹中最左下節點else return p -> rchild;
}

3. 求中序線索二叉樹的最后一個節點

ThreadNode *LastNode(ThreadNode *p){while(p -> rtag == 0) p = p -> rchild;return p;
}

4. 求節點p前驅

ThreadNode *PreNode(ThreadNode *p){if(p -> ltag == 0) return LastNode(p -> lchild);return p;
}

利用上述1.2.兩個算法，我們可以寫出不含頭節點的中序線索二叉樹的中序遍歷算法：

void InOrder(ThreadNode *T){for(ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))visit(p); // 訪問節點，可自由設定
}