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

54次阅读

共计 5786 个字符，预计需要花费 15 分钟才能阅读完成。

应用的数据结构

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

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);
 }
}

正文完
java
发表至： java
2020-09-19
 0
Spring Cloud Alibaba Sentinel 整合 Feign 的设计实现
cas调用链
springbootplus后台快速开发框架100RELEASE发布了
使用Prometheus+Grafana监控JVM