先看一道题将{1,3,6,8,10,14}的序列构建成一棵二叉树。n+1=7，如下图问题分析：当我们对上面的二叉树进行中序遍历时，序列为{8,3,10,1,14,6}但是左右指针节点6、8、10和14中的一部分未完全使用。如果我们想充分利用每个节点的左右指针，让每个节点都指向自己的前后节点呢？-1)=n+1]空指针字段。利用二叉链表中的空指针字段，按照一定的遍历顺序存储节点的前驱点和后继点的指针（这个额外的指针称为线索）。这种线程二叉链表称为线程链表，对应的二叉树称为线程二叉树（ThreadedBinaryTree）。根据线索的不同性质，线索二叉树可以分为三种类型：前序线索二叉树、中序线索二叉树和后序线索二叉树。一个节点的前一个节点称为前驱节点。节点之后的节点称为后继节点。中序线程二叉树图中序遍历{8,3,10,1,14,6}的结果表明：对二叉树进行线程化后，Node节点的左右属性有如下条件：指向的值byleft是左子树，也可能是指向的前驱节点，比如①节点left指向的左子树，⑩节点的左子树就是前驱节点。right指向的右子树也可能指向后继节点。例如①noderight指向右子树，⑩node'sright指向后继节点。代码示例packagecom.xie.tree.threadedbinarytree；publicclassThreadedBinaryTreeDemo{publicstaticvoidmain(String[]args){//测试有序线程二叉树HeroNoderoot=newHeroNode(1,"tom");HeroNodenode2=newHeroNode(3,"jack");HeroNodenode3=newHeroNode(6,"smith");HeroNodenode4=newHeroNode(8,"mary");HeroNodenode5=newHeroNode(10,"king");HeroNodenode6=newHeroNode(14,"dim");root.setLeft(node2);root.setRight(node3);node2.setLeft(node4);node2.setRight(node5);node3.setLeft(node6);ThreadedBinaryTreethreadedBinaryTree=newThreadedBinaryTree();threadedBinaryTree.setRoot(root);threadedBinaryTree.threadedNodes();//测试：用节点10测试HeroNodeleft=node5.getLeft()；System.out.println("节点10的前驱节点为："+left);HeroNoderight=node5.getRight();System.out.println("10号节点的后继节点为："+right);System.out.println("使用threaded方法遍历线程二叉树");threadedBinaryTree.threadedBinaryTreeList();/***10号节点的前驱节点为：HeroNode{no=3,name=jack}*节点10的后继节点为：HeroNode{no=1,name=tom}*以线程方式遍历线程二叉树*HeroNode{no=8,name=mary}*HeroNode{no=3,name=jack}*HeroNode{no=10,name=king}*HeroNode{no=1,name=tom}*HeroNode{no=14,name=dim}*HeroNode{no=6,name=smith}*/}}//二叉树类ThreadedBinaryTree{实现线程函数的privateHeroNoderoot;//为了实现线程化，需要创建指向当前节点的前驱节点的指针//递归线程化时，pre始终保留前一个节点privateHeroNodepre;publicvoidsetRoot(HeroNoderoot){this.root=root;}/***一种遍历线程二叉树的方法*/publicvoidthreadedBinaryTreeList(){//定义一个变量存放当前遍历的节点，从root开始HeroNodenode=root;while(node!=null){//循环寻找leftType==1的节点，第一个foundis8Node//随着后面的遍历而变化，因为当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();}}/***重载threadedNodes方法*/publicvoidthreadedNodes(){threadedNodes(root);}/***写一个线程化二叉树的方法**@paramnode目前需要线程化节点*/publicvoidthreadedNodes(HeroNodenode){if(node==null){return;}//先线程左子树threadedNodes(node.getLeft());//线程当前节点【难点】//处理当前节点的前驱节点//用8个节点理解，8个节点.left=nullif(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());}}//创建一个HeroNode节点classHeroNode{staticintpreCount=0;staticintinfoxCount=0;staticintpostCount=0;privateintno;privateStringname;privateHeroNodeleft;privateHeroNoderight;//0表示指向左子树，1表示指向左子树tothePrecursornodeprivateintleftType;//0表示指向右子树，1表示指向后继节点privateintrightType;publicHeroNode(intno,Stringname){this.no=no;this.name=name;}publicintgetNo(){returnno;}publicvoidsetNo(intno){this.no=no;}publicStringgetName(){returnname;}publicvoidsetName(Stringname){this.name=name;}publicHeroNodegetLeft(){returnleft;}publicvoidsetLeft(HeroNodeleft){this.left=left;}publicHeroNodegetRight(){returnright;}publicvoidsetRight(HeroNoderight){this.right=right;}publicintgetLeftType(){returnleftType;}publicvoidsetLeftType(intleftType){this.leftType=leftType;}publicintgetRightType(){returnrightType;}publicvoidsetRightType(intrightType){this.rightType=rightType;}@OverridepublicStringtoString(){return"HeroNode{"+"no="+no+",name="+name+'}';}//前序遍历publicvoidpreOrder(){System.out.println(this);//递归前序遍历左子树if(this.left!=null){this.left.preOrder();}//递归到右子树前序遍历if(this.right!=null){this.right.preOrder();}}//中序遍历publicvoidinfixOrder(){//递归左子树中序遍历if(this.left!=null){this.left.infixOrder();}System.out.println(this);//递归右子树中序遍历if(this.right!=null){this.right.infixOrder();}}//后序遍历publicvoidpostOrder(){//递归后序遍历到左子树if(this.left!=null){this.left.postOrder();}//递归后序遍历到右子树subtreeif(this.right!=null){this.right.postOrder();}System.out.println(this);}//递归删除节点//1.如果删除的节点是叶节点，则删除节点//2。如果删除的节点是非叶节点，则删除树。publicvoiddelNo(intno){/***1.因为我们的二叉树是单向的，我们判断当前节点的子节点是否是需要删除的节点，但是无法判断当前节点是否是需要删除的节点。*2.如果当前节点的左子节点不为空，且左子节点为要删除的节点，则设置this.left=null；并返回（结束递归）。*3.如果当前节点的右子节点不为空，且右子节点为要删除的节点，则设置this.right=null；并返回（结束递归）。*4.如果在第2步和第3步中没有删除该节点，则需要递归删除左子树。*5.如果第4步没有删除该节点，则递归删除到右子树。*/if(this.left!=null&&this.left.no==no){this.left=null;return;}if(this.right!=null&&this.right.no==no){this.right=null;return;}if(this.left!=null){this.left.delNo(no);}if(this.right!=null){this.right.delNo(no);}}//前序遍历查找publicHeroNodepreOrderSearch(intno){HeroNoderes=null;preCount++;//这个必须放在this之前。no==实际比较前不判断//找到则返回if(this.no==no){returnthis;}//不是找到，递归对左子树进行前序搜索if(this.left!=null){res=this.left.preOrderSearch(no);}//如果res!=null,直接返回if(res!=null){returnres;}//如果左子树没有搜索到，则按前序搜索右子树if(this.right!=null){res=this.right.preOrderSearch(no);}//找到则返回){res=this.left.infixOrderSearch(no);}if(res!=null){returnres;}infoxCount++;//必须放在this之前.no==在实际比较之前没有判断if(this.no==no){returnthis;}if(this.right!=null){res=this.right.infixOrderSearch(no);}if(res!=null){returnres;}returnres;}//后序遍历查找publicHeroNodepostOrderSearch(intno){HeroNoderes=null;if(this.left!=null){res=this.left.postOrderSearch(no);}if(res!=null){returnres;}if(this.right!=null){res=this.right.postOrderSearch(no);}if(res!=null){returnres;}postCount++;//这个必须放在this.no之前==实际比较前不判断if(this.no==no){returnthis;}returnres;}}【小编推荐】和妹子聊Java16的新特性，好甜！IT项目太多，太难管理？不！因为你还没有学会这七招。学习Python五年，这些网站让我认识了最近。快来一起体验吧。Java都到了16了，你怎么还在用8？是不是越来越糟了？太奇妙了！Windows10的这些黑科技功能你都用过吗？
