Java实现二叉搜索树（增删功能）

引入

二叉搜索树，左节点的值<当前节点的值<右节点的值 二叉搜索树难在删除，我用Java递归实现删除代码，并且附上注释解释，做个笔记

代码

BinaryTreeClass .java

import java.util.Stack; public class BinaryTreeClass { // 中序遍历，用来验证是否删除成功 public void midorder(TreeNode curnode){ Stack<TreeNode> stack = new Stack<>(); while(curnode != null || !stack.isEmpty()){ // 依次把左子树压入栈 while(curnode != null){ stack.push(curnode); curnode = curnode.leftNode; } // 遍历完左子树，弹出栈顶并访问 curnode = stack.pop(); System.out.print(curnode.val+" "); // 变换为它的右节点继续中序遍历 curnode = curnode.rightNode; } System.out.println(); } // 在二叉搜索树中增加一个节点 public TreeNode insertNode(TreeNode tr, int val){ // 如果tr节点为空，代表找到了该值的位置，实例化它并且返回去，在上一层中会对它绑定在哪个节点上 if(tr == null){ tr = new TreeNode(val); }else{ // 插入值小于当前节点值，代表要往左边插入 if(val < tr.val){ // tr.leftnode设置为返回的节点 tr.leftNode = insertNode(tr.leftNode, val); }else if(val > tr.val){ // tr.rightnode设置为返回的节点 tr.rightNode = insertNode(tr.rightNode, val); } } // 返回节点 return tr; } // 在二叉搜索树中根据值来删除节点 public TreeNode delete(TreeNode tr, int val){ // 如果为空，说明整个二叉搜索树中没有找到这个元素 if(tr == null){ System.out.println("未找到要删的元素"); }else{ // 1.往左边找 if(val < tr.val){ tr.leftNode = delete(tr.leftNode, val); }else if(val > tr.val){ // 2.往右边找 tr.rightNode = delete(tr.rightNode, val); }else{ // 3.找到了，进行处理 /* 第一种情况，左右节点都存在，就变换为第二种情况 在右子树中找到一个没有子节点的节点或者只有右节点的节点来代替自己（简单的理解为：右子树中最小的节点，这个最小的节点是没有子节点或者只有右节点的） 再删除这个新找到的节点 */ if(tr.leftNode != null && tr.rightNode != null){ // 1.往右边找最小的节点来代替自己。 TreeNode findtr = findMin(tr.rightNode); // 2.并未实际删除tr本身，而是更换值 tr.val = findtr.val; // 3.从右子树中实际删除findtr节点,从tr的右节点开始，找要删除的元素值，对其删除 /* 递归删除，找到后会进入第二种情况 如果findtr是没有子节点，直接tr.rightnode置为null 如果有右子节点，则将它设为tr的右节点（此时，findtr的右子节点代替了findtr的位置） */ tr.rightNode = delete(tr.rightNode, findtr.val); }else{ // 第二种情况,1.有一个子节点。 2.没有子节点。 if(tr.leftNode == null){ // 当左节点不存在或者左右节点都不存在，tr直接变化为它的右节点。（因为右节点不存在的话也只能是空） tr = tr.rightNode; }else{ // 否则，tr变为它的左节点 tr = tr.leftNode; } } } } return tr; } // 找到右子树中最小的节点，就是右子树的最左节点或者第一个自己 public TreeNode findMin(TreeNode tr){ // 当tr没有子节点就直接返回自己 if(tr.leftNode == null){ return tr; }else{ // 持续遍历左节点 return findMin(tr.leftNode); } } public static void main(String[] args) { TreeNode root = new TreeNode(6); BinaryTreeClass btc = new BinaryTreeClass(); // 建立二叉搜索树，自动构建 btc.insertNode(root, 6); btc.insertNode(root, 4); btc.insertNode(root, 3); btc.insertNode(root, 5); btc.insertNode(root, 8); btc.insertNode(root, 7); btc.insertNode(root, 14); btc.insertNode(root, 13); btc.insertNode(root, 16); btc.insertNode(root, 2); System.out.println("未删除前的子树："); btc.midorder(root); System.out.println("删除一个节点它只有左节点的情况："); btc.delete(root, 3);// 2顶替了自己的位置 btc.midorder(root); System.out.println("删除一个节点它有左右节点的情况"); btc.delete(root, 8); btc.midorder(root);// 可见13顶替了自己8的位置 } }

运行结果：

TreeNode.java

public class TreeNode { TreeNode leftNode; TreeNode rightNode; int val; public TreeNode() { // TODO Auto-generated constructor stub } public TreeNode(int vl) { // TODO Auto-generated constructor stub this.val = vl; } public TreeNode getLeftNode() { return leftNode; } public void setLeftNode(TreeNode leftNode) { this.leftNode = leftNode; } public TreeNode getRightNode() { return rightNode; } public void setRightNode(TreeNode rightNode) { this.rightNode = rightNode; } public int getVal() { return val; } public void setVal(int val) { this.val = val; } }