中序线索二叉树的解释

将数列{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();
 
    }
}

以上就是极悦小编介绍的"中序线索二叉树的解释"，希望对大家有帮助，如有疑问，请在线咨询，有专业老师随时为您务。