充分利用空节点，作为前驱节点或后继节点。
public class HeroNode { private int no; private String name; //默认为null 左节点或前驱结点 private HeroNode left; //默认为null 右节点或后继节点 private HeroNode right; //0表示指向左子树，1表示指向前驱节点 private int leftType; //0表示右子树，1表示后继节点 private int rightType; public HeroNode(int no, String name) { this.no = no; this.name = name; } /** * 递归删除节点 * 如果删除节点是叶子节点，直接删除 * 如果删除节点是非叶子节点，删除数 * * @param no */ 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); } if (this.right != null) { this.right.delNode(no); } } /** * 前序遍历方法 */ 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); } /** * 前序查找 * * @param no * @return */ public HeroNode preOrderSearch(int no) { // 比较当前节点 if (this.no == no) { return this; } //定义返回内容 HeroNode res = null; //搜索左子节点 if (this.left != null) { res = this.left.preOrderSearch(no); } //搜索右子节点 if (res == null && this.right != null) { res = this.right.preOrderSearch(no); } return res; } /** * 中序查找 * * @param no * @return */ public HeroNode infixOrderSearch(int no) { //定义返回内容 HeroNode res = null; //搜索左子节点 if (this.left != null) { res = this.left.preOrderSearch(no); } // 比较当前节点 if (res == null && this.no == no) { return this; } //搜索右子节点 if (res == null && this.right != null) { res = this.right.preOrderSearch(no); } return res; } /** * 后序查找 * * @param no * @return */ public HeroNode postOrderSearch(int no) { //定义返回内容 HeroNode res = null; //搜索左子节点 if (this.left != null) { res = this.left.preOrderSearch(no); } //搜索右子节点 if (res == null && this.right != null) { res = this.right.preOrderSearch(no); } // 比较当前节点 if (res == null && this.no == no) { return this; } return res; } 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; } 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } }
public class ThreadedBinaryTree { private HeroNode root; //指向当前节点的前驱节点的指针 private HeroNode pre = null; public void setRoot(HeroNode root) { this.root = root; } public void threadedNodes() { threadedNodes(root); } /** * 遍历线索化二叉树的方法 */ public void threadedList() { HeroNode node=root; while (node!=null){ // 找到第一个节点 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(); } } /** * 对二叉树进行中序线索化 * * @param node */ public void threadedNodes(HeroNode node) { //如果node==null,不能线索化 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()); } /** * 递归删除节点 * 如果删除节点是叶子节点，直接删除 * 如果删除节点是非叶子节点，删除数 * * @param no */ public void delNode(int no) { if (root == null) { return; } if (root.getNo() == no) { root = null; return; } root.delNode(no); } /** * 前序遍历方法 */ public void preOrder() { System.out.println("前序遍历"); if (this.root != null) { this.root.preOrder(); } else { System.out.println("二叉树为空"); } } /** * 中序遍历方法 */ public void infixOrder() { System.out.println("中序遍历"); if (this.root != null) { this.root.infixOrder(); } else { System.out.println("二叉树为空"); } } /** * 后序遍历方法 */ public void postOrder() { System.out.println("后序遍历"); if (this.root != null) { this.root.postOrder(); } else { System.out.println("二叉树为空"); } } /** * 前序查找 * * @param no * @return */ public HeroNode preOrderSearch(int no) { HeroNode res = null; System.out.println("前序查找"); if (this.root != null) { res = this.root.preOrderSearch(no); } else { System.out.println("二叉树为空"); } return res; } /** * 中序查找 * * @param no * @return */ public HeroNode infixOrderSearch(int no) { HeroNode res = null; System.out.println("中序查找"); if (this.root != null) { res = this.root.infixOrderSearch(no); } else { System.out.println("二叉树为空"); } return res; } /** * 后序查找 * * @param no * @return */ public HeroNode postOrderSearch(int no) { HeroNode res = null; System.out.println("后序查找"); if (this.root != null) { res = this.root.postOrderSearch(no); } else { System.out.println("二叉树为空"); } return res; } }
public class ThreadedBinaryTreeDemo { public static void main(String[] args) { HeroNode root = new HeroNode(1, "tom"); HeroNode node2 = new HeroNode(3, "jack"); HeroNode node3 = new HeroNode(6, "smith"); HeroNode node4 = new HeroNode(8, "mary"); HeroNode node5 = new HeroNode(10, "king"); HeroNode node6 = new HeroNode(14, "dim"); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadedBinaryTree tree = new ThreadedBinaryTree(); tree.setRoot(root); tree.threadedNodes(); System.out.println(tree); // 测试 System.out.println(node5.getLeft()); System.out.println(node5.getRight()); } }
