看了網上不少線索二叉樹的遍歷流程代碼：拿著嚴版教材一通copy就直接發到網上，關鍵的一些代碼全都不說明，導致我自己琢磨好久
現在就把我琢磨的東西發出來分享！
那我來講一下我學習的程序中看到這遇到的問題：
1.如何尋找當前節點的后繼
2.如何確保中序線索遍歷一直進行下去
下面我拿一個例子來進行講解
我就拿我這個圖來說，我先把他變成線索二叉樹形態：
在撰寫代碼的時候，首先就會思考第一個問題：如何尋找當前節點的下一個后繼節點！比如說我要尋找9的后繼，比如我要找7的后繼節點，再比如我要找1的后繼節點
首先解決第一個小問題：
尋找9的后繼節點很簡單：因為變成了線索樹，只需要按照紫色箭頭所指向的方向走下去即可：
反應到代碼可以這么寫：這個地方用到p->rtag就很簡單了，只要p這個節點存在直接后繼，我就讓p走下去
if(p->rtag==1)
q=p->right;
第二個小問題：
如何找到7的后繼：我們可以看到圖中寫到的中序遍歷順序是7到10，那么如何尋找呢？這里就需要總結出一個規律，當一個節點不能靠線索走下去的時候，那么他的后繼就是其右孩子的最左邊的子樹，反應到圖中就是7的孫子節點10，也就是9的左子樹，
這里如果我們再變一下，假設10還存在n個左子樹，那么7這個節點的后繼就是10的最左邊的那個孫子節點，反應到代碼是這樣的
q=p->right; while(q->ltag==0) q=q->left;
代碼的意思就是先將當前節點轉化為其右節點，然后再沿其右節點一直往左子樹的方向走
但是！注意我這里為什么沒有直接寫q=q->left;而是寫為while條件陳述句！原因就和第三個小問題有關：
我們在尋找1這個節點的后繼時發現，其右子樹為3，當沿著3的左子樹走下去的時候，發現3不存在左子樹；3
就是1的直接后繼，那么該怎么辦呢？
可不可以將代碼改成
while(q->left!=NULL) q=q->left;
答案是不行，
看上面我畫的線索圖，3有一條前驅指標指向1本身，如果按照上面的寫法將會形成一個死回圈：1指向3，3指向1,無法出來，
所以我們這個地方一定要將while條件判斷改成指向當前節點的“左孩子”，左孩子的判斷很簡單：當前節點的ltag=0的時候一定就有左孩子
你可能會問：
若q的左孩子是空怎么辦？當前不會為空，之前線索化二叉樹的時候已經將所有的空指標線索化了，tag==0就說明指標指向了孩子，tag==1就代表指標指向了前驅或者后繼結點，不存在指標為空的情況，
那么我們的求節點后繼的函式就可以這么寫
Node* next(Node *p) { Node *q=NULL; if(p->rtag==1) q=p->right; else { q=p->right; while(q->ltag==0) q=q->left; } return q; }
寫完了如何找到線索二叉樹的后繼，那么接下來就是如何遍歷線索二叉樹了：
我們值到中序二叉樹的起點都是最左邊的節點開始遍歷，那么如何定位到最左邊的節點呢？只需要用一個while回圈：從根節點開始，不斷遍歷其左孩子，一直到rtag==1時，就說明不存在左孩子了，進而找到了我們需要的最左邊的節點，
while(p->ltag==0) { p=p->left; } printf("%d\t",p->data);
這個地方printf出最左邊節點的data，原因是最左邊的孩子是中序遍歷的第一個節點，自然需要列印出來
然后就只需要把線索二叉樹當成一個鏈表，不斷的往左走就可以了
while(p->right!=NULL) { p=next(p); printf("%d\t",p->data); }
所以整個的代碼可以寫成這樣
void RunInthread(Node *node) { if(node==NULL) return; Node *p=node; if(p!=NULL) { while(p->ltag==0) { p=p->left; } printf("%d\t",p->data); while(p->right!=NULL) { p=next(p); printf("%d\t",p->data); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/17340.html
標籤：C
下一篇：8.C語言 變數宣告和定義