溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“Java數(shù)據(jù)結(jié)構(gòu)之線索化二叉樹(shù)怎么實(shí)現(xiàn)”，在日常操作中，相信很多人在Java數(shù)據(jù)結(jié)構(gòu)之線索化二叉樹(shù)怎么實(shí)現(xiàn)問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Java數(shù)據(jù)結(jié)構(gòu)之線索化二叉樹(shù)怎么實(shí)現(xiàn)”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！
將數(shù)列 {1, 3, 6, 8, 10, 14 } 構(gòu)建成一顆二叉樹(shù).
問(wèn)題分析:
1.當(dāng)我們對(duì)上面的二叉樹(shù)進(jìn)行中序遍歷時(shí)，數(shù)列為 {8, 3, 10, 1, 6, 14 }
2.但是 6, 8, 10, 14 這幾個(gè)節(jié)點(diǎn)的 左右指針，并沒(méi)有完全的利用上.
3.如果我們希望充分的利用 各個(gè)節(jié)點(diǎn)的左右指針， 讓各個(gè)節(jié)點(diǎn)可以指向自己的前后節(jié)點(diǎn),怎么辦?
4.解決方案-線索二叉樹(shù)
概念：當(dāng)用二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，可以很方便的找到某個(gè)結(jié)點(diǎn)的左右孩子；但一般情況下，無(wú)法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)。所以使用線索化，利用二叉樹(shù)結(jié)構(gòu)鏈表的空指針域進(jìn)行線索化。
n 個(gè)結(jié)點(diǎn)的二叉鏈表中含有 n+1 【公式 2n-(n-1)=n+1】 個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向該結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針（這種附加的指針?lè)Q為"線索"）
這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)(Threaded BinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹(shù)可分為前序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種
中序線索化二叉樹(shù)并遍歷
應(yīng)用案例說(shuō)明：將下面的二叉樹(shù)，進(jìn)行中序線索二叉樹(shù)。中序遍歷的數(shù)列為 {8, 3, 10, 1, 14, 6}
思路分析
中序遍歷的結(jié)果：{8, 3, 10, 1, 14, 6}
那么線索化之后的二叉樹(shù)的左右指針如上圖↑
說(shuō)明: 當(dāng)線索化二叉樹(shù)后，Node 節(jié)點(diǎn)的 屬性 left 和 right ，有如下情況:
left 指向的是左子樹(shù)，也可能是指向的前驅(qū)節(jié)點(diǎn). 比如 ① 節(jié)點(diǎn) left 指向的左子樹(shù), 而 ⑩ 節(jié)點(diǎn)的 left 指向的 就是前驅(qū)節(jié)點(diǎn).
right 指向的是右子樹(shù)，也可能是指向后繼節(jié)點(diǎn)，比如 ① 節(jié)點(diǎn) right 指向的是右子樹(shù)，而⑩ 節(jié)點(diǎn)的 right 指向的是后繼節(jié)點(diǎn).
因此要改變?cè)瓉?lái)的二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)
package com.studySelf.tree.threadedBinaryTree;
/**
* @author wang
* @version 1.0
* @packageName com.studySelf.tree.tree01
* @className Node
* @date 2022/4/19 20:15
* @Description Node結(jié)點(diǎn)
*/
public class Node {
//唯一編號(hào)
private int num;
//結(jié)點(diǎn)的值
private String name;
//左結(jié)點(diǎn)
private Node left;
//右節(jié)點(diǎn)
private Node right;
//這個(gè)屬性用來(lái)控制線索二叉樹(shù)的結(jié)點(diǎn)的指向，0代表指向左結(jié)點(diǎn)，1代表指向前趨結(jié)點(diǎn)
private int leftType;
//這個(gè)屬性用來(lái)控制線索二叉樹(shù)的結(jié)點(diǎn)的指向，0代表指向右結(jié)點(diǎn)，1代表指向后繼結(jié)點(diǎn)
private int rightType;
//構(gòu)造方法
public Node(int num, String name) {
this.num = num;
this.name = name;
}
public int getLeftType() {
return leftType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public int getRightType() {
return rightType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return "Node{" +
"num=" + num +
", name='" + name +
'}';
}
/**
* 前序遍歷
*/
public void preSelect() {
//首先輸出根結(jié)點(diǎn)
System.out.println(this);
//其次判斷是否有左結(jié)點(diǎn)
if (this.left != null) {
//沒(méi)有左結(jié)點(diǎn)，就遞歸調(diào)用本方法輸出該結(jié)點(diǎn)。
this.left.preSelect();
}
if (this.right != null) {
this.right.preSelect();
}
}
/**
* 中序遍歷
*/
public void infixSelect() {
//首先判斷左結(jié)點(diǎn)
if (this.left != null) {
//如果左結(jié)點(diǎn)不為空，遞歸向左子樹(shù)調(diào)用
this.left.infixSelect();
}
//當(dāng)左結(jié)點(diǎn)為空，再輸出根結(jié)點(diǎn)。當(dāng)他本身就是最后一個(gè)左結(jié)點(diǎn)的時(shí)候，會(huì)直接輸出，且沒(méi)有右節(jié)點(diǎn)
System.out.println(this);
if (this.right != null) {
//右節(jié)點(diǎn)同樣如此，遞歸調(diào)用。直到?jīng)]有結(jié)點(diǎn)為止。
this.right.infixSelect();
}
}
/**
* 設(shè)二叉樹(shù)有三個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)，左結(jié)點(diǎn)，右節(jié)點(diǎn)。
* 后序遍歷,解釋，當(dāng)一個(gè)二叉樹(shù)的左結(jié)點(diǎn)不為空，那么他會(huì)進(jìn)入下一個(gè)遞歸調(diào)用自己的后序遍歷方法
* 此時(shí)，根結(jié)點(diǎn)就是左結(jié)點(diǎn)，這時(shí)判斷左結(jié)點(diǎn)，右節(jié)點(diǎn)均為空，就會(huì)輸出左結(jié)點(diǎn)
* 回退到根結(jié)點(diǎn)為this的時(shí)候，左結(jié)點(diǎn)已經(jīng)判斷完畢，接下來(lái)是右節(jié)點(diǎn)，右節(jié)點(diǎn)不為空，進(jìn)入后續(xù)遍歷遞歸，
* 此時(shí)的this就是右節(jié)點(diǎn)，進(jìn)入遞歸后，判斷，不存在左右結(jié)點(diǎn)，輸出this，也就是整個(gè)二叉樹(shù)的右節(jié)點(diǎn)
* 回退到this為根結(jié)點(diǎn)時(shí)，右節(jié)點(diǎn)也已經(jīng)輸出，走到最后一步，輸出自己也就是this。
* 整個(gè)后序遍歷就結(jié)束，那么該二叉樹(shù)的遍歷結(jié)果就是左，右，根
*/
public void afterSelect() {
if (this.left != null) {
this.left.afterSelect();
}
if (this.right != null) {
this.right.afterSelect();
}
System.out.println(this);
}
/**
* @param num
* @Date 2022/4/21 17:51
* @Param
* @Return Node
* @MetodName preSearchByNum
* @Author wang
* @Description 根據(jù)結(jié)點(diǎn)的編號(hào)來(lái)查詢結(jié)點(diǎn), 前序遍歷查詢，根，左，右
*/
public Node preSearchByNum(int num) {
//首先判斷傳進(jìn)來(lái)的num與該結(jié)點(diǎn)的num是否相等
//如果相等，那該結(jié)點(diǎn)就是我們要找的結(jié)點(diǎn)。
if (this.num == num) {
return this;
}
//如果不相等，該結(jié)點(diǎn)就不是我們要找的結(jié)點(diǎn)
//那么我們就遍歷該結(jié)點(diǎn)的左子節(jié)點(diǎn)，和右子結(jié)點(diǎn)
//定義一個(gè)結(jié)點(diǎn)用于接收最后的返回結(jié)果
Node resultNode = null;
//如果該結(jié)點(diǎn)的左子結(jié)點(diǎn)不為空，就遞歸調(diào)用前序遍歷，繼續(xù)查找，如果找到了，那么resultNode就是我們想要的值
if (this.left != null) {
resultNode = this.left.preSearchByNum(num);
}
//如果遍歷完左子結(jié)點(diǎn)，已經(jīng)找到了我們想要的結(jié)果，直接返回結(jié)果即可，
if (resultNode != null) {
return resultNode;
}
//如果左子結(jié)點(diǎn)為空，且沒(méi)有找到我們想要的結(jié)點(diǎn)的情況下。那就判斷右子結(jié)點(diǎn)
if (this.right != null) {
resultNode = this.right.preSearchByNum(num);
}
//最后，如果找到了，那么resultNode一定會(huì)被賦值，如果沒(méi)找到，就會(huì)返回null
return resultNode;
}
/**
* @param num
* @Date 2022/4/21 17:58
* @Param
* @Return Node
* @MetodName infixSearchByNum
* @Author wang
* @Description 中序遍歷查找，左，根，右進(jìn)行查詢即可。
*/
public Node infixSearchByNum(int num) {
//首先判斷左子結(jié)點(diǎn),如果存在左子結(jié)點(diǎn)，遞歸繼續(xù)查詢遍歷即可即可。
Node resultNode = null;
if (this.left != null) {
resultNode = this.left.infixSearchByNum(num);
}
//如果左子結(jié)點(diǎn)已經(jīng)找到了我們想要的結(jié)點(diǎn)，直接返回當(dāng)前結(jié)點(diǎn)即可
if (resultNode != null) {
return resultNode;
}
//判斷根結(jié)點(diǎn)
if (this.num == num) {
return this;
}
//判斷右子結(jié)點(diǎn)，
if (this.right != null) {
resultNode = this.right.infixSearchByNum(num);
}
//最后返回我們的結(jié)果即可。
return resultNode;
}
/**
* @param num
* @Date 2022/4/21 19:15
* @Param
* @Return Node
* @MetodName afterSearchNum
* @Author wang
* @Description 后續(xù)遍歷結(jié)點(diǎn)進(jìn)行查找結(jié)點(diǎn)。左，右，根
*/
public Node afterSearchNum(int num) {
Node resultNode = null;
//首先遍歷左結(jié)點(diǎn)
if (this.left != null) {
resultNode = this.left.afterSearchNum(num);
}
//判斷左結(jié)點(diǎn)是否找到哦啊
if (resultNode != null) {
return resultNode;
}
//判斷右節(jié)點(diǎn)是否為空
if (this.right != null) {
resultNode = this.right.afterSearchNum(num);
}
//判斷右節(jié)點(diǎn)是否找到
if (resultNode != null) {
return resultNode;
}
//判斷根結(jié)點(diǎn)是否為我們找的結(jié)點(diǎn)
if (this.num == num) {
return this;
}
//最后返回
return resultNode;
}
/**
* @param num
* @Date 2022/4/25 19:30
* @Param
* @Return void
* @MetodName delNodeByNum
* @Author wang
* @Description 根據(jù)結(jié)點(diǎn)的編號(hào)刪除結(jié)點(diǎn)
*/
public void delNodeByNum(int num) {
//首先，判斷當(dāng)前結(jié)點(diǎn)的左結(jié)點(diǎn)是否為空，并且左結(jié)點(diǎn)的num是否與num相等
if (this.left != null && this.left.num == num) {
//如果相等，那就說(shuō)明該結(jié)點(diǎn)就是我們要?jiǎng)h除的結(jié)點(diǎn),將其左結(jié)點(diǎn)置空即可
this.left = null;
return;
}
//如果左結(jié)點(diǎn)沒(méi)有執(zhí)行，說(shuō)明左結(jié)點(diǎn)沒(méi)有我們想要的結(jié)果，也就是要?jiǎng)h除的結(jié)點(diǎn)不在左結(jié)點(diǎn)
//那么就對(duì)右節(jié)點(diǎn)進(jìn)行判斷
if (this.right != null && this.right.num == num) {
this.right = null;
return;
}
//如果左右結(jié)點(diǎn)均沒(méi)有找到目標(biāo)結(jié)點(diǎn)
//那么就對(duì)左子樹(shù)進(jìn)行遞歸刪除操作
if (this.left != null) {
this.left.delNodeByNum(num);
}
//同理，如果左子樹(shù)沒(méi)有目標(biāo)結(jié)點(diǎn)，向右子樹(shù)進(jìn)行遞歸刪除操作
if (this.right != null) {
this.right.delNodeByNum(num);
}
}
}可以看到我們多出來(lái)了這么兩個(gè)屬性：
//這個(gè)屬性用來(lái)控制線索二叉樹(shù)的結(jié)點(diǎn)的指向，0代表指向左結(jié)點(diǎn)，1代表指向前趨結(jié)點(diǎn) private int leftType; //這個(gè)屬性用來(lái)控制線索二叉樹(shù)的結(jié)點(diǎn)的指向，0代表指向右結(jié)點(diǎn)，1代表指向后繼結(jié)點(diǎn) private int rightType;
中序線索化二叉樹(shù)
/**中序線索化二叉樹(shù)*/
/**
* @param node 該結(jié)點(diǎn)為根結(jié)點(diǎn)，從根節(jié)點(diǎn)開(kāi)始線索化二叉樹(shù)，中序
*/
public void infixThreadNodes(Node node) {
/**首先判斷二叉樹(shù)的根節(jié)點(diǎn)上會(huì)否為空，如果根結(jié)點(diǎn)為空，不可以線索化，因?yàn)闆](méi)有二叉樹(shù)*/
if (node == null) {
return;
}
/**接著對(duì)左子樹(shù)進(jìn)行線索化*/
infixThreadNodes(node.getLeft());
/**對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行線索化*/
/**首先判斷當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)是否為空*/
if (node.getLeft() == null) {
//如果左子結(jié)點(diǎn)為空，說(shuō)明就找到了我們需要線索化的結(jié)點(diǎn)
//就可以將pre也就是一直在當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)設(shè)置給當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)，
//如果這是第一個(gè)結(jié)點(diǎn)，那么pre為空，正好第一個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)也為空
node.setLeft(pre);
//并且將它的左子結(jié)點(diǎn)的類型設(shè)置為前趨結(jié)點(diǎn)。1代表前趨結(jié)點(diǎn)
node.setLeftType(1);
}
/**接著判斷前趨結(jié)點(diǎn)的右子結(jié)點(diǎn)是否為空，前提是前趨結(jié)點(diǎn)不能為空，如果他為空，說(shuō)明這是第一個(gè)結(jié)點(diǎn)還沒(méi)走完*/
if (pre != null && pre.getRight() == null) {
//如果條件滿足，說(shuō)明前趨結(jié)點(diǎn)現(xiàn)在已經(jīng)走到了值，并且還沒(méi)有線索到后繼結(jié)點(diǎn)，
// 也就是當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)（這個(gè)上一個(gè)結(jié)點(diǎn)就是當(dāng)前的前趨結(jié)點(diǎn)）還沒(méi)有后繼，
//那么上一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)就是當(dāng)前結(jié)點(diǎn)，因此賦值前趨結(jié)點(diǎn)（也就是上一個(gè)結(jié)點(diǎn)）的后繼結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)。
//這樣這條線索就連接上了,并且只有滿足葉子結(jié)點(diǎn)的結(jié)點(diǎn)才可以進(jìn)行線索化
pre.setRight(node);
pre.setRightType(1);
}
//當(dāng)前兩步走完之后，就可以將pre結(jié)點(diǎn)賦值為當(dāng)前結(jié)點(diǎn)，
// 因?yàn)橄乱粋€(gè)結(jié)點(diǎn)一走，當(dāng)前結(jié)點(diǎn)就是前趨結(jié)點(diǎn)了。直到走到全部線索化結(jié)束
//這步十分重要，這一步不寫(xiě)，整個(gè)線索化就連接不上
pre = node;
/**對(duì)右子樹(shù)進(jìn)行線索化*/
infixThreadNodes(node.getRight());
}中序線索化二叉樹(shù)思路
因?yàn)橹行虮闅v的二叉樹(shù)順序是左根右，因此，首先對(duì)左子樹(shù)進(jìn)行線索化，遞歸線索化即可；
當(dāng)遞歸到左子樹(shù)的最左結(jié)點(diǎn)的時(shí)候，他的左結(jié)點(diǎn)肯定為空，那么就對(duì)他的左結(jié)點(diǎn)賦值為pre（pre結(jié)點(diǎn)是在線索化的最后一步賦值為當(dāng)前結(jié)點(diǎn)，這樣遞歸才能進(jìn)行下去）,注意左結(jié)點(diǎn)的類型一定要改為1，代表他是前趨結(jié)點(diǎn)。前趨結(jié)點(diǎn)就線索掉了。
后繼結(jié)點(diǎn)的處理則是判斷前趨結(jié)點(diǎn)，當(dāng)前趨結(jié)點(diǎn)不為空，并且前趨結(jié)點(diǎn)的右節(jié)點(diǎn)為空，那么設(shè)置前趨結(jié)點(diǎn)的右節(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，也就是上一個(gè)結(jié)點(diǎn)未設(shè)置的右節(jié)點(diǎn)，類型同樣要設(shè)置為后繼
最后就是對(duì)pre這個(gè)結(jié)點(diǎn)賦值，為當(dāng)前結(jié)點(diǎn)，因?yàn)橄乱淮芜f歸，當(dāng)前結(jié)點(diǎn)就成了上一個(gè)結(jié)點(diǎn)，也就是這里的pre
最后就是對(duì)二叉樹(shù)的右子結(jié)點(diǎn)進(jìn)行線索化。
中序線索化二叉樹(shù)的遍歷
遍歷中序線索化二叉樹(shù)首先應(yīng)該明確的是他的遍歷順序要和遍歷原來(lái)的中序二叉樹(shù)遍歷的結(jié)果是一樣的，才是遍歷成功
那么第一步應(yīng)該就是判斷根結(jié)點(diǎn)不為空，也就是循環(huán)結(jié)束條件
接著就循環(huán)查找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)類型為0的也就是沒(méi)有被線索化的結(jié)點(diǎn)，只要他為0，那么結(jié)點(diǎn)就一直往左子結(jié)點(diǎn)賦值。直到找到第一個(gè)被線索化的結(jié)點(diǎn)，輸出他，他就是我們第一個(gè)線索化并且也是中序遍歷的第一個(gè)左子結(jié)點(diǎn)。
輸出之后，判斷他的右子結(jié)點(diǎn)是否被線索化，如果被線索化，那么當(dāng)前結(jié)點(diǎn)node就被賦值為它自己的右子結(jié)點(diǎn)，并且輸出，如果他之后的結(jié)點(diǎn)的右子結(jié)點(diǎn)的類型又為1，那么繼續(xù)往后走并賦值，說(shuō)明他有后繼
直到右子結(jié)點(diǎn)的類型為0，退出循環(huán)之后，也應(yīng)該向右再賦值，繼續(xù)向后遍歷
代碼演示
/**遍歷中序線索化二叉樹(shù)*/
public void infixThreadNodesSelect() {
/**第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)*/
Node node = root;
while(node != null) {
/**當(dāng)結(jié)點(diǎn)不為空，就一直遍歷*/
/**當(dāng)該結(jié)點(diǎn)的左子結(jié)點(diǎn)的類型為1的時(shí)候，也就是說(shuō)該結(jié)點(diǎn)是被線索化的結(jié)點(diǎn),
* 因?yàn)槭侵行虮闅v，所以應(yīng)該遍歷到最左邊的最左子結(jié)點(diǎn)，那么就是第一個(gè)
* 左子結(jié)點(diǎn)類型為1的結(jié)點(diǎn)。*/
while(node.getLeftType() == 0) {
node = node.getLeft();
}
/**當(dāng)左子結(jié)點(diǎn)的類型為1,輸出左子結(jié)點(diǎn)*/
System.out.println(node);
/**當(dāng)右子結(jié)點(diǎn)類型為1，當(dāng)前結(jié)點(diǎn)輸出完畢后
* 中序遍歷就應(yīng)該輸出右子結(jié)點(diǎn)，那么就是當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)類型只要為1，就往后移動(dòng)
* 并且輸出，當(dāng)他為0，說(shuō)明沒(méi)有線索化，那么沒(méi)有后繼結(jié)點(diǎn)，但是他有右子結(jié)點(diǎn)，
* 因此要在循環(huán)結(jié)束以后向后移動(dòng)。*/
while (node.getRightType() == 1) {
node = node.getRight();
System.out.println(node);
}
/**當(dāng)右子結(jié)點(diǎn)循環(huán)退出，說(shuō)明這里到了類型為0也就是后繼結(jié)點(diǎn)*/
node = node.getRight();
}線索化二叉樹(shù)
/**
* 前序線索化二叉樹(shù)
*/
public void preThreadNodes(Node node) {
/**首先判斷當(dāng)前節(jié)點(diǎn)是否為空*/
if (node == null) {
return;
}
/**如果是前序遍歷，那么先對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行判斷，當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)的操作*/
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
/**處理后繼結(jié)點(diǎn),定義的前趨結(jié)點(diǎn)不為空，說(shuō)明他有值，就是已經(jīng)存在了上一個(gè)結(jié)點(diǎn)的值，他的右子結(jié)點(diǎn)沒(méi)有值的話，就可以
* 給他賦予后繼結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，這里賦予的也就是上一個(gè)結(jié)點(diǎn)*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
/**這里是關(guān)鍵的一步*/
pre = node;
/**對(duì)左子結(jié)點(diǎn)進(jìn)行線索化,注意，這里需要排除已經(jīng)被線索化掉的結(jié)點(diǎn),因?yàn)檫@里要考慮一個(gè)情況，
* 比如這里已將到了最下面一個(gè)左子結(jié)點(diǎn)，由于是前序遍歷，遍歷到左子結(jié)點(diǎn)，他的前趨結(jié)點(diǎn)在上面就設(shè)置了
* 如果這里不判斷左子結(jié)點(diǎn)的類型，那么就會(huì)進(jìn)入遞歸，但是這個(gè)遞歸如果進(jìn)去了，就是錯(cuò)誤的遞歸，因?yàn)樗麄鬟^(guò)去的結(jié)點(diǎn)
* 是我們剛剛給他賦值的前趨結(jié)點(diǎn)，也就是根結(jié)點(diǎn)。會(huì)發(fā)生錯(cuò)誤。因此得判斷類型*/
if (node.getLeftType() != 1) {
preThreadNodes(node.getLeft());
}
/**對(duì)右子結(jié)點(diǎn)進(jìn)行遞歸線索化*/
if (node.getRightType() != 1) {
preThreadNodes(node.getRight());
}
}遍歷線索化二叉樹(shù)
/**
* 前序遍歷線索二叉樹(shù)*/
public void preThreadNodeSelect() {
Node node = root;
while(node !=null) {
while(node.getLeftType() == 0) {
/**前序遍歷為根左右，先輸出根結(jié)點(diǎn),因?yàn)樗看芜M(jìn)來(lái)循環(huán)肯定是先到根結(jié)點(diǎn)，所以一進(jìn)該循環(huán)
* 就要輸出根結(jié)點(diǎn)，當(dāng)他的lefttype=1循環(huán)結(jié)束，說(shuō)明遇到了被線索化的地方了。*/
System.out.println(node);
/**再最左子結(jié)點(diǎn)進(jìn)行遍歷*/
node = node.getLeft();
}
/**上面的循環(huán)結(jié)束之后就應(yīng)該輸出當(dāng)前結(jié)點(diǎn)，也就是那個(gè)序列化的結(jié)點(diǎn)
* 之后結(jié)點(diǎn)向右移動(dòng)繼續(xù)遍歷*/
System.out.println(node);
node = node.getRight();
}
}圖解
后續(xù)線索化二叉樹(shù)
/**
* 后序線索化二叉樹(shù)的方法
*/
public void postThreadedBinaryTree(Node node) {
/**首先判斷結(jié)店不能為空*/
if (node == null) {
return;
}
/**先后續(xù)線索化左子結(jié)點(diǎn)*/
postThreadedBinaryTree(node.getLeft());
/**在后續(xù)線索化右子結(jié)點(diǎn)*/
postThreadedBinaryTree(node.getRight());
/**處理當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)*/
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
/**處理后繼結(jié)點(diǎn)*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
pre = node;
}到此，關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)之線索化二叉樹(shù)怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼