1.線索化二叉樹的介紹
將數(shù)列 {1, 3, 6, 8, 10, 14 } 構(gòu)建成一顆二叉樹.
問題分析:
1.當(dāng)我們對上面的二叉樹進(jìn)行中序遍歷時，數(shù)列為 {8, 3, 10, 1, 6, 14 }
2.但是 6, 8, 10, 14 這幾個節(jié)點(diǎn)的 左右指針，并沒有完全的利用上.
3.如果我們希望充分的利用 各個節(jié)點(diǎn)的左右指針， 讓各個節(jié)點(diǎn)可以指向自己的前后節(jié)點(diǎn),怎么辦?
4.解決方案-線索二叉樹
概念：當(dāng)用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，可以很方便的找到某個結(jié)點(diǎn)的左右孩子；但一般情況下，無法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)。所以使用線索化，利用二叉樹結(jié)構(gòu)鏈表的空指針域進(jìn)行線索化。
2.線索化二叉樹的基本特點(diǎn)
n 個結(jié)點(diǎn)的二叉鏈表中含有 n+1 【公式 2n-(n-1)=n+1】 個空指針域。利用二叉鏈表中的空指針域，存放指向該結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針（這種附加的指針稱為"線索"）
這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種
3.線索化二叉樹的應(yīng)用案例
中序線索化二叉樹并遍歷
應(yīng)用案例說明：將下面的二叉樹，進(jìn)行中序線索二叉樹。中序遍歷的數(shù)列為 {8, 3, 10, 1, 14, 6}
思路分析
中序遍歷的結(jié)果：{8, 3, 10, 1, 14, 6}
那么線索化之后的二叉樹的左右指針如上圖↑
說明: 當(dāng)線索化二叉樹后，Node 節(jié)點(diǎn)的 屬性 left 和 right ，有如下情況:
- left 指向的是左子樹，也可能是指向的前驅(qū)節(jié)點(diǎn). 比如 ① 節(jié)點(diǎn) left 指向的左子樹, 而 ⑩ 節(jié)點(diǎn)的 left 指向的 就是前驅(qū)節(jié)點(diǎn).
- right 指向的是右子樹，也可能是指向后繼節(jié)點(diǎn)，比如 ① 節(jié)點(diǎn) right 指向的是右子樹，而⑩ 節(jié)點(diǎn)的 right 指向的是后繼節(jié)點(diǎn).
因此要改變原來的二叉樹的結(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 {
//唯一編號
private int num;
//結(jié)點(diǎn)的值
private String name;
//左結(jié)點(diǎn)
private Node left;
//右節(jié)點(diǎn)
private Node right;
//這個屬性用來控制線索二叉樹的結(jié)點(diǎn)的指向，0代表指向左結(jié)點(diǎn)，1代表指向前趨結(jié)點(diǎn)
private int leftType;
//這個屬性用來控制線索二叉樹的結(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) {
//沒有左結(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)不為空，遞歸向左子樹調(diào)用
this.left.infixSelect();
}
//當(dāng)左結(jié)點(diǎn)為空，再輸出根結(jié)點(diǎn)。當(dāng)他本身就是最后一個左結(jié)點(diǎn)的時候，會直接輸出，且沒有右節(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è)二叉樹有三個結(jié)點(diǎn)，根結(jié)點(diǎn)，左結(jié)點(diǎn)，右節(jié)點(diǎn)。
* 后序遍歷,解釋，當(dāng)一個二叉樹的左結(jié)點(diǎn)不為空，那么他會進(jìn)入下一個遞歸調(diào)用自己的后序遍歷方法
* 此時，根結(jié)點(diǎn)就是左結(jié)點(diǎn)，這時判斷左結(jié)點(diǎn)，右節(jié)點(diǎn)均為空，就會輸出左結(jié)點(diǎn)
* 回退到根結(jié)點(diǎn)為this的時候，左結(jié)點(diǎn)已經(jīng)判斷完畢，接下來是右節(jié)點(diǎn)，右節(jié)點(diǎn)不為空，進(jìn)入后續(xù)遍歷遞歸，
* 此時的this就是右節(jié)點(diǎn)，進(jìn)入遞歸后，判斷，不存在左右結(jié)點(diǎn)，輸出this，也就是整個二叉樹的右節(jié)點(diǎn)
* 回退到this為根結(jié)點(diǎn)時，右節(jié)點(diǎn)也已經(jīng)輸出，走到最后一步，輸出自己也就是this。
* 整個后序遍歷就結(jié)束，那么該二叉樹的遍歷結(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)的編號來查詢結(jié)點(diǎn), 前序遍歷查詢，根，左，右
*/
public Node preSearchByNum(int num) {
//首先判斷傳進(jìn)來的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)
//定義一個結(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)為空，且沒有找到我們想要的結(jié)點(diǎn)的情況下。那就判斷右子結(jié)點(diǎn)
if (this.right != null) {
resultNode = this.right.preSearchByNum(num);
}
//最后，如果找到了，那么resultNode一定會被賦值，如果沒找到，就會返回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)的編號刪除結(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) {
//如果相等，那就說明該結(jié)點(diǎn)就是我們要刪除的結(jié)點(diǎn),將其左結(jié)點(diǎn)置空即可
this.left = null;
return;
}
//如果左結(jié)點(diǎn)沒有執(zhí)行，說明左結(jié)點(diǎn)沒有我們想要的結(jié)果，也就是要刪除的結(jié)點(diǎn)不在左結(jié)點(diǎn)
//那么就對右節(jié)點(diǎn)進(jìn)行判斷
if (this.right != null && this.right.num == num) {
this.right = null;
return;
}
//如果左右結(jié)點(diǎn)均沒有找到目標(biāo)結(jié)點(diǎn)
//那么就對左子樹進(jìn)行遞歸刪除操作
if (this.left != null) {
this.left.delNodeByNum(num);
}
//同理，如果左子樹沒有目標(biāo)結(jié)點(diǎn)，向右子樹進(jìn)行遞歸刪除操作
if (this.right != null) {
this.right.delNodeByNum(num);
}
}
}可以看到我們多出來了這么兩個屬性：
//這個屬性用來控制線索二叉樹的結(jié)點(diǎn)的指向，0代表指向左結(jié)點(diǎn)，1代表指向前趨結(jié)點(diǎn)
private int leftType;
//這個屬性用來控制線索二叉樹的結(jié)點(diǎn)的指向，0代表指向右結(jié)點(diǎn)，1代表指向后繼結(jié)點(diǎn)
private int rightType;
中序線索化二叉樹
/**中序線索化二叉樹*/
/**
* @param node 該結(jié)點(diǎn)為根結(jié)點(diǎn)，從根節(jié)點(diǎn)開始線索化二叉樹，中序
*/
public void infixThreadNodes(Node node) {
/**首先判斷二叉樹的根節(jié)點(diǎn)上會否為空，如果根結(jié)點(diǎn)為空，不可以線索化，因?yàn)闆]有二叉樹*/
if (node == null) {
return;
}
/**接著對左子樹進(jìn)行線索化*/
infixThreadNodes(node.getLeft());
/**對當(dāng)前結(jié)點(diǎn)進(jìn)行線索化*/
/**首先判斷當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)是否為空*/
if (node.getLeft() == null) {
//如果左子結(jié)點(diǎn)為空，說明就找到了我們需要線索化的結(jié)點(diǎn)
//就可以將pre也就是一直在當(dāng)前結(jié)點(diǎn)的前趨結(jié)點(diǎn)設(shè)置給當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)，
//如果這是第一個結(jié)點(diǎn)，那么pre為空，正好第一個結(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)不能為空，如果他為空，說明這是第一個結(jié)點(diǎn)還沒走完*/
if (pre != null && pre.getRight() == null) {
//如果條件滿足，說明前趨結(jié)點(diǎn)現(xiàn)在已經(jīng)走到了值，并且還沒有線索到后繼結(jié)點(diǎn)，
// 也就是當(dāng)前結(jié)點(diǎn)的上一個結(jié)點(diǎn)（這個上一個結(jié)點(diǎn)就是當(dāng)前的前趨結(jié)點(diǎn)）還沒有后繼，
//那么上一個結(jié)點(diǎn)的后繼結(jié)點(diǎn)就是當(dāng)前結(jié)點(diǎn)，因此賦值前趨結(jié)點(diǎn)（也就是上一個結(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)橄乱粋€結(jié)點(diǎn)一走，當(dāng)前結(jié)點(diǎn)就是前趨結(jié)點(diǎn)了。直到走到全部線索化結(jié)束
//這步十分重要，這一步不寫，整個線索化就連接不上
pre = node;
/**對右子樹進(jìn)行線索化*/
infixThreadNodes(node.getRight());
}
? 中序線索化二叉樹思路
- 因?yàn)橹行虮闅v的二叉樹順序是左根右，因此，首先對左子樹進(jìn)行線索化，遞歸線索化即可；
- 當(dāng)遞歸到左子樹的最左結(jié)點(diǎn)的時候，他的左結(jié)點(diǎn)肯定為空，那么就對他的左結(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)，也就是上一個結(jié)點(diǎn)未設(shè)置的右節(jié)點(diǎn)，類型同樣要設(shè)置為后繼
- 最后就是對pre這個結(jié)點(diǎn)賦值，為當(dāng)前結(jié)點(diǎn)，因?yàn)橄乱淮芜f歸，當(dāng)前結(jié)點(diǎn)就成了上一個結(jié)點(diǎn)，也就是這里的pre
- 最后就是對二叉樹的右子結(jié)點(diǎn)進(jìn)行線索化。
中序線索化二叉樹的遍歷
- 遍歷中序線索化二叉樹首先應(yīng)該明確的是他的遍歷順序要和遍歷原來的中序二叉樹遍歷的結(jié)果是一樣的，才是遍歷成功
- 那么第一步應(yīng)該就是判斷根結(jié)點(diǎn)不為空，也就是循環(huán)結(jié)束條件
- 接著就循環(huán)查找當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)類型為0的也就是沒有被線索化的結(jié)點(diǎn)，只要他為0，那么結(jié)點(diǎn)就一直往左子結(jié)點(diǎn)賦值。直到找到第一個被線索化的結(jié)點(diǎn)，輸出他，他就是我們第一個線索化并且也是中序遍歷的第一個左子結(jié)點(diǎn)。
- 輸出之后，判斷他的右子結(jié)點(diǎn)是否被線索化，如果被線索化，那么當(dāng)前結(jié)點(diǎn)node就被賦值為它自己的右子結(jié)點(diǎn)，并且輸出，如果他之后的結(jié)點(diǎn)的右子結(jié)點(diǎn)的類型又為1，那么繼續(xù)往后走并賦值，說明他有后繼
- 直到右子結(jié)點(diǎn)的類型為0，退出循環(huán)之后，也應(yīng)該向右再賦值，繼續(xù)向后遍歷
代碼演示
/**遍歷中序線索化二叉樹*/
public void infixThreadNodesSelect() {
/**第一個結(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的時候，也就是說該結(jié)點(diǎn)是被線索化的結(jié)點(diǎn),
* 因?yàn)槭侵行虮闅v，所以應(yīng)該遍歷到最左邊的最左子結(jié)點(diǎn)，那么就是第一個
* 左子結(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)他為0，說明沒有線索化，那么沒有后繼結(jié)點(diǎn)，但是他有右子結(jié)點(diǎn)，
* 因此要在循環(huán)結(jié)束以后向后移動。*/
while (node.getRightType() == 1) {
node = node.getRight();
System.out.println(node);
}
/**當(dāng)右子結(jié)點(diǎn)循環(huán)退出，說明這里到了類型為0也就是后繼結(jié)點(diǎn)*/
node = node.getRight();
}
4.前序線索化二叉樹、遍歷
線索化二叉樹
/**
* 前序線索化二叉樹
*/
public void preThreadNodes(Node node) {
/**首先判斷當(dāng)前節(jié)點(diǎn)是否為空*/
if (node == null) {
return;
}
/**如果是前序遍歷，那么先對當(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)不為空，說明他有值，就是已經(jīng)存在了上一個結(jié)點(diǎn)的值，他的右子結(jié)點(diǎn)沒有值的話，就可以
* 給他賦予后繼結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，這里賦予的也就是上一個結(jié)點(diǎn)*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
/**這里是關(guān)鍵的一步*/
pre = node;
/**對左子結(jié)點(diǎn)進(jìn)行線索化,注意，這里需要排除已經(jīng)被線索化掉的結(jié)點(diǎn),因?yàn)檫@里要考慮一個情況，
* 比如這里已將到了最下面一個左子結(jié)點(diǎn)，由于是前序遍歷，遍歷到左子結(jié)點(diǎn)，他的前趨結(jié)點(diǎn)在上面就設(shè)置了
* 如果這里不判斷左子結(jié)點(diǎn)的類型，那么就會進(jìn)入遞歸，但是這個遞歸如果進(jìn)去了，就是錯誤的遞歸，因?yàn)樗麄鬟^去的結(jié)點(diǎn)
* 是我們剛剛給他賦值的前趨結(jié)點(diǎn)，也就是根結(jié)點(diǎn)。會發(fā)生錯誤。因此得判斷類型*/
if (node.getLeftType() != 1) {
preThreadNodes(node.getLeft());
}
/**對右子結(jié)點(diǎn)進(jìn)行遞歸線索化*/
if (node.getRightType() != 1) {
preThreadNodes(node.getRight());
}
}
遍歷線索化二叉樹
/**
* 前序遍歷線索二叉樹*/
public void preThreadNodeSelect() {
Node node = root;
while(node !=null) {
while(node.getLeftType() == 0) {
/**前序遍歷為根左右，先輸出根結(jié)點(diǎn),因?yàn)樗看芜M(jìn)來循環(huán)肯定是先到根結(jié)點(diǎn)，所以一進(jìn)該循環(huán)
* 就要輸出根結(jié)點(diǎn)，當(dāng)他的lefttype=1循環(huán)結(jié)束，說明遇到了被線索化的地方了。*/
System.out.println(node);
/**再最左子結(jié)點(diǎn)進(jìn)行遍歷*/
node = node.getLeft();
}
/**上面的循環(huán)結(jié)束之后就應(yīng)該輸出當(dāng)前結(jié)點(diǎn)，也就是那個序列化的結(jié)點(diǎn)
* 之后結(jié)點(diǎn)向右移動繼續(xù)遍歷*/
System.out.println(node);
node = node.getRight();
}
??????? }
圖解
5.后序線索化二叉樹
后續(xù)線索化二叉樹
/**
* 后序線索化二叉樹的方法
*/
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;
}
后續(xù)線索化思路類似，只不過將順序改為了左右根。
以上就是Java數(shù)據(jù)結(jié)構(gòu)之線索化二叉樹的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java線索化二叉樹的資料請關(guān)注html5模板網(wǎng)其它相關(guān)文章！
【網(wǎng)站聲明】本站部分內(nèi)容來源于互聯(lián)網(wǎng),旨在幫助大家更快的解決問題，如果有圖片或者內(nèi)容侵犯了您的權(quán)益，請聯(lián)系我們刪除處理，感謝您的支持！