PS：本文为转载文章，原文可读性会更好。作为案例，我先画一棵二叉树，如图1所示：如果我们对图1中的二叉树进行中序遍历，结果是：425136，当我们仔细观察二叉树时图1中的树，发现456个节点的左右指针没用，3个节点的左指针也没用；如果我们要使用每个节点的左右指针，让每个节点都可以指向自己的前后节点，那么我们就使用threading二叉树。线程二叉树的基本介绍；(1)前驱节点：就是以中序遍历的方式遍历二叉树，某节点的前一个节点，比如图1中的5个节点，看图1中序遍历的结果：425136，5个节点前面有2个节点，所以5个节点的前驱节点为2个节点；一个节点有前驱节点的前提是该节点的左子节点为空且该节点有前一个节点，比如5节点的左子节点为空时，中序遍历就出来了，节点5有前一个节点，节点4没有前一个节点，所以不存在前驱节点；通常前驱节点是节点的父节点或父节点节点的父节点，等等。(2)后继节点：就是按照中序遍历的方式遍历二叉树，某个节点的下一个节点，比如图1中的5个节点，看图中序遍历的结果1:425136，5个节点后面跟着1个节点，所以5个节点的后继节点为1个节点；一个结点有后继结点的前提是该结点的右子结点为空且该结点后面有一个结点，例如5结点的右孩子结点为空时则中序遍历出来，第5个节点有下一个节点，第6个节点的右子节点为空但是后面没有节点，所以第6个节点没有后继节点；通常后继节点是父节点或该节点的父节点的父节点，等等。(3)n个节点的二叉链表包含n+1(公式2n-(n-1)=n+1)个空指针字段；利用二进制链表中的空指针字段，将指向节点的指针按照某种遍历顺序存储在指向前驱节点和后继节点的指针中（这个额外的指针被称为“线程”）。(4)这个带有线索的二叉链表称为线索链表，对应的二叉树称为线索二叉树。.好吧，我们把指向前驱节点的指针和指向后继节点的指针添加到图1中的二叉树中，就得到了图2中的inorderclue二叉树，如下图；图片说明：黑色箭头表示指向前驱节点的指针，橙色箭头表示指向后继节点的指针。好了，现在我们用代码实现图2中序线索的二叉树，打印出4个节点的后继节点，5个节点的前驱节点和后继节点，3个节点的前驱节点，前驱节点的6个节点，看看图2是否指的是相同的。(1)写一个节点类Node:publicclassNode{privateintno;私有节点离开；privateNoderight;//如果为0表示左子树；如果为1，则表示前驱节点privateintleftType;//如果为0，则表示右子树；如果为1，则表示后继节点privateintrightType；publicintgetLeftType(){返回leftType;}publicvoidsetLeftType(intleftType){this.leftType=leftType;}publicintgetRightType(){returnrightType;}publicvoidsetRightType(intrightType){this.rightType=rightType;}publicNode(intno){super();this.no=no;}publicNodegetLeft(){returnleft;}publicvoidsetLeft(Nodeleft){this.left=left;}publicNodegetRight(){returnright;}publicvoidsetRight(Noderight){this.right=right;}publicintgetNo(){returnno;}}(2)编写一个类Test，在二叉树上执行顺序线程：publicclassTest{private节点根；staticNode[]nodes;//创建指向当前节点的前驱节点的指针privateNodepre;publicstaticvoidmain(String[]args){}//打印当前节点的前驱节点privatevoidprintPreNode(Nodenode){if(node==null){System.out.println("这个节点是空，所以没有前驱节点");}else{if(node.getLeft()!=null&&node.getLeftType()==1){节点左=node.getLeft();System.out.println(node.getNo()+"该节点的前驱节点为："+left.getNo()+"节点");}else{System.out.println("无前驱节点");}}}//打印当前节点的后继节点privatevoidprintPostNode(Nodenode){if(node==null){System.out.println("这个节点是空的，所以没有后继节点");}else{if(node.getRight()!=null&&node.getRightType()==1){Noderight=node.getRight();System.out.println(node.getNo()+"Node的后继节点是："+right.getNo()+"node");}else{System.out.println("无后继节点");}}}privatevoidthreadedNodes(){if(root!=null){threadedNodes(root);}else{System.out.println("根节点为空，无法进行二叉树的中序线程");}}//创建二叉树privatevoidcreateBinaryTree(){nodes=newNode[6];for(inti=0;i
