线索化二叉树及其遍历

//线索化二叉树 public class ThreadedBinaryTreeDemo { public static void main(String[] args) { //测试一把中序线索二叉树 HeroNode root new HeroNode(1,tom); HeroNode node2 new HeroNode(3,tom); HeroNode node3 new HeroNode(6,fee); HeroNode node4 new HeroNode(8,feff); HeroNode node5 new HeroNode(10,ewrweq); HeroNode node6 new HeroNode(14,werqr); //先手动创建 root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); //测试线索化 BinaryTree binaryTreenew BinaryTree(); binaryTree.setRoot(root); binaryTree.threadNodes(); //测试 10号节点 /* HeroNode left node5.getLeft(); HeroNode Right node5.getRight(); System.out.println(10号节点的前驱节点是 left); System.out.println(10号节点的后继节点是 Right);*/ System.out.println(使用线索化的方式遍历线索化二叉树); binaryTree.threaddeList(); } } //定义二叉树 class BinaryTree { private HeroNode root; //未来实现线索化需要创建要给指向当前节点的前驱节点的指针 //在递归进行线索化时 pre总是保留前一个节点 private HeroNode prenull; public void setRoot(HeroNode root) { this.root root; } //重载一把threadNodes、 public void threadNodes() { this.threadNodes(root); } //遍历线索化二叉树的方法 public void threaddeList() { //定义一个变量 存储当前遍历的节点从root开始 HeroNode noderoot; while (node!null) { //循环的找到lefttype1的节点第一个找到是8节点 //后面随着遍历而变化因为当lefttype1,说明该节点是按照线索化有效处理的节点 while (node.getLeftType()0) { nodenode.getLeft(); } System.out.println(node); //如果后继节点指向的后继节点就一直输出 while (node.getRightType()1) { nodenode.getRight(); System.out.println(node); } //替换这个遍历的节点 nodenode.getRight(); } } //编写二叉树中序线索化的方法 //node就是需要线索化的节点 public void threadNodes(HeroNode node) { if(nodenull) return; //(一) 先线索化左子树 threadNodes(node.getLeft()); //二线索化当前节点[有难度] //先处理当前节点的前驱节点 //以8节点来理解的化 //8节点的leftnull 8节点leftType1 if(node.getLeft()null) { //让当前节点的左指针指向前驱节点 node.setLeft(pre); node.setLeftType(1); } //处理后继节点 if(pre!nullpre.getRight()null) { pre.setRight(node); pre.setRightType(1); } // !!!每处理一个节点后 让当前节点是下一个节点的前驱节点 prenode; //三线索化右子树 threadNodes(node.getRight()); } 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 preSearch(int val) { if(this.root!null) return this.root.preOrdersearch(val); else System.out.println(无法遍历); return null; } public HeroNode infixSearch(int val) { if(this.root!null) return this.root.infixOrdersearch(val); else System.out.println(无法遍历); return null; } public HeroNode postSearch(int val) { if(this.root!null) return this.root.postOrdersearch(val); else System.out.println(无法遍历); return null; } } //创建节点 //先创建HeroNode class HeroNode { private int val; private String name; private HeroNode left; private HeroNode Right; //说明 //1.leftType0表示指向左子树 1表示指向前驱节点 //2.rightType0表示指向右子树 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(int val, String name) { this.val val; this.name name; } public int getVal() { return val; } public void setVal(int val) { this.val val; } 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) { Right right; } Override public String toString() { return HeroNode{ val val , name name \ }; } //编写前序遍历方法 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.val no) return this; HeroNode resNode null; if (this.left ! null) { resNode this.left.preOrdersearch(no); } if (resNode ! null) { System.out.println(找到了); //说明找到 return resNode; } if (this.Right ! null) { resNode this.Right.preOrdersearch(no); } return resNode; } //中序遍历查找 找到 返回该node 没找到 返回null public HeroNode infixOrdersearch(int no) { HeroNode resNode null; if (this.left ! null) { resNode this.left.infixOrdersearch(no); } if (resNode ! null) { //说明找到 return resNode; } System.out.println(进入中序查找); //比较当前节点是不是 if (this.val no) return this; if (this.Right ! null) { resNode this.Right.infixOrdersearch(no); } return resNode; } //后序遍历查找 找到 返回该node 没找到 返回null 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; } System.out.println(后续遍历); //比较当前节点是不是 if (this.val no) return this; return resNode; } }