关于java:Java实现二叉树遍历查询删除算法

应用的数据结构

这里应用的数据结构是一个节点对象，代码如下：

public class TreeNode {    private Integer val;//序号 private TreeNode left;//左孩子 private TreeNode right;//右孩子 public TreeNode(int val){        this.val = val; }    public Integer getVal() {        return val; }    public void setVal(Integer val) {        this.val = val; }    public TreeNode getLeft() {        return left; }    public void setLeft(TreeNode left) {        this.left = left; }    public TreeNode getRight() {        return right; }    public void setRight(TreeNode right) {        this.right = right; }}

遍历

要实现二叉树的遍历有三种方法，别离是前序遍历、中序遍历和后序遍历
- 前序遍历：先找父节点，再找左右子节点
- 中序遍历：先找左子节点，再找父节点，最初找右子节点
- 后序遍历：先找左右子节点，再找父节点
从这能够看出，所谓的前/中/后序，其实是绝对于父节点来说，如果是前序，那么父节点就是先于左右子节点，如果是中序，那么父节点就是在左右子节点两头，如果是后序，那么父节点就是在最初
举个例子：如下图所示
- 对于前序：
  - 先输入父节点18，再看左子节点20，左子节点也是个父节点，输入20，再看20的左子节点16，发现16是个叶子节点间接输入。
  - 这样对于父节点18来说，它本人自身以及它的左子节点曾经遍历完了，再看它的右子节点29
  - 右子节点29是父节点，先输入29，再看29的左子节点，发现是个叶子节点，间接输入。再看29的右子节点，也是8，间接输入
  - 这样整个二叉树就遍历完了
- 中序和后序也是一样的办法
代码如下：

我这里用的是递归的办法

public class TreeTraversal {    //前序遍历 public static void preorder_Traversal(TreeNode root){        if (root == null) return; System.out.println(root.getVal()); preorder_Traversal(root.getLeft()); preorder_Traversal(root.getRight()); }    //中序遍历 public static void inorder_Traversal(TreeNode root){        if (root == null) return; inorder_Traversal(root.getLeft()); System.out.println(root.getVal()); inorder_Traversal(root.getRight()); }    //后序遍历 public static void postorder_Traversal(TreeNode root){        if (root == null) return; postorder_Traversal(root.getLeft()); postorder_Traversal(root.getRight()); System.out.println(root.getVal()); }    public static void main(String[] args) {        TreeNode node1 = new TreeNode(18); TreeNode node2 = new TreeNode(20); TreeNode node3 = new TreeNode(29); TreeNode node4 = new TreeNode(16); TreeNode node5 = new TreeNode(39); TreeNode node6 = new TreeNode(8); node1.setLeft(node2); node1.setRight(node3); node2.setLeft(node4); node3.setLeft(node5); node3.setRight(node6); postorder_Traversal(node1); }}

查问

查问和遍历是一样的，也分前序、中序和后序，只是在遍历的时候多进行一次比拟，这里就不多说了
代码如下：

//前序查找public static TreeNode preOrder_Search(TreeNode root, int findVal){    if (root == null) return null; //判断以后节点的值是否等于findVal if (root.getVal() == findVal){        return root; }    //向左子节点递归查找 TreeNode node = preOrder_Search(root.getLeft(), findVal); //如果node不为空，证实找到了 if (node != null) return node; //如果左子节点没有找到，向右查找 node = preOrder_Search(root.getRight(), findVal); if (node != null) return node; return node;}//中序查找public static TreeNode inOrder_Search(TreeNode root, int findVal){    if (root == null) return null; //向左子节点递归查找 TreeNode node = inOrder_Search(root.getLeft(), findVal); //如果node不为空，证实找到了 if (node != null) return node; //判断以后节点的值是否等于findVal System.out.println("比拟"); if (root.getVal() == findVal){        return root; }    //如果左子节点没有找到，向右查找 node = inOrder_Search(root.getRight(), findVal); if (node != null) return node; return node;}//后序查找public static TreeNode postOrder_Search(TreeNode root, int findVal){    if (root == null) return null; //向左子节点递归查找 TreeNode node = postOrder_Search(root.getLeft(), findVal); //如果node不为空，证实找到了 if (node != null) return node; //如果左子节点没有找到，向右查找 node = postOrder_Search(root.getRight(), findVal); if (node != null) return node; //判断以后节点的值是否等于findVal System.out.println("比拟"); if (root.getVal() == findVal){        return root; }    return node;}

删除

二叉树删除节点有两种状况：
- 1）删除的是叶子节点，则间接删除
- 2）删除的是非叶子节点，则要删除子树
基本思路：
- 1）如果只有一个根节点，并且是咱们要找的节点，则间接置空
- 2）判断以后节点的子节点是否是要删除的节点：
  - 如果以后节点的左子节点不为空，并且是要删除的节点，那么将左子节点置空
  - 如果以后节点的右子节点不为空，并且是要删除的节点，那么将右子节点置空
- 3）如果以后节点的子节点不是要删除的节点，那么向左子树递归
- 4）如果步骤3）也没删除，那么向右子树递归
代码如下：

public class TreeTraversal {    private static TreeNode root = null; //前序遍历 public static void preorder_Traversal(TreeNode root){        if (root == null) return; System.out.print(root.getVal() + " "); preorder_Traversal(root.getLeft()); preorder_Traversal(root.getRight()); }    //中序遍历 public static void inorder_Traversal(TreeNode root){        if (root == null) return; inorder_Traversal(root.getLeft()); System.out.println(root.getVal()); inorder_Traversal(root.getRight()); }    //后序遍历 public static void postorder_Traversal(TreeNode root){        if (root == null) return; postorder_Traversal(root.getLeft()); postorder_Traversal(root.getRight()); System.out.println(root.getVal()); }    //前序查找 public static TreeNode preOrder_Search(TreeNode root, int findVal){        if (root == null) return null; //判断以后节点的值是否等于findVal if (root.getVal() == findVal){            return root; }        //向左子节点递归查找 TreeNode node = preOrder_Search(root.getLeft(), findVal); //如果node不为空，证实找到了 if (node != null) return node; //如果左子节点没有找到，向右查找 node = preOrder_Search(root.getRight(), findVal); if (node != null) return node; return node; }    //中序查找 public static TreeNode inOrder_Search(TreeNode root, int findVal){        if (root == null) return null; //向左子节点递归查找 TreeNode node = inOrder_Search(root.getLeft(), findVal); //如果node不为空，证实找到了 if (node != null) return node; //判断以后节点的值是否等于findVal System.out.println("比拟"); if (root.getVal() == findVal){            return root; }        //如果左子节点没有找到，向右查找 node = inOrder_Search(root.getRight(), findVal); if (node != null) return node; return node; }    //后序查找 public static TreeNode postOrder_Search(TreeNode root, int findVal){        if (root == null) return null; //向左子节点递归查找 TreeNode node = postOrder_Search(root.getLeft(), findVal); //如果node不为空，证实找到了 if (node != null) return node; //如果左子节点没有找到，向右查找 node = postOrder_Search(root.getRight(), findVal); if (node != null) return node; //判断以后节点的值是否等于findVal System.out.println("比拟"); if (root.getVal() == findVal){            return root; }        return node; }    //删除节点 public static void delete(int val){        deleteRootNode(val); }    public static void deleteRootNode(int val){        if (root == null) return; if (root.getVal() == val){            root = null; }else {            deleteChildNode(root, val); }    }    public static void deleteChildNode(TreeNode root, int val){        if (root.getLeft() != null && root.getLeft().getVal() == val){            root.setLeft(null); return; }        if (root.getRight() != null && root.getRight().getVal() == val){            root.setRight(null); return; }        if (root.getLeft() != null){            deleteChildNode(root.getLeft(), val); }        if (root.getRight() != null){            deleteChildNode(root.getRight(), val); }    }    public static void main(String[] args) {        root = new TreeNode(18); TreeNode node2 = new TreeNode(20); TreeNode node3 = new TreeNode(29); TreeNode node4 = new TreeNode(16); TreeNode node5 = new TreeNode(39); TreeNode node6 = new TreeNode(8); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node3.setLeft(node5); node3.setRight(node6); preorder_Traversal(root); delete(20); System.out.println(); preorder_Traversal(root); }}