如何實作Java資料結構中的線索化二元樹？
- WBOY轉載
- 2023-05-09 08:05:43710瀏覽
1.線索化二元樹的介紹
將數列{1, 3, 6, 8, 10, 14 } 建構成一顆二元樹.
#問題分析:
1.當我們對上面的二元樹進行中序遍歷時，數列為{8, 3, 10, 1, 6, 14 }
2.但是6, 8, 10, 14 這幾個節點的左右指針，並沒有完全的利用上.
#3.如果我們希望充分的利用各個節點的左右指針， 讓各個節點可以指向自己的前後節點,怎麼辦?
4.解決方案-線索二叉樹
概念：當用二叉鍊錶作為二叉樹的存儲結構時，可以很方便的找到某個結點的左右孩子；但一般情況下，無法直接找到該結點在某種遍歷序列中的前驅和後繼結點。所以使用線索化，利用二元樹結構鍊錶的空指標域進行線索化。
2.線索化二元樹的基本特性
n 個結點的二元鍊錶中含有 n 1 【公式 2n-(n-1)=n 1】 個空指標域。利用二元鍊錶中的空指標域，存放指向該結點在某種遍歷次序下的前驅和後繼結點的指標（這種附加的指標稱為"線索"）
這種加上了線索的二元鍊錶稱為線索鍊錶，對應的二元樹稱為線索二元樹(Threaded BinaryTree)。依線索性質的不同，線索二元樹可分為前序線索二元樹、中序線索二元樹與後序線索二元樹三種
3.線索化二元樹的應用案例
中序線索化二元樹並遍歷
應用案例說明：將下面的二元樹，進行中序線索二元樹。中序遍歷的數列為{8, 3, 10, 1, 14, 6}
思路分析
中序遍歷的結果：{8 , 3, 10, 1, 14, 6}
那麼線索化之後的二元樹的左右指針如上圖↑
#說明: 當線索化二元樹後，Node 節點的屬性left 和right ，有如下情況:
#left 指向的是左子樹，也可能是指向的前驅節點. 例如① 節點left 指向的左子樹, 而⑩ 節點的left 指向的就是前驅節點.
right 指向的是右子樹，也可能是指向後繼節點，例如① 節點right 指向的是右子樹，而⑩ 節點的right 指向的是後繼節點.
因此要改變原來的二元樹的結點結構
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结点
*/
public class Node {
//唯一编号
private int num;
//结点的值
private String name;
//左结点
private Node left;
//右节点
private Node right;
//这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
private int leftType;
//这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
private int rightType;
//构造方法
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() {
//首先输出根结点
System.out.println(this);
//其次判断是否有左结点
if (this.left != null) {
//没有左结点，就递归调用本方法输出该结点。
this.left.preSelect();
}
if (this.right != null) {
this.right.preSelect();
}
}
/**
* 中序遍历
*/
public void infixSelect() {
//首先判断左结点
if (this.left != null) {
//如果左结点不为空，递归向左子树调用
this.left.infixSelect();
}
//当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点
System.out.println(this);
if (this.right != null) {
//右节点同样如此，递归调用。直到没有结点为止。
this.right.infixSelect();
}
}
/**
* 设二叉树有三个结点，根结点，左结点，右节点。
* 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法
* 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点
* 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归，
* 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点
* 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。
* 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根
*/
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 根据结点的编号来查询结点, 前序遍历查询，根，左，右
*/
public Node preSearchByNum(int num) {
//首先判断传进来的num与该结点的num是否相等
//如果相等，那该结点就是我们要找的结点。
if (this.num == num) {
return this;
}
//如果不相等，该结点就不是我们要找的结点
//那么我们就遍历该结点的左子节点，和右子结点
//定义一个结点用于接收最后的返回结果
Node resultNode = null;
//如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值
if (this.left != null) {
resultNode = this.left.preSearchByNum(num);
}
//如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可，
if (resultNode != null) {
return resultNode;
}
//如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点
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 中序遍历查找，左，根，右进行查询即可。
*/
public Node infixSearchByNum(int num) {
//首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。
Node resultNode = null;
if (this.left != null) {
resultNode = this.left.infixSearchByNum(num);
}
//如果左子结点已经找到了我们想要的结点，直接返回当前结点即可
if (resultNode != null) {
return resultNode;
}
//判断根结点
if (this.num == num) {
return this;
}
//判断右子结点，
if (this.right != null) {
resultNode = this.right.infixSearchByNum(num);
}
//最后返回我们的结果即可。
return resultNode;
}
/**
* @param num
* @Date 2022/4/21 19:15
* @Param
* @Return Node
* @MetodName afterSearchNum
* @Author wang
* @Description 后续遍历结点进行查找结点。左，右，根
*/
public Node afterSearchNum(int num) {
Node resultNode = null;
//首先遍历左结点
if (this.left != null) {
resultNode = this.left.afterSearchNum(num);
}
//判断左结点是否找到哦啊
if (resultNode != null) {
return resultNode;
}
//判断右节点是否为空
if (this.right != null) {
resultNode = this.right.afterSearchNum(num);
}
//判断右节点是否找到
if (resultNode != null) {
return resultNode;
}
//判断根结点是否为我们找的结点
if (this.num == num) {
return this;
}
//最后返回
return resultNode;
}
/**
* @param num
* @Date 2022/4/25 19:30
* @Param
* @Return void
* @MetodName delNodeByNum
* @Author wang
* @Description 根据结点的编号删除结点
*/
public void delNodeByNum(int num) {
//首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等
if (this.left != null && this.left.num == num) {
//如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可
this.left = null;
return;
}
//如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点
//那么就对右节点进行判断
if (this.right != null && this.right.num == num) {
this.right = null;
return;
}
//如果左右结点均没有找到目标结点
//那么就对左子树进行递归删除操作
if (this.left != null) {
this.left.delNodeByNum(num);
}
//同理，如果左子树没有目标结点，向右子树进行递归删除操作
if (this.right != null) {
this.right.delNodeByNum(num);
}
}
}可以看到我們多出來了這麼兩個屬性：
//这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
private int leftType;
//这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
private int rightType;中序線索化二元樹
/**中序线索化二叉树*/
/**
* @param node 该结点为根结点，从根节点开始线索化二叉树，中序
*/
public void infixThreadNodes(Node node) {
/**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/
if (node == null) {
return;
}
/**接着对左子树进行线索化*/
infixThreadNodes(node.getLeft());
/**对当前结点进行线索化*/
/**首先判断当前结点的左子结点是否为空*/
if (node.getLeft() == null) {
//如果左子结点为空，说明就找到了我们需要线索化的结点
//就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点，
//如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空
node.setLeft(pre);
//并且将它的左子结点的类型设置为前趋结点。1代表前趋结点
node.setLeftType(1);
}
/**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/
if (pre != null && pre.getRight() == null) {
//如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点，
// 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继，
//那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。
//这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化
pre.setRight(node);
pre.setRightType(1);
}
//当前两步走完之后，就可以将pre结点赋值为当前结点，
// 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束
//这步十分重要，这一步不写，整个线索化就连接不上
pre = node;
/**对右子树进行线索化*/
infixThreadNodes(node.getRight());
}中序線索化二元樹思路
因為中序遍歷的二元樹順序是左根右，因此，首先對左子樹進行線索化，遞歸線索化即可；
當遞歸到左子樹的最左結點的時候，他的左結點肯定為空，那麼就對他的左結點賦值為pre（pre結點是在線索化的最後一步賦值為當前結點，這樣遞歸才能進行下去）,注意左結點的類型一定要改為1，代表他是前趨結點。前趨結點就線索掉了。
後繼結點的處理則是判斷前趨結點，當前趨結點不為空，且前趨結點的右節點為空，那麼設定前趨結點的右節點為目前結點，也就是上一個結點未設定的右節點，型別同樣要設定為後繼
最後就是對pre這個結點賦值，為目前結點，因為下一次遞歸，當前結點就成了上一個結點，也就是這裡的pre
最後就是將二元樹的右子結點線索化。
中序線索化二元樹的遍歷
#遍歷中序線索化二元樹首先應該明確的是他的遍歷順序要和遍歷原來的中序二元樹遍歷的結果是一樣的，才是遍歷成功
那麼第一步應該就是判斷根結點不為空，也就是循環結束條件
接著就循環找出目前結點的左子結點類型為0的也就是沒有被線索化的結點，只要他為0，那麼結點就一直往左子結點賦值。直到找到第一個被線索化的結點，輸出他，他就是我們第一個線索化並且也是中序遍歷的第一個左子結點。
輸出之後，判斷他的右子結點是否被線索化，如果被線索化，那麼當前結點node就被賦值為它自己的右子結點，並且輸出，如果他之後的結點的右子結點的類型又為1，那麼繼續往後走並賦值，說明他有後繼
直到右子結點的類型為0，退出循環之後，也應該向右再賦值，繼續向後遍歷
#程式碼示範
/**遍历中序线索化二叉树*/
public void infixThreadNodesSelect() {
/**第一个结点为根结点*/
Node node = root;
while(node != null) {
/**当结点不为空，就一直遍历*/
/**当该结点的左子结点的类型为1的时候，也就是说该结点是被线索化的结点,
* 因为是中序遍历，所以应该遍历到最左边的最左子结点，那么就是第一个
* 左子结点类型为1的结点。*/
while(node.getLeftType() == 0) {
node = node.getLeft();
}
/**当左子结点的类型为1,输出左子结点*/
System.out.println(node);
/**当右子结点类型为1，当前结点输出完毕后
* 中序遍历就应该输出右子结点，那么就是当前结点的右子结点类型只要为1，就往后移动
* 并且输出，当他为0，说明没有线索化，那么没有后继结点，但是他有右子结点，
* 因此要在循环结束以后向后移动。*/
while (node.getRightType() == 1) {
node = node.getRight();
System.out.println(node);
}
/**当右子结点循环退出，说明这里到了类型为0也就是后继结点*/
node = node.getRight();
}4.前序線索化二元樹、遍歷
線索化二元樹
/**
* 前序线索化二叉树
*/
public void preThreadNodes(Node node) {
/**首先判断当前节点是否为空*/
if (node == null) {
return;
}
/**如果是前序遍历，那么先对当前结点进行判断，当前结点的前趋结点的操作*/
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
/**处理后继结点,定义的前趋结点不为空，说明他有值，就是已经存在了上一个结点的值，他的右子结点没有值的话，就可以
* 给他赋予后继结点为当前结点，这里赋予的也就是上一个结点*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
/**这里是关键的一步*/
pre = node;
/**对左子结点进行线索化,注意，这里需要排除已经被线索化掉的结点,因为这里要考虑一个情况，
* 比如这里已将到了最下面一个左子结点，由于是前序遍历，遍历到左子结点，他的前趋结点在上面就设置了
* 如果这里不判断左子结点的类型，那么就会进入递归，但是这个递归如果进去了，就是错误的递归，因为他传过去的结点
* 是我们刚刚给他赋值的前趋结点，也就是根结点。会发生错误。因此得判断类型*/
if (node.getLeftType() != 1) {
preThreadNodes(node.getLeft());
}
/**对右子结点进行递归线索化*/
if (node.getRightType() != 1) {
preThreadNodes(node.getRight());
}
}遍历线索化二叉树
/**
* 前序遍历线索二叉树*/
public void preThreadNodeSelect() {
Node node = root;
while(node !=null) {
while(node.getLeftType() == 0) {
/**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环
* 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/
System.out.println(node);
/**再最左子结点进行遍历*/
node = node.getLeft();
}
/**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点
* 之后结点向右移动继续遍历*/
System.out.println(node);
node = node.getRight();
}
}图解
5.后序线索化二叉树
后续线索化二叉树
/**
* 后序线索化二叉树的方法
*/
public void postThreadedBinaryTree(Node node) {
/**首先判断结店不能为空*/
if (node == null) {
return;
}
/**先后续线索化左子结点*/
postThreadedBinaryTree(node.getLeft());
/**在后续线索化右子结点*/
postThreadedBinaryTree(node.getRight());
/**处理当前结点的前趋结点*/
if (node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
/**处理后继结点*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
pre = node;
}以上是如何實作Java資料結構中的線索化二元樹？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
陳述：
本文轉載於：yisu.com。如有侵權，請聯絡admin@php.cn刪除