李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--二叉排序树
Leefs
2020-02-16 PM
2351℃
0条
# 数据结构和算法学习--二叉排序树 ### 一、二叉排序树介绍 二叉排序树:BST(Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。 特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点 比如针对前面的数据(7,3,10,12,5,1,9),对应的二叉排序树为: ![35.二叉排序树01.png][1] ### 二、二叉排序树创建和遍历 一个数组创建成对应的二叉排序树,并使用中序遍历二叉排序树,比如:数组为Array(7,3,10,12,5,1,9),创建对应的二叉排序树为: ![35.二叉排序树02.png][2] ### 三、二叉排序树的删除 二叉排序树的删除情况比较复杂,有下面三种情况需要考虑 (1)删除叶子节点(比如:2,5,9,12) (2)删除只有一颗子树的节点(比如:1) (3)删除有两颗子树的节点(比如:7,3,10) ![35.二叉排序树03.png][3] **思路分析:** 第一种情况:**删除叶子节点(比如:2,5,9,12)** 思路: (1)需求先去找到要删除的结点`targetNode` (2)找到`targetNode`的父结点parent (3)确定`targetNode`是parent的左子结点 还是右子结点 (4)根据前面的情况来对应删除 左子结点 parent.left = null; 右子结点 parent.right = null; 第二种情况:**删除只有一颗子树的节点 比如 1** 思路: (1)需求先去找到要删除的结点 `targetNode` (2)找到`targetNode`的父结点parent (3)确定targetNode的子节点是左子结点还是右子节点 (4)targetNode是parent的左子结点还是右子节点 (5)如果targetNode有左子结点 5.1 如果targetNode是parent的左子结点 `parent.left=targetNode.left;` 5.2 如果targetNode是parent的右子节点 `parent.right=targetNode.left;` (6)如果targetNode有右子结点 6.1 如果targetNode是parent的左子结点 `parent.left=targetNode.right;` 6.2 如果targetNode是parent的右子节点 `parent.right=targetNode.right;` 情况三:**删除有两颗子树的节点(比如:7,3,10)** 思路 (1)需求先去找到要删除的结点 targetNode (2)找到targetNode的父结点parent (3)从targetNode的右子树找到最小的结点 (4)用一个临时变量,将最小结点的值保存temp=11 (5)删除该最小结点 (6)targetNode.value=temp **代码实现** ```java public class BinarySortTreeDemo { public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9, 2}; BinarySortTree binarySortTree = new BinarySortTree(); //循环的添加结点到二叉排序树 for(int i = 0; i< arr.length; i++) { binarySortTree.add(new Node(arr[i])); } //中序遍历二叉排序树 System.out.println("中序遍历二叉排序树~"); binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12 //测试一下删除叶子结点 binarySortTree.delNode(12); binarySortTree.delNode(5); binarySortTree.delNode(10); binarySortTree.delNode(2); binarySortTree.delNode(3); binarySortTree.delNode(9); binarySortTree.delNode(1); binarySortTree.delNode(7); System.out.println("root=" + binarySortTree.getRoot()); System.out.println("删除结点后"); binarySortTree.infixOrder(); } } //创建二叉排序树 class BinarySortTree { private Node root; public Node getRoot() { return root; } //查找要删除的结点 public Node search(int value) { if(root == null) { return null; } else { return root.search(value); } } //查找父结点 public Node searchParent(int value) { if(root == null) { return null; } else { return root.searchParent(value); } } //编写方法: //1. 返回的 以node 为根结点的二叉排序树的最小结点的值 //2. 删除node 为根结点的二叉排序树的最小结点 /** * * @param node 传入的结点(当做二叉排序树的根结点) * @return 返回的 以node 为根结点的二叉排序树的最小结点的值 */ public int delRightTreeMin(Node node) { Node target = node; //循环的查找左子节点,就会找到最小值 while(target.left != null) { target = target.left; } //这时 target就指向了最小结点 //删除最小结点 delNode(target.value); return target.value; } //删除结点 public void delNode(int value) { if(root == null) { return; }else { //1.需求先去找到要删除的结点 targetNode Node targetNode = search(value); //如果没有找到要删除的结点 if(targetNode == null) { return; } //如果我们发现当前这颗二叉排序树只有一个结点 if(root.left == null && root.right == null) { root = null; return; } //去找到targetNode的父结点 Node parent = searchParent(value); //如果要删除的结点是叶子结点 if(targetNode.left == null && targetNode.right == null) { //判断targetNode 是父结点的左子结点,还是右子结点 if(parent.left != null && parent.left.value == value) { //是左子结点 parent.left = null; } else if (parent.right != null && parent.right.value == value) {//是由子结点 parent.right = null; } } else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点 int minVal = delRightTreeMin(targetNode.right); targetNode.value = minVal; } else { // 删除只有一颗子树的结点 //如果要删除的结点有左子结点 if(targetNode.left != null) { if(parent != null) { //如果 targetNode 是 parent 的左子结点 if(parent.left.value == value) { parent.left = targetNode.left; } else { // targetNode 是 parent 的右子结点 parent.right = targetNode.left; } } else { root = targetNode.left; } } else { //如果要删除的结点有右子结点 if(parent != null) { //如果 targetNode 是 parent 的左子结点 if(parent.left.value == value) { parent.left = targetNode.right; } else { //如果 targetNode 是 parent 的右子结点 parent.right = targetNode.right; } } else { root = targetNode.right; } } } } } //添加结点的方法 public void add(Node node) { if(root == null) { root = node;//如果root为空则直接让root指向node } else { root.add(node); } } //中序遍历 public void infixOrder() { if(root != null) { root.infixOrder(); } else { System.out.println("二叉排序树为空,不能遍历"); } } } //创建Node结点 class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } //查找要删除的结点 /** * * @param value 希望删除的结点的值 * @return 如果找到返回该结点,否则返回null */ public Node search(int value) { if(value == this.value) { //找到就是该结点 return this; } else if(value < this.value) {//如果查找的值小于当前结点,向左子树递归查找 //如果左子结点为空 if(this.left == null) { return null; } return this.left.search(value); } else { //如果查找的值不小于当前结点,向右子树递归查找 if(this.right == null) { return null; } return this.right.search(value); } } //查找要删除结点的父结点 /** * * @param value 要找到的结点的值 * @return 返回的是要删除的结点的父结点,如果没有就返回null */ public Node searchParent(int value) { //如果当前结点就是要删除的结点的父结点,就返回 if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) { return this; } else { //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空 if(value < this.value && this.left != null) { return this.left.searchParent(value); //向左子树递归查找 } else if (value >= this.value && this.right != null) { return this.right.searchParent(value); //向右子树递归查找 } else { return null; // 没有找到父结点 } } } @Override public String toString() { return "Node [value=" + value + "]"; } //添加结点的方法 //递归的形式添加结点,注意需要满足二叉排序树的要求 public void add(Node node) { if(node == null) { return; } //判断传入的结点的值,和当前子树的根结点的值关系 if(node.value < this.value) { //如果当前结点左子结点为null if(this.left == null) { this.left = node; } else { //递归的向左子树添加 this.left.add(node); } } else { //添加的结点的值大于 当前结点的值 if(this.right == null) { this.right = node; } else { //递归的向右子树添加 this.right.add(node); } } } //中序遍历 public void infixOrder() { if(this.left != null) { this.left.infixOrder(); } System.out.println(this); if(this.right != null) { this.right.infixOrder(); } } } ``` [1]: https://lilinchao.com/usr/uploads/2020/02/1349693663.png [2]: https://lilinchao.com/usr/uploads/2020/02/2008199356.png [3]: https://lilinchao.com/usr/uploads/2020/02/927245915.png
标签:
数据结构和算法
,
二叉树
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/615.html
上一篇
LeetCode-2 两数相加
下一篇
LeetCode-3 无重复字符的最长子串
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
48
NLP
8
标签云
Golang
随笔
HDFS
ClickHouse
Azkaban
机器学习
BurpSuite
Flume
JavaScript
Typora
排序
前端
gorm
JavaSE
递归
Yarn
Kafka
Hive
Java工具类
Redis
Linux
GET和POST
Python
Hbase
Kibana
序列化和反序列化
ajax
Spring
Sentinel
Tomcat
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞