本文目錄一覽：
線索二叉樹的構建
建立線索二叉樹，或者說對二叉樹線索化，實質上就是遍歷一棵二叉樹。在遍歷過程中，訪問結點的操作是檢查當前的左，右指針域是否為空，將它們改為指向前驅結點或後續結點的線索。為實現這一過程，設指針pre始終指向剛剛訪問的結點，即若指針p指向當前結點，則pre指向它的前驅，以便設線索。
另外，在對一顆二叉樹加線索時，必須首先申請一個頭結點，建立頭結點與二叉樹的根結點的指向關係，對二叉樹線索化後，還需建立最後一個結點與頭結點之間的線索。
下面是建立中序二叉樹的遞歸算法，其中pre為全局變量。 voidInThreading(BiThrTree*p);//預先聲明BiThrNodeType*pre;BiThrTree*InOrderThr(BiThrTree*T){/*中序遍歷二叉樹T，並將其中序線索化，pre為全局變量*/BiThrTree*head;//線索二叉樹的頭結點，指向根結點head=(BitThrNodeType*)malloc（sizeof（BitThrNodeType））;/*設申請頭結點成功*/head-ltag=0;head-rtag=1;/*建立頭結點*/head-rchild=head;/*右指針回指*/if(!T)head-lchild=head;/*若二叉樹為空，則左指針回指*/else{head-lchild=T;pre=head;InThreading(T);/*中序遍歷進行中序線索化*/pre-rchild=head;pre-rtag=1;/*最後一個結點線索化*/head-rchild=pre;}returnhead;}voidInThreading(BiThrTree*p){/*通過中序遍歷進行中序線索化*/if(p){InThreading(p-lchild);/*左子樹線索化，遞歸*/if(p-lchild==NULL)/*前驅線索*/{ p-ltag=1;p-lchild=pre;}elsep-ltag=0;if(p-rchild==NULL)p-rtag=1;/*後驅線索*/elsep-rtag=0;if(pre!=NULLpre-rtag==1)pre-rchild=p;pre=p;InThreading(p-rchild);/*右子樹線索化*/}}算法 （1）中序線索二叉樹：若結點的ltag=1，lchild指向其前驅；否則，該結點的前驅是以該結點為根的左子樹上按中序遍歷的最後一個結點。若rtag=1，rchild指向其後繼；否則，該結點的後繼是以該結點為根的右子樹上按中序遍歷的第一個結點。
求後繼的算法如下： bithptr*INORDERNEXT(bithptr*p){if(p-rtag==1)return(p-rchild);else{q=p-rchild;/*找右子樹最先訪問的結點*/while(q-ltag==0)q=q-lchild;return(q);}}求前驅的算法如下： bithptr*INORDERNEXT(bithptr*p){if(p-ltag==1)return(p-lchild);else{q=p-lchild;/*找左子樹最後訪問的結點*/while(q-rtag==0)q=q-rchild;return(q);}}(2) 後序線索二叉樹：
在後序線索二叉樹中查找結點*p的前驅：若結點*p無左子樹，則p-lchild指向其前驅；否則，若結點*p有左子樹，當其右子樹為空時，其左子樹的根（即p-lrchild）為其後序前驅。當其右子樹非空時，其右子樹的根（即p-rchild）為其後序前驅。
在後序線索二叉樹中查找結點*p的後繼：若結點*p為根，則無後繼；若結點*p為其雙親的右孩子，則其後繼為其雙親；若結點*p為其雙親的左孩子，且雙親無右子女，則其後繼為其雙親；若結點*p為其雙親的左孩子，且雙親有右子女，則結點*p的後繼是其雙親的右子樹中按後序遍歷的第一個結點。所以，求後序線索二叉樹中結點的後繼要知道其雙親的信息，要使用棧，所以說後序線索二叉樹是不完善的。
（3）先序線索二叉樹：
在先序線索二叉樹中查找結點的後繼較容易，而查找前驅要知道其雙親的信息，要使用棧，所以說先序線索二叉樹也是不完善的。
求幫忙改錯——數據結構 樹的遍歷 線索二叉樹
Status InorderTraverse(BiTree T,Status(*Visit)(TElemType)){
BiTree p;
p=T-lchild;
while(p!=T){
while(p-LTag==Link) 這一行出現了錯誤P是定義為BiTree,它沒有LTag
p=p-lchild;
if(!Visit(p-data))
return ERROR;//訪問其左子樹為空的結點
while(p-RTag==Threadp-rchild!=T){
p=p-rchild;
Visit(p-data);//訪問後繼結點
}
p=p-rchild;
}
return OK;
}
如何實現二叉樹的線索化
自己理解得方法：
先把二叉樹給標記化：既設置兩個標記Ltag，Rtag，如果左孩子指針為空，Ltag=1，如果右孩子指針為空，Rtag=1。
先序遍歷線索二叉樹：
首先進行先序遍歷，然後把得到的節點依次入隊
然後把隊列里除了根節點以外的節點依次根據標記，隊里首節點Ltag=0，如果Ltag=1，左指針指向隊里前一個元素，如果Rtag=1，右指針指向隊里後一個元素。
中序遍歷線索二叉樹：
首先進行中序遍歷，然後把得到的節點依次入隊
然後把隊列里除了根節點以外的節點依次根據標記，隊列里首節點Ltag=0，如果Ltag=1，左指針指向隊里前一個元素，如果Rtag=1，右指針指向隊里後一個元素。
後序遍歷線索二叉樹：
首先進行後序遍歷，然後把得到的節點依次入隊
然後把隊列里除了根節點以外的節點依次根據標記，隊列里首節點Ltag=0，如果Ltag=1，左指針指向隊里前一個元素，如果Rtag=1，
java 二叉樹前序遍歷
//類Node定義二叉樹結點的數據結構;
//一個結點應包含結點值，左子結點的引用和右子結點的引用
class Node{
public Node left; //左子結點
public Node right; //右子結點
public int value; //結點值
public Node(int val){
value = val;
}
}
public class Traversal
{
//read()方法將按照前序遍歷的方式遍歷輸出二叉樹的結點值
//此處採用遞歸算法會比較簡單，也容易理解，當然也可以用
//循環的方法遍歷，但會比較複雜，也比較難懂。二叉樹遍歷
//用遞歸算法最為簡單，因為每個結點的遍歷方式都是，根，
//左，右，遞歸的調用可以讓每個結點以這種方式遍歷
public static void read(Node node){
if(node != null){
System.out.println(node.value);//輸出當前結點的值
if(node.left != null)
read(node.left); //遞歸調用 先讀左結點
if(node.right != null)
read(node.right); //遞歸調用 後讀右結點
}
}
public static void main(String[] args){
//初始化5個結點，分別初始值為1，2，3，4，5
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
//構建二叉樹，以n1為根結點
n1.left = n2;
n1.right = n5;
n2.left = n3;
n2.right = n4;
read(n1);
}
}
注釋和代碼都是我自己寫的，如果樓主覺得有的注釋多餘可以自己刪除一些！代碼我都編譯通過，並且運行結果如你提的要求一樣！你只要把代碼複製編譯就可以了，注意要以文件名Traversal.java來保存，否則編譯不通過，因為main函數所在的類是public類型的！
怎麼線索二叉樹？
用二叉鏈表作為二叉樹的存儲結構時，因為每個結點中只有指向其左右孩子結點的指針域，所以從任一結點出發只能直接找到該結點的左右孩子結點，而無法直接找到該結點在某種遍歷序列中的前驅和後繼結點。為了保存遍歷後結點的前驅和後繼信息，可採用增加向前和向後的指針，但這種方法增加了存儲開銷，不可取。對於具有n個結點的二叉樹，採用二叉鏈表存儲結構時，每個結點有兩個指針域，總共有2n個指針域，其中有n＋1個空指針域。由此，利用這些空鏈域來存放遍歷後結點的前驅和後繼信息，這就是線索二叉樹構成的思想。由於遍歷方法不同，所獲得的線性序列中，結點的前驅和後繼也不同，因此線索二叉樹又分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹。
1.線索二叉樹的基本概念（1）線索：將二叉鏈表中的空指針域指向前驅結點和後繼結點的指針稱為線索。
（2）線索鏈表：把加上了線索的二叉鏈表稱為線索鏈表。
（2）線索化：使二叉鏈表中結點的空鏈域存放以某種次序遍歷得到的前驅或後繼信息的過程稱為線索化。
（4）線索二叉樹：加上線索的二叉樹稱為線索二叉樹。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/295946.html
微信掃一掃 
支付寶掃一掃 