二叉排序树的增删改查（java版）

最后的删除，目前我测试的是正确的

1. 基本节点

TreeNode:

class TreeNode{private int val;TreeNode left;TreeNode right;public void setLeft(TreeNode left){this.left = left;}public void setRight(TreeNode right){this.right = right;}TreeNode(){}TreeNode(int val){this.val = val;}public int getVal(){return this.val;}public String toStringNode(){String ans = "[ val = " + this.val;if(this.left != null){ans += "->left = " + this.left.toStringNode();}if(this.right != null){ans += "->right = " + this.right.toStringNode() + "]";}return ans;}public void setVal(int val){this.val = val;}
}

2. 二叉排序树

class BinaryTree{public TreeNode root;
}

里面写一些方法吧！！！

2.1 增加节点

其实就是插入：

public void insert(int val){TreeNode newNode = new TreeNode(val);if(root == null){root = newNode;return;}TreeNode curNode = root;TreeNode preNode;while(true){preNode = curNode;if(newNode.getVal() > curNode.getVal()){curNode = curNode.right;if(curNode == null){preNode.setRight(newNode);return;}}else{curNode = curNode.left;if(curNode == null){preNode.setLeft(newNode);return;}}}}

2.2 查找（就是遍历）就一起写了吧

跟修改一样

public void inOrder(TreeNode root){if(root == null)return;inOrder(root.left);System.out.print(root.getVal() + " ");inOrder(root.right);}public void preOrder(TreeNode root){if(root == null)return;System.out.print(root.getVal() + " ");preOrder(root.left);preOrder(root.right);}public void HOrder(TreeNode root){if(root == null)return;HOrder(root.left);HOrder(root.right);System.out.print(root.getVal() + " ");}

2.3 广度优先遍历

利用队列

// 广度优先搜索void BFS(){if(this.root == null){System.out.println("BFS: null");return;}System.out.print("BFS: ");Queue<TreeNode> queue = new LinkedList<>();queue.add(this.root);while(!queue.isEmpty()){TreeNode cur = queue.poll();System.out.print(cur.getVal() + " ");if(cur.left != null)queue.add(cur.left);if(cur.right != null)queue.add(cur.right);}}

2.4 删除（这个有点意思）

分了六类情况：

• 目标节点是叶子节点（直接删了）
• 目标节点只有一个孩子（直接连接上）
• 目标节点有俩孩子
  • 左孩子没有右孩子（把目标右子树连在左孩子的右孩子上，然后目标父亲那条指向左孩子）
  • 右孩子没有左孩子（把目标左子树连在右孩子的左孩子上，然后目标父亲那条指向右孩子）
  • 最坏情况了，找目标节点的左孩子最右或者左孩子最左（交换值，删了那个被交换的孩子）

// 删除节点// 获取最左最右节点public TreeNode getLR(TreeNode root){if(root == null || (root.left == null && root.right == null))return null;TreeNode ans;if(root.left != null){if(root.left.right == null)return root.left;ans = root.left.right;while(ans.right != null){ans = ans.right;}// System.out.println("获取最右");return ans;}if(root.right != null){if(root.right.left == null)return root.right;ans = root.right.left;while(ans.left != null){ans = ans.left;}// System.out.println("获取最左");return ans;}return null;}// 获取父节点public TreeNode getParent(TreeNode root, int val){if(root == null || (root.left == null && root.right == null) || root.getVal() == val)return null;// 左孩子不等if(root.getVal() > val){if(root.left != null){if(root.left.getVal() == val)return root;elsereturn getParent(root.left, val);}elsereturn null;}else{if(root.right != null){if(root.right.getVal() == val)return root;elsereturn getParent(root.right, val);}elsereturn null;}}public void delNode(int val){TreeNode parent = new TreeNode(Integer.MAX_VALUE);parent.left = root;delNode(val, parent, null);this.root = parent.left;}public void delNode(int val, TreeNode root, TreeNode parent){if(root == null)return;if(root.getVal() < val){delNode(val, root.right, root);}else if(root.getVal() > val){delNode(val, root.left, root);}else{  // 相等if(root.left != null && root.right == null){    // 没有左孩子if(parent.left == root){parent.left = root.left;}else{parent.right = root.left;}}else if(root.left == null && root.right != null){  // 没有右孩子if(parent.left == root){parent.left = root.right;}else{parent.right = root.right;}}else if(root.left == null && root.right == null){  // 都是nullif(parent.left == root){parent.left = null;}else{parent.right = null;} }else{ // 进行交换if(root.left.right == null){root.left.right = root.right;if(parent.left == root){parent.left = root.left;}else{parent.right = root.left;}}else if(root.right.left == null){root.right.left = root.left;if(parent.left == root){parent.left = root.left;}else{parent.right = root.left;}}else{TreeNode cur = getLR(root); // 获取最左最右节点// 删除那个节点TreeNode curParent = getParent(root, cur.getVal()); // 获取父节点if(curParent.getVal() > cur.getVal())curParent.left = null;else{curParent.right = null;}root.setVal(cur.getVal());  // 设置值}}}}

2.5 测试样例

public class Test2{public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);// 进行构建node1.setRight(node2);node1.setLeft(node3);node3.setLeft(node4);node4.setLeft(node5);node4.setRight(node6);// System.out.println(node1.toStringNode());BinaryTree b = new BinaryTree();b.insert(5);b.insert(7);b.insert(4);b.insert(2);b.insert(0);b.insert(3);b.insert(8);b.insert(6);b.insert(1);// System.out.println(b.root.toStringNode());// System.out.println(b.getParent(b.root, 3).getVal());for(int i = 8; i >= 0; i--){System.out.println("删除了：" + i);b.delNode(i);b.BFS();System.out.println();}// // 中序// System.out.println("中序：");// // 先序// System.out.println();// System.out.println("先序：");// b.preOrder(b.root);// // 后序// System.out.println();// System.out.println("后序：");// b.HOrder(b.root);// // 深度System.out.println();b.BFS();}
}