public class HeroNode { private int no; private String name; //默认为null private HeroNode left; //默认为null private HeroNode right; 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } }
public class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } /** * 递归删除节点 * 如果删除节点是叶子节点,直接删除 * 如果删除节点是非叶子节点,删除数 * * @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 BinaryTreeDemo { public static void main(String[] args) { //创建二叉树 BinaryTree bt = new BinaryTree(); HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2, "吴用"); HeroNode node3 = new HeroNode(3, "卢俊义"); HeroNode node4 = new HeroNode(4, "林冲"); HeroNode node5 = new HeroNode(5, "关胜"); root.setLeft(node2); root.setRight(node3); node3.setRight(node4); node3.setLeft(node5); bt.setRoot(root); 1 2 3 4 5 //bt.preOrder(); 2 1 5 3 4 //bt.infixOrder(); 2 5 4 3 1 //bt.postOrder(); //System.out.println(bt.preOrderSearch(2)); //System.out.println(bt.infixOrderSearch(2)); //System.out.println(bt.postOrderSearch(2)); bt.preOrder(); System.out.println(); bt.delNode(5); bt.preOrder(); } }
前序遍历 HeroNode{no=1, name='宋江'} HeroNode{no=2, name='吴用'} HeroNode{no=3, name='卢俊义'} HeroNode{no=5, name='关胜'} HeroNode{no=4, name='林冲'} 前序遍历 HeroNode{no=1, name='宋江'} HeroNode{no=2, name='吴用'} HeroNode{no=3, name='卢俊义'} HeroNode{no=4, name='林冲'}