二叉排序树的概述及实现

墨蓝 2021-09-01 04:43 241阅读 0赞

### 二叉排序树的概述及实现 ###

*  概述
 *  特点
 *   *  代码实现

# 概述 #

二叉排序树：二叉排序树也叫二叉查找树、二叉搜索树（简称：BST）对于二叉树中的任何一个非叶子节点要求左子节点比当前节点值小，右子节点比当前节点值大（一个空树也可以称为一个二叉排序树）。

# 特点 #

1.线性结构树的缺点

<table> 
 <thead> 
  <tr> 
   <th>线性结构树</th> 
   <th>特点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>顺序存储</td> 
   <td>不排序时查找困难；排序时删除困难</td> 
  </tr> 
  <tr> 
   <td>链式存储</td> 
   <td>无论是否排序查找困难</td> 
  </tr> 
 </tbody> 
</table>

2.二叉排序树的基本步骤  
例如：一个数组\[7,3,10,12,5,1,9\]

*  拿到第一个数组7，作为根节点；
 *  拿到第二数字与跟节点比较，比根节点小放在左子节点上，比根节点大放在右子节点上
 *  拿到第三个数字，若比根节点小，比右子节点小，比左子节点大，则放在左子节点的子节点的右节点上
 *  依次类推  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]

## 代码实现 ##

1.  Node.java

public class Node {
       
       int value;
       Node left;
       Node right;
       
       public Node(int value) {
       	this.value = value;
       }
       /**
        * 向二叉排序树中添加节点
        * @param node
        */
       public void add(Node node) {
       	if(node == null) {
       		return;
       	}
       	if(node.value < this.value) {
       		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);
       		}
       	}
       }
       /**
        * 中序遍历二叉树
        * @param node
        */
       public void midShow(Node node) {
       	if(node == null) {
       		return ;
       	}else {
       		midShow(node.left);
       		System.out.println(node.value);
       		midShow(node.right);
       	}
       }
       public Node search(int value) {
       	if(this.value == value) {
       		return this;
       	}else if(this.value > value) {
       		if(left == null) {
       			return null;
       		}
       		return left.search(value);
       	}else {
       		if(right == null) {
       			return null;
       		}
       		return right.search(value);
       	}
       }
       /**
        * 搜索父节点
        * @param value
        * @return
        */
       public Node searchParent(int value) {
       	if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
       		return this;
       	}else {
       		if(this.value > value && this.left != null) {
       			return this.left.searchParent(value);
       		}else if(this.value < value && this.left != null) {
       			return this.right.searchParent(value);
       		}
       		return null;
       	}
       }
    }

1.  BinarySortTree.java

public class BinarySortTree {
       
       Node root;
       /**
        * 向二叉排序树中添加节点
        * @param node
        */
       public void add(Node node) {
       	if(root == null) {
       		root = node;
       	}else {
       		root.add(node);
       	}
       }
       /**
        * 中序遍历
        * @param node
        */
       public void midShow() {
       	if(root != null) {
       		root.midShow(root);
       	}
       }
       
       /**
        * 节点的查找
        * @param value
        * @return
        */
       public  Node search(int value) {
       	if(root == null) {
       		return null;
       	}else {
       		return root.search(value);
       	}
       }
    
       /**
        * 删除节点
        */
       public  void delete(int value) {
       	if(root == null) {
       		return ;
       	}else {
       		//找到这个节点
       		Node target = search(value);
       		//如果没有这个节点
       		if(target == null) {
       			return;
       		}
       		//找它的父节点
       		Node parent = searchParent(value);
       		//要删除节点的叶子节点
       		if(target.left == null && target.right == null) {
       			//要删除的节点时左子叶节点
       			if(parent.left.value == value) {
       				parent.left = null;
       			}else {
       				parent.right = null;
       		    }
       		//要删除的节点有两个子节点的情况
       		/**
       		 * 例如：要删除7，则要找到代替他的子树节点；
       		 * 这个节点一定是在右子树中存在，我们先删除右子树中的这个最小的值（即7的替换节点）并拿到他的值
       		 * 然后放到7的位置
       		 */
       		}else if(target.left != null && target.right != null) {
       			
       			//删除右子树中值最小的节点，并获取到该节点的值
       			 int min = deleteMin(target.right);
       			//替换目标节点中的值
       			 target.value = min;
       			 
       		//要删除的节点有一个左子节点或者右子节点
       		}else {
       			//有左子节点
       			if(target.left != null) {
       				//要删除的节点时父节点的左子节点
       				if(parent.left.value == value) {
       					parent.left = target.left;
       				}else {
       					parent.right = target.left;
       				}
       			//有右子节点
       			}else {
       				//要删除的节点时父节点的右子节点
       				if(parent.left.value == value) {
       					parent.left = target.right;
       				}else {
       					parent.right = target.right;
       				}
       			}
       		}
       	}
       }
       /**
        * 删除一颗树中最小的节点
        * @param right
        * @return
        */
       private int deleteMin(Node node) {
       	Node target = node;
       	//递归循环找右子树中最小的左子节点
       	while(target.left != null) {
       		target = target.left;
       	}
       	//如果最小的左子节点存在右子节点
       	delete(target.value);
       	return target.value;
       }
       /**
        * 搜索父节点
        * @param value
        * @return
        */
       public  Node searchParent(int value) {
       	if(root == null) {
       		return null;
       	}else {
       		return root.searchParent(value);
       	}
       }
    
    }

1.  TestBinaryTree.java

public class TestBinaryTree {
    
    	public static void main(String[] args) {
    
    		int[] arr = {7,3,10,12,5,1,9};
    		//创建一个二叉排序树
    		BinarySortTree bst = new BinarySortTree();
    		//循环添加                                                                                 
    		for(int i : arr) {
    			bst.add(new Node(i));
    		}
    		//查看树中的值
    		bst.midShow();  //运行结果：1,3,5,7,9,10,12
    		
    		//查找
    		Node node1 = bst.search(10);
    		System.out.println(node1.value);  //返回10
    		
    //		Node node2 = bst.search(20);
    //		System.out.println(node2);  //结果返回 null
    		
    		
    		System.out.println("------------");
    		
    		//查找父节点
    //		Node p1 = bst.searchParent(5);
    //		System.out.println(p1.value);
    //		System.out.println("------------");
    		/**
    		 * 二叉排序树删除节点
    		 * 1.删除叶子节点
    		 * 2.删除只有一个子节点的节点
    		 * 3.删除有两个子节点的节点 
    		 */
    		//删除叶子节点
    //		bst.delete(1);
    //		bst.midShow();
    //		System.out.println("------------");
    //		//删除只有一个叶子节点的子节点
    //		bst.delete(3);
    //		bst.midShow();
    		//删除带有两个子节点的子节点
    		bst.delete(10);
    		bst.midShow();
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]: /images/20210901/4e4f6c3232b843ac9a4c794a0cc1d243.png