闲暇之余，手写了个二叉搜索树的代码实现，包括对二叉搜索树的构建、遍历、查询、删除节点的算法。
二叉搜索树
二叉查找树（Binary Search Tree），（又叫：二叉搜索树，二叉排序树），
特点：
- 是一棵空树；
- 具有下列性质的二叉树：
- 2.1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 2.2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 2.3、它的左、右子树也分别为二叉排序树。
二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
代码实现
首先，定义一个树的数据节点：
|
1 2 3 4 5 6 7 8 9 10 |
//定义二叉树 class TreeNode{ int data; TreeNode left; TreeNode right; public TreeNode(int data) { this.data = data; } } |
构建二叉搜索树
使用递归的方式，插入节点，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
/** * 插入节点 * @param tree * @param data * @return */ public TreeNode insert(TreeNode tree,int data){ if(tree == null){ return new TreeNode(data); } int _data = tree.data; if(data < _data){ tree.left = insert(tree.left,data); }else{ tree.right = insert(tree.right,data); } return tree; } |
测试：依次插入一个数组
|
1 2 3 4 5 6 7 8 |
int[] datas = new int[]{50,81,31,33,12,22,92,95,67,18,85,98,84,91,15,86,89,59,30,37,83,36,4,74,49,42,7,96}; BinaryTree binaryTree = new BinaryTree(); TreeNode treeNode = null; for(int data : datas){ treeNode = binaryTree.insert(treeNode,data); } System.out.println(new Gson().toJson(treeNode)); |
用图形表示如下图：
二叉搜索树的遍历：
根据根节点的遍历顺序，分为前序遍历，中序遍历，后序遍历。
前序遍历
遍历思路：根结点 —> 左子树 —> 右子树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/** * 前序遍历 * @param tree * @param nums 遍历的结果值 */ public void preorder(TreeNode tree, List<Integer> nums){ if(tree == null) return; //先访问根节点 nums.add(tree.data); //访问左儿子 preorder(tree.left,nums); //访问右儿子 preorder(tree.right,nums); } |
运行结果：
前序遍历：[50,31,12,4,7,22,18,15,30,33,37,36,49,42,81,67,59,74,92,85,84,83,91,86,89,95,98,96]
中序遍历：
遍历思路：左子树–>根节点–>右子树
|
1 2 3 4 5 6 7 8 9 10 11 |
/** * 中序遍历 * @param tree * @param nums */ public void inorder(TreeNode tree, List<Integer> nums){ if(tree == null) return; inorder(tree.left,nums); nums.add(tree.data); inorder(tree.right,nums); } |
遍历结果：
中序遍历：[4,7,12,15,18,22,30,31,33,36,37,42,49,50,59,67,74,81,83,84,85,86,89,91,92,95,96,98]
后序遍历：
遍历思路：左子树—>右子树->根节点
|
1 2 3 4 5 6 7 8 9 10 11 |
/** * 后序遍历 * @param tree * @param nums */ public void postorder(TreeNode tree, List<Integer> nums){ if(tree == null) return; postorder(tree.left,nums); postorder(tree.right,nums); nums.add(tree.data); } |
遍历结果：
后序遍历：[7,4,15,18,30,22,12,36,42,49,37,33,31,59,74,67,83,84,89,86,91,85,96,98,95,92,81,50]
可以看到，前中后序遍历中，中序遍历是严格的从小到大的排序
查询节点
根据一个数值，查询树的节点，从头结点开始递归查找，比当前节点小，往左查找，比当前节点大，往右查找，直至找到相等节点或者查不到返回null。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
/** * 查询节点 * @param tree * @param data * @return */ public TreeNode search(TreeNode tree,int data){ //如果当前节点为空或者 正好相等 直接返回 if(tree == null || tree.data == data) return tree; //如果当前节点小于目标值，往右搜索 if(data > tree.data ){ return search(tree.right,data); }else{ //如果当前节点大于目标值，往左搜索 return search(tree.left,data); } } |
删除节点
删除节点是最复杂的，分几种情况：
1、要删除的如果是叶子节点，直接删除
例如，删除图中的15节点，不会影响其他节点，直接把18节点的left置为空即可。
2、要删除的节点，非叶子节点，左子树为空，则直接用右子节点替换本身所在的位置
例如上图中，删除节点4，只需要把4的父节点（节点12）的left置为其右子节点（节点7）即可。
3、要删除的节点，非叶子节点，右子树为空，则直接用其左子节点替换本身所在的位置。
例如上图中，要删除节点98，只需要把98的父节点（节点95）的right置为其左子节点（节点96）
4、要删除的节点，非叶子节点，且同时存在左右子树
这种情况最复杂，一般来说需要找一个与其数值最接近的节点替换它的位置即可，所以关键有两点：1）寻找最接近的节点，2）替换位置
根据二叉搜索的特性来看，该节点的左子树的最右边的子节点 或者 右子树的最左边的子节点，是最接近被删除节点的，所以一般来说，简单一点，我们直接找右子树的最左子节点。
如上图，如果要删除81节点，则81节点的左子树的最右子节点是74，右子树的最左子节点是83，
我们可以直接用83替换掉81的位置，替换的步骤如下：
1、节点50的right=节点83
2、节点83的left=节点67
3、节点83的right=节点92
4、节点84的left=null ，复杂的情况是，如果节点83还有右子树，则节点84的left应该等于83的右子节点。
实现代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
/** * 删除节点 * @param tree * @param data */ public void delete(TreeNode tree,int data){ TreeNode[] searchNode = searchParent(tree,null,data); //要删除的节点 if(searchNode == null || searchNode[1] == null) return; TreeNode delNode = searchNode[1]; TreeNode parent = searchNode[0]; //目标节点 父节点 TreeNode leftChild = delNode.left; //目标节点左子节点 TreeNode rightChild = delNode.right; //目标节点右子节点 //如果是叶子节点，直接删除 if(leftChild == null && rightChild == null){ if(parent.isLeft(data)){ parent.left=null; }else { parent.right=null; } return; } //如果左子树是空，则直接把右子节点挂到父节点上去 if(leftChild == null){ if(parent.isLeft(data)){ parent.left = rightChild; }else { parent.right = rightChild; } } //如果右子树是空，则直接把左子节点挂到父节点上去 if(rightChild == null){ if(parent.isLeft(data)){ parent.left = leftChild; }else { parent.right = leftChild; } } //既有左儿子，又有右儿子 //先找到右侧最左边的节点 TreeNode[] LeftmostSubtree = this.searchLeftmostSubtree(rightChild,null); if(parent.isLeft(data)){ //最左子节点 挂在 要删除节点的父节点下 parent.left = LeftmostSubtree[1]; }else{ parent.right = LeftmostSubtree[1]; } //最左子节点 的右儿子 上位替换自己 LeftmostSubtree[0].left = LeftmostSubtree[1].right; //最左子节点 替换 要删除的节点 LeftmostSubtree[1].left = delNode.left; LeftmostSubtree[1].right = delNode.right; } /** * 查找目标节点，并返回其父节点 * @param tree * @param parent * @param data * @return 返回数组，0-父节点，1-目标子节点 */ public TreeNode[] searchParent(TreeNode tree,TreeNode parent,int data){ if(tree == null || tree.data == data) return new TreeNode[]{parent,tree}; if(data > tree.data ){ return searchParent(tree.right,tree,data); }else{ return searchParent(tree.left,tree,data); } } /** * 搜索最左子树 * @param tree * @param parent * @return */ public TreeNode[] searchLeftmostSubtree(TreeNode tree,TreeNode parent){ if(tree.left == null){ TreeNode[] nodes = new TreeNode[]{parent,tree}; return nodes; } return searchLeftmostSubtree(tree.left,tree); } |
由于我们在定义的二叉树是单向链接的关系，查询到某个节点，只知道其子节点，不能往上找，删除节点需要涉及目标节点的父节点的指针的改动，所以我们定义了两个方法：
查找目标节点，并返回其父节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/** * 查找目标节点，并返回其父节点 * @param tree * @param parent * @param data * @return 返回数组，0-父节点，1-目标子节点 */ public TreeNode[] searchParent(TreeNode tree,TreeNode parent,int data){ if(tree == null || tree.data == data) return new TreeNode[]{parent,tree}; if(data > tree.data ){ return searchParent(tree.right,tree,data); }else{ return searchParent(tree.left,tree,data); } } |
查找右子树的最左子节点，并返回其父节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/** * 搜索最左子树 * @param tree * @param parent * @return */ public TreeNode[] searchLeftmostSubtree(TreeNode tree,TreeNode parent){ if(tree.left == null){ TreeNode[] nodes = new TreeNode[]{parent,tree}; return nodes; } return searchLeftmostSubtree(tree.left,tree); } |
至此，一个简单的二叉搜索的构建、遍历、查找、删除节点的操作均已完毕，我们发现对于二叉树的CRUD操作基本都是 递归遍历，这也是对于树形结构的最直接、最常用的一种方法，需要大家有这种递归的思维。
下面奉上全部的源码，供参考调试：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 |
package com.arkao.study.algo; import com.google.gson.Gson; import java.util.ArrayList; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; /** * @Description: 二叉搜索树 * @Author: LiuZhaoKao * @email: liuzhaokao@haier.com * @Date: 2021/6/11 9:15 */ public class BinaryTree { //定义二叉树 class TreeNode{ int data; TreeNode left; TreeNode right; public TreeNode(int data) { this.data = data; } public boolean isLeft(int dt){ if(this.left != null && this.left.data == dt) return true; return false; } } /** * 插入节点 * @param tree * @param data * @return */ public TreeNode insert(TreeNode tree,int data){ if(tree == null){ return new TreeNode(data); } int _data = tree.data; if(data < _data){ tree.left = insert(tree.left,data); }else{ tree.right = insert(tree.right,data); } return tree; } /** * 前序遍历 * @param tree * @param nums 遍历的结果值 */ public void preorder(TreeNode tree, List<Integer> nums){ if(tree == null) return; //先访问根节点 nums.add(tree.data); //访问左儿子 preorder(tree.left,nums); //访问右儿子 preorder(tree.right,nums); } /** * 中序遍历 * @param tree * @param nums */ public void inorder(TreeNode tree, List<Integer> nums){ if(tree == null) return; inorder(tree.left,nums); nums.add(tree.data); inorder(tree.right,nums); } /** * 后序遍历 * @param tree * @param nums */ public void postorder(TreeNode tree, List<Integer> nums){ if(tree == null) return; postorder(tree.left,nums); postorder(tree.right,nums); nums.add(tree.data); } /** * 查询节点 * @param tree * @param data * @return */ public TreeNode search(TreeNode tree,int data){ //如果当前节点为空或者 正好相等 直接返回 if(tree == null || tree.data == data) return tree; //如果当前节点小于目标值，往右搜索 if(data > tree.data ){ return search(tree.right,data); }else{ //如果当前节点大于目标值，往左搜索 return search(tree.left,data); } } /** * 查找目标节点，并返回其父节点 * @param tree * @param parent * @param data * @return 返回数组，0-父节点，1-目标子节点 */ public TreeNode[] searchParent(TreeNode tree,TreeNode parent,int data){ if(tree == null || tree.data == data) return new TreeNode[]{parent,tree}; if(data > tree.data ){ return searchParent(tree.right,tree,data); }else{ return searchParent(tree.left,tree,data); } } /** * 搜索最左子树 * @param tree * @param parent * @return */ public TreeNode[] searchLeftmostSubtree(TreeNode tree,TreeNode parent){ if(tree.left == null){ TreeNode[] nodes = new TreeNode[]{parent,tree}; return nodes; } return searchLeftmostSubtree(tree.left,tree); } /** * 删除节点 * @param tree * @param data */ public void delete(TreeNode tree,int data){ TreeNode[] searchNode = searchParent(tree,null,data); //要删除的节点 if(searchNode == null || searchNode[1] == null) return; TreeNode delNode = searchNode[1]; TreeNode parent = searchNode[0]; //目标节点 父节点 TreeNode leftChild = delNode.left; //目标节点左子节点 TreeNode rightChild = delNode.right; //目标节点右子节点 //如果是叶子节点，直接删除 if(leftChild == null && rightChild == null){ if(parent.isLeft(data)){ parent.left=null; }else { parent.right=null; } return; } //如果左子树是空，则直接把右子节点挂到父节点上去 if(leftChild == null){ if(parent.isLeft(data)){ parent.left = rightChild; }else { parent.right = rightChild; } } //如果右子树是空，则直接把左子节点挂到父节点上去 if(rightChild == null){ if(parent.isLeft(data)){ parent.left = leftChild; }else { parent.right = leftChild; } } //既有左儿子，又有右儿子 //先找到右侧最左边的节点 TreeNode[] LeftmostSubtree = this.searchLeftmostSubtree(rightChild,null); if(parent.isLeft(data)){ //最左子节点 挂在 要删除节点的父节点下 parent.left = LeftmostSubtree[1]; }else{ parent.right = LeftmostSubtree[1]; } //最左子节点 的右儿子 上位替换自己 LeftmostSubtree[0].left = LeftmostSubtree[1].right; //最左子节点 替换 要删除的节点 LeftmostSubtree[1].left = delNode.left; LeftmostSubtree[1].right = delNode.right; } public static void main(String[] args) { /*Set<Integer> datas = new LinkedHashSet<>(); for(int i = 0;i<30;i++){ int dd = (int)(Math.random() * 100); if(!datas.contains(dd)){ datas.add(dd); } } System.out.println(new Gson().toJson(datas));*/ int[] datas = new int[]{50,81,31,33,12,22,92,95,67,18,85,98,84,91,15,86,89,59,30,37,83,36,4,74,49,42,7,96}; BinaryTree binaryTree = new BinaryTree(); TreeNode treeNode = null; for(int data : datas){ treeNode = binaryTree.insert(treeNode,data); } System.out.println(new Gson().toJson(treeNode)); List<Integer> preList = new ArrayList<>(); binaryTree.preorder(treeNode,preList); System.out.println("前序遍历："+new Gson().toJson(preList)); List<Integer> inList = new ArrayList<>(); binaryTree.inorder(treeNode,inList); System.out.println("中序遍历："+new Gson().toJson(inList)); List<Integer> postList = new ArrayList<>(); binaryTree.postorder(treeNode,postList); System.out.println("后序遍历："+new Gson().toJson(postList)); TreeNode[] searchNode = binaryTree.searchParent(treeNode,null,67); System.out.println("查询59节点："+new Gson().toJson(searchNode)); binaryTree.delete(treeNode,85); System.out.println("删除节点："+new Gson().toJson(treeNode)); } } |
转载请注明：刘召考的博客 » 二叉搜索树的CRUD的代码实现