public class BinaryTree { private static class Node { // 定义树的节点 private int value; // 节点当中的值 private Node leftNode; // 左子节点 private Node rightNode; // 右子节点 public Node(int value) { this.value = value; // 初始化节点赋值 } @Override public String toString() { return "Node{" + "value=" + value + '}'; } } private Node root; // 定义根节点 public BinaryTree() { this.root = null; // 初始化根节点为null } // 添加叶子节点 public boolean addLeaf(Node node) { if (node == null) return false; if (root == null) { // 第一个节点直接设置为根节点 root = node; return true; } // 找到要添加节点的位置 Node currNode = root; Node currNodeParent = null; boolean isLeftNode = false; while (currNode != null) { currNodeParent = currNode; // 当前节点成为父节点 if (node.value < currNode.value) { // 小于当前节点 currNode = currNode.leftNode; // 左子结点成为当前节点 isLeftNode = true; // 添加位置是左节点 } else { currNode = currNode.rightNode; // 右子节点成为当前节点 isLeftNode = false; // 添加位置是右节点 } } if (isLeftNode) { // 位置是左节点，那么父级节点的左节点设置为node currNodeParent.leftNode = node; } else { // 位置是右节点，那么父级节点的右节点设置为node currNodeParent.rightNode = node; } // 返回true return true; } // 查找节点 public Node findNode(int value) { if (root == null) return null; Node currNode = root; while (currNode.value != value) { // 如果找到值相等的节点中断循环 if (value < currNode.value) { currNode = currNode.leftNode; } else { currNode = currNode.rightNode; } if (currNode == null) return null; } return currNode; } // 删除 public boolean deleteNode(Node node) { if (root == null || node == null) return false; // 获取被删除节点的父节点 Node parentNode = null; Node currNode = root; boolean isLeftNode = false; // 当前节点是父节点的左子结点 while (currNode.value != node.value) { // 当找到值匹配的当前节点终止循环 parentNode = currNode; // 当前节点成为父节点 if (node.value < currNode.value) { currNode = currNode.leftNode; isLeftNode = true; } else { currNode = currNode.rightNode; isLeftNode = false; } } if (node.leftNode == null && node.rightNode == null) { // 被删除的节点没有子节点，直接将父节点的子节点置为null即可 if (root == node) { // 如果被删除的是根节点 root = null; } else if (isLeftNode) { // 被删除的是父节点的左子结点 parentNode.leftNode = null; } else { // 被删除的是父节点的右子节点 parentNode.rightNode = null; } } else if (node.leftNode == null) { // 被删除节点有1个右子节点 if (root == node) { root = node.rightNode; // 右子节点设置为根节点 } else if (isLeftNode) { parentNode.leftNode = node.rightNode; // 右子节点设置为被删除节点的父节点的左子结点 } else { parentNode.rightNode = node.rightNode; // 右子节点设置为被删除节点的父节点的右子节点 } } else if (node.rightNode == null) { // 被删除的节点有1个左子结点 if (root == node) { root = node.leftNode; // 左子结点设置为根节点 } else if (isLeftNode) { parentNode.leftNode = node.leftNode; // 左子结点设置为被删除节点的父节点的左子结点 } else { parentNode.rightNode = node.leftNode; // 左子结点设置为被删除节点的父节点的右子节点 } } else { // 被删除的节点有2个子节点 // 先找到中序后继节点 Node successorNode = currNode.rightNode; Node successorParentNode = null; while (successorNode.leftNode != null) { successorParentNode = successorNode; // 设置中序后继节点的父节点 successorNode = successorNode.leftNode; // 找到中序后继节点 } // 如果右节点就是后继节点 if (successorParentNode == null) { if (root == node) { // 删除的是根节点 successorNode.leftNode = root.leftNode; // 根节点的左子结点设置为后继节点的左子结点 root = successorNode; // 后继节点设置为根节点 } else if (isLeftNode) { parentNode.leftNode = successorNode; // 被删除节点的父节点的左子结点设置为后继节点 successorNode.leftNode = node.leftNode; // 被删除节点的左子结点设置为后继节点的左子结点 } else { parentNode.rightNode = successorNode; // 被删除节点的父节点的右子节点设置为后继节点 successorNode.leftNode = node.leftNode; // 被删除节点的左子结点设置为后继节点的左子结点 } } else { // 如果右节点不是后继节点 successorParentNode.leftNode = successorNode.rightNode; // 后继节点的左子结点设置为后继节点的父级的左子结点 successorNode.rightNode = root.rightNode; // 后继节点的右节点设置为根节点的右子节点 if (root == node) { successorNode.leftNode = root.leftNode; // 后继节点的左子结点设置为根节点的左子结点 root = successorNode; // 后继节点设置为根节点 } else if (isLeftNode) { successorNode.leftNode = node.leftNode; // 被删除节点的左子结点设置为后继节点的左子结点 parentNode.leftNode = successorNode; // 后继节点设置为被删除节点的父级节点的左子结点 } else { successorNode.leftNode = node.leftNode; // 被删除节点的左子结点设置为后继节点的左子结点 parentNode.rightNode = successorNode; // 后继节点设置为被删除节点的父级节点的右子节点 } } } return true; } // 遍历 public void traverse(int type) { switch (type) { case 1: // 前序 preOrder(root); break; case 2: // 中序 inOrder(root); break; case 3: // 后序 postOrder(root); break; } } // 前序遍历 private void preOrder(Node node) { if (node != null) { System.out.println(node); preOrder(node.leftNode); preOrder(node.rightNode); } } // 中序遍历 private void inOrder(Node node) { if (node != null) { inOrder(node.leftNode); System.out.println(node); inOrder(node.rightNode); } } // 后序遍历 private void postOrder(Node node) { if (node != null) { postOrder(node.leftNode); postOrder(node.rightNode); System.out.println(node); } } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); System.out.println("添加节点-------------"); tree.addLeaf(new Node(3)); tree.addLeaf(new Node(1)); tree.addLeaf(new Node(2)); tree.addLeaf(new Node(0)); tree.addLeaf(new Node(5)); tree.addLeaf(new Node(4)); tree.addLeaf(new Node(6)); System.out.println("中序遍历--------------"); tree.traverse(2); System.out.println("查找节点--------------"); Node node = tree.findNode(3); System.out.println(node); System.out.println("删除节点--------------"); tree.deleteNode(node); tree.traverse(2); } }