乐趣区

关于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);
 }
}
退出移动版