将数列{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指向的是后继节点
publicvoidthreadedNodes(HeroNode node){ //如果node==null, 不能线索化if(node == null) { return; } //(一)先线索化左子树 threadedNodes(node.getLeft()); //(二)线索化当前结点//处理当前结点的前驱结点//以8结点来理解//8结点的.left = null , 8结点的.leftType = 1if(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()); }遍历线索二叉树
因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。
//遍历线索化二叉树的方法publicvoidthreadedList() { //定义一个变量，存储当前遍历的结点，从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; classHeroNode { privateint id; private String name; private HeroNode left; private HeroNode right; //说明//1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点//2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点privateint leftType; privateint rightType; publicintgetLeftType() { return leftType; } publicvoidsetLeftType(int leftType) { this.leftType = leftType; } publicintgetRightType() { return rightType; } publicvoidsetRightType(int rightType) { this.rightType = rightType; } public HeroNode getLeft() { return left; } publicvoidsetLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } publicvoidsetRight(HeroNode right) { this.right = right; } publicHeroNode(int id, String name) { this.id = id; this.name = name; } publicintgetId() { return id; } publicvoidsetId(int id) { this.id = id; } public String getName() { return name; } publicvoidsetName(String name) { this.name = name; } @Override public String toString() { return"HeroNode{" + "id=" + id + ", name='" + name + '\'' + '}'; } } classThreadedBinaryTree { private HeroNode root; private HeroNode pre = null; publicvoidsetRoot(HeroNode root) { this.root = root; } publicvoidthreadNodes() { this.threadNodes(root); } publicvoidthreadNodes(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()); } publicvoidthreadedList() { 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(); } } } publicclassThreadedBinaryTreeDemo { publicstaticvoidmain(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(); } }以上就是动力节点小编介绍的"中序线索二叉树的解释"，希望对大家有帮助，如有疑问，请在线咨询，有专业老师随时为您务。