代码实现
在最后面
package com.lin.tree_0308; public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); HeroNode heroNode1 = new HeroNode(1, "伍六七"); HeroNode heroNode2 = new HeroNode(2, "梅花十一"); HeroNode heroNode3 = new HeroNode(3, "梅花十三"); HeroNode heroNode4 = new HeroNode(4, "江主任"); HeroNode heroNode5 = new HeroNode(5, "希义"); heroNode1.setLeft(heroNode2); heroNode1.setRight(heroNode3); heroNode3.setRight(heroNode4); heroNode3.setLeft(heroNode5); binaryTree.setRoot(heroNode1); // System.out.println("前序遍历:"); // binaryTree.preOrder(); // System.out.println("中序遍历:"); // binaryTree.infixOrder(); // // System.out.println("后序遍历"); // binaryTree.postOrder(); // System.out.println("前序查找:"); // HeroNode preOrderSearch = binaryTree.preOrderSearch(5); // if(preOrderSearch != null) { // System.out.println(preOrderSearch); // } else { // System.out.println("没有找到"); // } // System.out.println("中序查找:"); // HeroNode infixOrderSearch = binaryTree.infixOrderSearch(5); // if(infixOrderSearch != null) { // System.out.println(infixOrderSearch); // } else { // System.out.println("没有找到"); // } // // System.out.println("后序查找:"); // HeroNode postOrderSearch = binaryTree.postOrderSearch(5); // if(postOrderSearch != null) { // System.out.println(postOrderSearch); // } else { // System.out.println("没有找到"); // } System.out.println("删除前"); binaryTree.preOrder(); binaryTree.delNode(2); System.out.println("删除后"); binaryTree.preOrder(); } }
class BinaryTree{ private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } // 删除节点 public void delNode(int no) { if (root != null) { // 如果只有一个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; } } }
class HeroNode{ private String name; private int no; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } 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 [name=" + name + ", no=" + 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); // 输出父节点 } // 前序查找 public HeroNode preOrderSearch(int no) { System.out.println("1"); // 比较当前节点是不是 if(this.no == no) { return this; } // 1 判断当前节点的左节点是否为空,如果不为空,则递归前序查找 // 2 如果左递归前序查找,找到节点,则返回 HeroNode resNode = null; if(this.left != null) { resNode = this.left.preOrderSearch(no); } if(resNode != null) {// 说明左子树找到了 return resNode; } // 1 左递归如果没有找到,则继续判断 // 2 当前节点的右节点是否为空,如果不为空,则继续向右递归前序查找 if(this.right != null) { resNode = this.right.preOrderSearch(no); } // 这时候不管有没有找到都要返回resNode return resNode; } // 中序查找 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("1"); 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; } System.out.println("1"); if(this.no == no) { return this; } // 如果都没有找到 return resNode; } /** * * @Description:1 因为我们的二叉树是单向,所以我们是判断当前节点的子节点是否需要删除节点,而不是直接去判断当前节点是否需要删除节点。<br> * 2 如果当前节点的左子节点不为空,并且左子节点就是要删除节点,就将this.left = null;并且就返回(结束递归删除) <br> * 3 如果当前节点的右子节点不为空,并且右子节点就是要删除节点,就将this.right = null;并且就返回(结束递归删除) <br> * 4 如果第2和第3都没有删除节点,那么我们就需要向左子树进行递归删除<br> * 5 如果第4补也没有删除节点,则向右子树进行递归删除<br> * @author LinZM * @date 2021-3-8 15:17:32 * @version V1.8 */ 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); } } }
仅供参考,有错误还请指出!
有什么想法,评论区留言,互相指教指教。
觉得不错的可以点一下右边的推荐哟