將數(shù)列{1 ，3 ，6， 8 ，10 ，14}構(gòu)建成一顆二叉樹

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

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

3)一個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，稱為前驅(qū)結(jié)點(diǎn)

4)一個(gè)結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)，稱為后繼結(jié)點(diǎn)

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

說(shuō)明：當(dāng)線索化二叉樹后，Node節(jié)點(diǎn)的屬性left 和right，有如下情況：

1)left 指向的是左子樹，也可能是指向的前驅(qū)節(jié)點(diǎn).比如1節(jié)點(diǎn)left 指向的左子樹，而10節(jié)點(diǎn)的left指向的就是前驅(qū)節(jié)點(diǎn)

2)right 指向的是右子樹，也可能是指向后繼節(jié)點(diǎn)，比如1節(jié)點(diǎn)right指向的是右子樹，而10節(jié)點(diǎn)的right指向的是后繼節(jié)點(diǎn)

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

遍歷線索二叉樹

因?yàn)榫€索化后，各個(gè)結(jié)點(diǎn)指向有變化，因此原來(lái)的遍歷方式不能使用，這時(shí)需要使用新的方式遍歷線索化二叉樹，各個(gè)節(jié)點(diǎn)可以通過(guò)線型方式遍歷，因此無(wú)需使用遞歸方式，這樣也提高了遍歷的效率。遍歷的次序應(yīng)當(dāng)和中序遍歷保持一致。

    //遍歷線索化二叉樹的方法
	public void threadedList() {
 
		//定義一個(gè)變量，存儲(chǔ)當(dāng)前遍歷的結(jié)點(diǎn)，從root開(kāi)始
		HeroNode node = root;
 
		while(node != null) {
			//循環(huán)的找到leftType == 1的結(jié)點(diǎn)，第一個(gè)找到就是8結(jié)點(diǎn)
			//后面隨著遍歷而變化,因?yàn)楫?dāng)leftType==1時(shí)，說(shuō)明該結(jié)點(diǎn)是按照線索化
			//處理后的有效結(jié)點(diǎn)
			while(node.getLeftType() == 0) {
				node = node.getLeft();
			}
			
			//打印當(dāng)前這個(gè)結(jié)點(diǎn)
			System.out.println(node);
 
			//如果當(dāng)前結(jié)點(diǎn)的右指針指向的是后繼結(jié)點(diǎn),就一直輸出
			while(node.getRightType() == 1) {
				//獲取到當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)
				node = node.getRight();
				System.out.println(node);
			}
 
			//替換這個(gè)遍歷的結(jié)點(diǎn)
			node = node.getRight();
			
		}
	}

完整代碼實(shí)現(xiàn)

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;
    //說(shuō)明
    //1. 如果leftType == 0 表示指向的是左子樹, 如果 1 則表示指向前驅(qū)結(jié)點(diǎn)
    //2. 如果rightType == 0 表示指向是右子樹, 如果 1表示指向后繼結(jié)點(diǎn)
    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, "關(guān)勝");
        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();
 
    }
}

以上就是動(dòng)力節(jié)點(diǎn)小編介紹的"中序線索二叉樹的解釋"，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為您務(wù)。