Java-线索化遍历二叉树

先看一个问题 将数列{1，3，6，8，10，14}构成一颗二叉树 问题分析： 1.当我们对上面的二叉树进行中序遍历时，数列为{8，3，10，1，6，14} 2.但是6，8，10，14这几个节点的左右指针没有完全利用上 3.如果我们希望充分利用各个节点的左右指针，让各个节点指向自己的前后节点怎么办 4.解决方法：线索化二叉树

线索二叉树基本介绍

1.n个节点的二叉链表中含有n+1个空指针域（公式：2n-(n-1)=n+1），利用二叉链表的空指针域，存放指向该节点再某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为线索） 2.这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded Binary Tree)，根据线索性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树和后续线索二叉树三种 3.一个节点的前一个节点叫做前驱节点，后一个节点叫做后继节点

线索二叉树应用案例

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为{8，3，10，1，14，6} 思路分析：中序遍历的结果：{8，3，10，1，14，6} 说明：当线索化二叉树后，Node节点的属性left和right有如下情况 1）left指向的是左子树，也可能指向的是前驱节点 2）right指向的是右子树，也可能是后继节点

代码实现

//先创建Node节点 class HeroNode{ private int no; private String name; private HeroNode left;//默认为null private HeroNode right;//默认为null private int leftType;//为0是左子树，1是前驱节点 private int rightType;///为0是右子树，1是后继结点 public HeroNode(int no, String name) { super(); this.no = no; this.name = name; } 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 int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } 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; } @Override public String toString() { return "Node [no=" + no + ", name=" + name + "]"; } //递归删除节点 public void delNode(int no) { 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.delNode(no); return; } if(this.right!=null) { this.right.delNode(no); return; } } //编写前序遍历的方法 public void preOrder(){ System.out.println(this);//先输出父节点 //递归左子树前序遍历 if(this.left!=null) { this.left.preOrder(); } //递归右子树遍历 if(this.right!=null) { this.right.preOrder(); } } //编写中序遍历的方法 public void infixOrder() { //递归左子树中序遍历 if(this.left!=null) { this.left.infixOrder(); } //输出父节点 System.out.println(this); //递归右子树中序遍历 if(this.right!=null) { this.right.infixOrder(); } } //编写后序遍历的方法 public void postOrder() { if(this.left!=null) { this.left.postOrder(); } if(this.right!=null) { this.right.postOrder(); } System.out.println(this); } //前序遍历查找 //如果找到返回Node，没找到返回null public HeroNode preOrderSearch(int no) { //比较当前节点是不是 if(this.no==no) { return this; } //判断当前节点的左子节点是否为空，如果不为空，则进行前序查找 //如果左递归前序查找，找到则返回 HeroNode resNode=null; if(this.left!=null) { resNode=this.left.preOrderSearch(no); } if(resNode!=null) {//说明找到 return resNode; } if(this.right!=null) { resNode=this.right.preOrderSearch(no); } return resNode; } //中序遍历查找 public HeroNode infixOrderSearch(int no) { //判断当前节点的左子节点是否为空，如果不为空，则递归中序查找 HeroNode resNode=null; if(this.left!=null) { resNode=this.left.infixOrderSearch(no); } if(resNode!=null) {//说明找到 return resNode; } //如果找到，则返回，如果没有找到，就和当前节点比较，如果是则返回当前节点 if(this.no==no) { return this; } //否则进行右递归的中序查找 if(this.right!=null) { resNode=this.right.infixOrderSearch(no); } return resNode; } //后序遍历查找 public HeroNode postOrderSearch(int no) { //判断当前节点是否为空，如果不为空，则递归后续查找 HeroNode resNode=null; if(this.left!=null) { resNode=this.left.postOrderSearch(no); } if(resNode!=null) { return resNode; } //如果左子树没有找到，则向右子树进行递归后序查找 if(this.right!=null) { resNode=this.right.postOrderSearch(no); } if(resNode!=null) { return resNode; } if(this.no==no) { return this; } return resNode; } } //定义二叉树 class ThreadedBinaryTree{ private HeroNode root; private HeroNode pre=null; public void setRoot(HeroNode root) { this.root = root; } public void threadedNode() { this.threadedNodes(root); } //编写对二叉树进行中序线索化的方法 public void threadedNodes(HeroNode node) { if(node==null) {//不能线索化 return; } //先线索化左子树 threadedNodes(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;//!!!每处理一个节点，让当前的节点是下一个节点的前驱节点 //线索化右子树 threadedNodes(node.getRight()); } //删除节点 public void delNode(int no) { if(root!=null) { //如果只有一个root节点，要立即判断root是否为要删除的节点 if(root.getNo()==no) { root=null; }else { root.delNode(no); } }else { System.out.println("空树， 不能删除"); } } //前序遍历 public void preOrder() { if(this.root!=null) { this.root.preOrder(); }else { System.out.println("二叉树为空，无法遍历"); } } //中序遍历 public void infixOrder() { if(this.root!=null) { this.root.infixOrder(); }else { System.out.println("二叉树为空，无法遍历"); } } //后序遍历 public void postOrder() { if(this.root!=null) { this.root.postOrder(); }else { System.out.println("二叉树为空，无法遍历"); } } //前序遍历查找 public HeroNode preOrderSearch(int no) { if(root!=null) { return root.preOrderSearch(no); }else { return null; } } //中序遍历查找 public HeroNode infixOrderSearch(int no) { if(root!=null) { return root.infixOrderSearch(no); }else { return null; } } //后序遍历查找 public HeroNode postOrderSearch(int no) { if(root!=null) { return root.postOrderSearch(no); }else { return null; } } } public static void main(String[] args) { HeroNode root=new HeroNode(1,"q"); HeroNode node2=new HeroNode(3,"w"); HeroNode node3=new HeroNode(6,"e"); HeroNode node4=new HeroNode(8,"r"); HeroNode node5=new HeroNode(10,"t"); HeroNode node6=new HeroNode(14,"y"); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadedBinaryTree threadedBinaryTree=new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNode(); HeroNode leftNode=node5.getLeft(); HeroNode rightNode=node5.getRight(); System.out.println("10的前驱节点是="+leftNode); System.out.println("10的后继结点是="+rightNode); }