中序線索二叉樹的解釋

將數列{1 ，3 ，6， 8 ，10 ，14}構建成一顆二叉樹

1)n個結點的二叉鏈表中含有n+1 [公式2n-(n-1)=n+1] 個空指針域。利用二叉鏈表中的空指針域，存放指向該結點在某種遍歷次序下的前驅和后繼結點的指針(這種附加的指針稱為"線索")

2)這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種

3)一個結點的前一個結點，稱為前驅結點

4)一個結點的后一個結點，稱為后繼結點

將上面的二叉樹，進行中序線索二叉樹。中序遍歷的數列為{8，3，10，1，14，6}

說明：當線索化二叉樹后，Node節點的屬性left 和right，有如下情況：

1)left 指向的是左子樹，也可能是指向的前驅節點.比如1節點left 指向的左子樹，而10節點的left指向的就是前驅節點

2)right 指向的是右子樹，也可能是指向后繼節點，比如1節點right指向的是右子樹，而10節點的right指向的是后繼節點

public void threadedNodes(HeroNode node) {
		
		//如果node==null, 不能線索化
		if(node == null) {
			return;
		}
		
		//(一)先線索化左子樹
		threadedNodes(node.getLeft());
 
		//(二)線索化當前結點
		
		//處理當前結點的前驅結點
		//以8結點來理解
		//8結點的.left = null , 8結點的.leftType = 1
		if(node.getLeft() == null) {
			//讓當前結點的左指針指向前驅結點 
			node.setLeft(pre); 
			//修改當前結點的左指針的類型,指向前驅結點
			node.setLeftType(1);
		}
		
		//處理后繼結點
		if (pre != null && pre.getRight() == null) {
			//讓前驅結點的右指針指向當前結點
			pre.setRight(node);
			//修改前驅結點的右指針類型
			pre.setRightType(1);
		}
		//!!! 每處理一個結點后，讓當前結點是下一個結點的前驅結點
		pre = node;
		
		//(三)在線索化右子樹
		threadedNodes(node.getRight());
		
	}

遍歷線索二叉樹

因為線索化后，各個結點指向有變化，因此原來的遍歷方式不能使用，這時需要使用新的方式遍歷線索化二叉樹，各個節點可以通過線型方式遍歷，因此無需使用遞歸方式，這樣也提高了遍歷的效率。遍歷的次序應當和中序遍歷保持一致。

    //遍歷線索化二叉樹的方法
	public void threadedList() {
 
		//定義一個變量，存儲當前遍歷的結點，從root開始
		HeroNode node = root;
 
		while(node != null) {
			//循環的找到leftType == 1的結點，第一個找到就是8結點
			//后面隨著遍歷而變化,因為當leftType==1時，說明該結點是按照線索化
			//處理后的有效結點
			while(node.getLeftType() == 0) {
				node = node.getLeft();
			}
			
			//打印當前這個結點
			System.out.println(node);
 
			//如果當前結點的右指針指向的是后繼結點,就一直輸出
			while(node.getRightType() == 1) {
				//獲取到當前結點的后繼結點
				node = node.getRight();
				System.out.println(node);
			}
 
			//替換這個遍歷的結點
			node = node.getRight();
			
		}
	}

完整代碼實現

package com.zx.ds.tree;
 
import sun.reflect.generics.tree.Tree;
 
class HeroNode {
    private int id;
    private String name;
    private HeroNode left;
    private HeroNode right;
    //說明
    //1. 如果leftType == 0 表示指向的是左子樹, 如果 1 則表示指向前驅結點
    //2. 如果rightType == 0 表示指向是右子樹, 如果 1表示指向后繼結點
    private int leftType;
    private int rightType;
 
    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 HeroNode getLeft() {
        return left;
    }
 
    public void setLeft(HeroNode left) {
        this.left = left;
    }
 
    public HeroNode getRight() {
        return right;
    }
 
    public void setRight(HeroNode right) {
        this.right = right;
    }
 
    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    public int getId() {
        return id;
    }
 
    public void setId(int id) {
        this.id = id;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    
}
 
class ThreadedBinaryTree {
    private HeroNode root;
    private HeroNode pre = null;
 
    public void setRoot(HeroNode root) {
        this.root = root;
    }
 
    public void threadNodes() {
        this.threadNodes(root);
    }
 
    public void threadNodes(HeroNode node) {
        if (node == null) {
            return;
        }
 
        threadNodes(node.getLeft());
 
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
 
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
 
        threadNodes(node.getRight());
 
    }
 
    public void threadedList() {
        HeroNode node = root;
        while (node != null) {
            while (node.getLeftType() != 1) {
                node = node.getLeft();
            }
 
            System.out.println(node);
 
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
 
            }
 
            node = node.getRight();
        }
    }
}
 
public class ThreadedBinaryTreeDemo {
 
    public static void main(String[] args) {
        HeroNode heroNode = new HeroNode(1, "宋江");
        HeroNode heroNode3 = new HeroNode(3, "吳用");
        HeroNode heroNode8 = new HeroNode(8, "盧俊義");
        HeroNode heroNode10 = new HeroNode(10, "公孫勝");
        HeroNode heroNode6 = new HeroNode(6, "關勝");
        HeroNode heroNode14 = new HeroNode(14, "林沖");
        heroNode.setLeft(heroNode3);
        heroNode.setRight(heroNode6);
        heroNode3.setLeft(heroNode8);
        heroNode3.setRight(heroNode10);
        heroNode6.setLeft(heroNode14);
 
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(heroNode);
        threadedBinaryTree.threadNodes();
        System.out.println("heroNode10.left=" + heroNode10.getLeft());
        System.out.println("heroNode10.right=" + heroNode10.getRight());
 
        System.out.println("中序線索樹遍歷：");
        threadedBinaryTree.threadedList();
 
    }
}

以上就是動力節點小編介紹的"中序線索二叉樹的解釋"，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為您務。