掉一根头发，搞定二叉排序(搜索)树

青旅半醒 2022-11-16 08:04 134阅读 0赞

> 文章已收录在 [数据结构与算法学习仓库][Link 1]

### 前言 ###

> 前面介绍学习的大多是线性表相关的内容，把指针搞懂后其实也没有什么难度，规则相对是简单的，后面会讲解一些比较常见的数据结构，用多图的方式让大家更容易吸收。

在数据结构与算法中，树是一个比较大的家族，家族中有很多厉害的成员，这些成员有二叉树和多叉树(例如B+树等)，而二叉树的大家族中，二叉搜索树(又称二叉排序树)是最最基础的，在这基础上才能继续拓展学习AVL(二叉平衡树)、红黑树等知识。

对于二叉排序树而言，本章重点关注其实现方式以及插入、删除步骤流程，我们会手写一个二叉排序树，二叉树遍历部分的内容比较多会单独详细讲解。

### 什么是树 ###

树是一种数据结构，它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。  
![image-20210405113134193][]

树是递归的，将树的任何一个节点以及节点下的节点都能组合成一个新的树，所以树的很多问题都是使用递归去完成。

**根节点：** 最上面的那个节点(root)，根节点没有父节点，只有子节点（0个或多个都可以）

**层数：** 一般认为根节点是第1层(有的也说第0层)，而**树的高度**就是层数最高(上图层数开始为1)节点的层数

**节点关系:**

*  父节点：连接该节点的上一层节点,
 *  孩子节点: 和父节点对应，上下关系。而祖先节点是父节点的父节点(或者祖先）节点。
 *  兄弟节点：拥有同一个父节点的节点们！

**节点的度:** 就是节点拥有**孩子节点**的个数(是直接连接的孩子不是子孙).

**树的度:** 就是所有节点中最大 **(节点的度)**。同时，如果度大于0的节点是分支节点,度等于0的节点是叶子节点（没有子孙）。

**相关性质**：

![image-20210402001215174][]

### 二叉树 ###

二叉树是一树的一种，但应用比较多，所以需要深入学习，**二叉树的每个节点最多只有两个子节点**(但不一定非得要有两个节点)。

**二叉树与度为2的树的**区别：  
1、度为2的的树必须有三个节点以上(否则就不叫度为二了，一定要先存在)，二叉树可以为空。  
2、二叉树的度不一定为2,比如**斜树**。  
3、二叉树有左右节点区分，而度为2的树没有左右节点的区分。

**几种特殊二叉树：**

**满二叉树**：高度为n的满二叉树有(2^n) -1个节点  
![满二叉树][db88591de1680813bdec1bae2eb1a6dc.png]

**完全二叉树**：上面一层全部满，最下一层从左到右顺序排列  
![完全二叉树][e5819847c73d55dbf1ed140f6c5fd8e8.png]  
二叉排序树：树按照一定规则插入排序(本文详解)。  
平衡二叉树：树上任意节点左子树和右子树深度差距不超过1(后文详解).

**二叉树性质：**

1、二叉树有用树的性质

2、非空二叉树叶子节点数=度为2的节点数+1.本来一个节点如果度为1.那么一直延续就一个叶子，但如果出现一个度为2除了延续原来的一个节点，会多出一个节点需要维系。所以到最后会多出一个叶子。

3、非空第i层最多有2^(i-1)个节点。

4、高为h的树最多有(2^h)-1个节点(等比求和)。

二叉树一般用链式存储，这样内存利用更高，但二叉树也可以用数组存储的(经常会遇到)，各个节点对应的下标是可以计算出来的，就拿一个完全二叉树若从左往右，从上到下编号如图：  
![二叉树节点位置对应关系][56980b2dcf6f8dd9e8a8e8c7720dffbe.png]

### 二叉排序(搜索)树 ###

#### 概念 ####

前面铺垫那么多，咱们言归正传，详细讲解并实现一个二叉排序树，二叉搜索树拥有二叉树的性质，同时有一些自己的规则：

首先要了解二叉排序树的规则：**从任意节点开始，节点左侧节点值总比节点右侧值要小。**

例如一个二叉排序树依次插入`15，6，23，7，4，71，5，50`会形成下图顺序  
![一个二叉排序树][1f59a2ad5419f6b47c4e788ff96c60e9.png]

#### 构造 ####

二叉排序树是由若干节点(node)构成的，对于node需要这些属性：left，right，和value。其中left和right是左右指针指向左右孩子子树，而value是储存的数据，这里用int 类型。

`node`类构造为：

class node {
        //结点
    	public int value;
    	public node left;
    	public node right;
    	public node()
    	{
        
    	}
    	public node(int value)
    	{
        
    		this.value=value;
    		this.left=null;
    		this.right=null;
    	}
    	public node(int value,node l,node r)
    	{
        
    		this.value=value;
    		this.left=l;
    		this.right=r;
    	}			
    }

既然节点构造好了，那么就需要节点等其他信息构造成树，有了链表构造经验，很容易得知一棵树最主要的还是`root`根节点。  
所以树的构造为：

public class BinarySortTree {
        
    	node root;//根
    	public BinarySortTree()
    	{
        root=null;}
    	public void makeEmpty()//变空
    	{
        root=null;}
    	public boolean isEmpty()//查看是否为空
    	{
        return root==null;}
    	//各种方法
    }

![image-20210405120743003][]

#### 主要方法 ####

既然已经构造好一棵树，那么就需要实现主要的方法,因为二叉排序树中**每个节点都能看作一棵树**。所以我们创建方法的是时候加上节点参数(方便一些递归调用)

#### findmax(),findmin() ####

**findmin()找到最小节点：**

因为所有节点的最小都是往左插入，所以只需要找到最左侧的返回即可，具体实现可使用递归也可非递归while循环。

**findmax()找到最大节点：**

因为所有节点大的都是往右面插入，所以只需要找到最右侧的返回即可，实现方法与findmin()方法一致。

**代码使用递归函数**

public node findmin(node t)//查找最小返回值是node，调用查看结果时需要.value
    {
        
    	if(t==null) {
        return null;}
    	else if(t.left==null) {
        return t;}
    	else return(findmin(t.left));	
    }
    public node findmax(node t)//查找最大
    {
        
    	if(t==null) {
        return null;}
    	else if(t.right==null) {
        return t;}
    	else return(findmax(t.right));	
    }

![查找过程][a974a2e2df669242bc4d0a6b3e1581e0.png]

#### isContains(int x) ####

这里的意思是查找二叉查找树中是否存在值为x的节点。

在具体实现上，根据二叉排序树左侧更小，右侧更大的性质进行往下查找，如果找到值为x的节点则返回true，如果找不到就返回false，当然实现上可以采用递归或者非递归，我这里使用非递归的方式。

public boolean isContains(int x)//是否存在
    {
        
    	node current=root;
    	if(root==null) {
        return false;}
    	while(current.value!=x&&current!=null) 
    	{
        
    		if(x<current.value) {
        current=current.left;}
    		if(x>current.value) {
        current=current.right;}
    		if(current==null) {
        return false;}//在里面判断如果超直接返回
    	}
    	//如果在这个位置判断是否为空会导致current.value不存在报错
    	 if(current.value==x) {
        return true;}		
    	return false;		
    }

#### insert(int x) ####

插入的思想和前面`isContains(int x)`类似，找到自己的位置(空位置)插入。

但是具体实现上有需要注意的地方，**我们要到待插入位置上一层节点**，你可能会疑问为什么不直接找到最后一个空，然后将current赋值过去`current=new node(x)`，这样的化current就相当于指向一个new node(x)节点，和原来树就脱离关系(原树相当于没有任何操作)，所以要提前通过父节点判定是否为空找到位置，找到合适位置通过父节点的left或者right节点指向新创建的节点才能完成插入的操作。

public node insert(int x)// 插入 t是root的引用
    {
        
    	node current = root;
    	if (root == null) {
        
    		root = new node(x);
    		return root;
    	}
    	while (current != null) {
        
    		if (x < current.value) {
        
    			if (current.left == null) {
        
    				return current.left = new node(x);}
    			else current = current.left;}
    	    else if (x > current.value) {
        
    			if (current.right == null) {
        
    				return current.right = new node(x);}
    			else current = current.right;
    		}
    	}
    	return current;//其中用不到
    }

比如说上面树插入值为51的节点。  
![插入值为51的节点][51]

#### delete(int x) ####

删除操作算是一个相对较难理解的操作了，因为待删除的点可能在不同位置所以具体处理的方式也不同，如果是叶子即可可直接删除，有一个孩子节点用子节点替换即可，有两个子节点的就要先找到值距离待删除节点最近的点(左子树最大点或者右子树最小点)，将值替换掉然后递归操作在子树中删除已经替换的节点，当然没具体分析可以看下面：

**删除的节点没有子孙:**

这种情况不需要考虑，直接删除即可(`节点=null`即可)(图中红色点均满足这种方式)。  
![待删除节点为叶子节点][ff545b28213b0a60548bf6ce0a04f2d4.png]

**一个子节点为空：**

此种情况也很容易，直接将删除点的子节点放到被删除位置即可。  
![待删除节点有1个孩子][1]

**左右节点均不空**

左右孩子节点都不为空这种情况是相对比较复杂的，因为不能直接用其中一个孩子节点替代当前节点(放不下，如果孩子节点也有两个孩子那么有一个节点无法放，例如拿下面71节点替代)  
![待删除节点有两个孩子][cf2ce6083125dcf37b977b75c12d22d1.png]

如果拿19或者71节点填补。虽然可以保证部分侧大于小于该节点，但是会引起合并的混乱.比如你若用71替代23节点。那么你需要考虑三个节点`(19,50,75)`之间如何处理，还要考虑他们是否满，是否有子女，这是个复杂的过程，不适合考虑。

所以，**我们要分析我们要的这个点的属性**：能够**保证该点在这个位置仍满足二叉搜索树的性质**(找到值最近的)，那么子树中哪个节点满足这样的关系呢？

**左子树中最右侧节点**或者**右子树中最左侧节点**都满足，我们可以选一个节点将待删除节点值替换掉(这里替换成左子树最右侧节点)。

这个点替换之后该怎么办呢？很简单啊，二叉树用**递归思路**解决问题，再次调用删除函数在左子树中删除替换的节点即可。

![先替换值再递归在子树中删除18节点][18]

这里演示是选取左子树最大节点(最右侧)替代，当然使用右子树最小节点也能满足在这待删除的大小关系，原理一致。整个删除算法流程为：  
![删除流程][a9dbdc72fa3686dc0745516862be7784.png]

这部分操作的代码为：

public node remove(int x, node t)// 删除节点
    {
        
      if (t == null) {
        
        return null;
      }
      if (x < t.value) {
        
        t.left = remove(x, t.left);
      } else if (x > t.value) {
        
        t.right = remove(x, t.right);
      } else if (t.left != null && t.right != null)// 左右节点均不空
      {
        
        t.value = findmin(t.right).value;// 找到右侧最小值替代
        t.right = remove(t.value, t.right);
      } else // 左右单空或者左右都空
      {
        
        if (t.left == null && t.right == null) {
        
          t = null;
        } else if (t.right != null) {
        
          t = t.right;
        } else if (t.left != null) {
        
          t = t.left;
        }
        return t;
      }
      return t;
    }

#### 完整代码 ####

这个完整代码是笔者在大三时候写的，可能有不少疏漏或者不规范的地方，仅供学习参考，如有疏漏错误还请指正。

二叉排序树完整代码为：

package 二叉树;
    
    import java.util.ArrayDeque;
    import java.util.Queue;
    import java.util.Stack;
    
    public class BinarySortTree {
        
    	class node {
        // 结点
    		public int value;
    		public node left;
    		public node right;
    
    		public node() {
        
    		}
    
    		public node(int value) {
        
    			this.value = value;
    			this.left = null;
    			this.right = null;
    		}
    
    		public node(int value, node l, node r) {
        
    			this.value = value;
    			this.left = l;
    			this.right = r;
    		}
    	}
    
    	node root;// 根
    
    	public BinarySortTree() {
        
    		root = null;
    	}
    
    	public void makeEmpty()// 变空
    	{
        
    		root = null;
    	}
    
    	public boolean isEmpty()// 查看是否为空
    	{
        
    		return root == null;
    	}
    
    	public node findmin(node t)// 查找最小返回值是node，调用查看结果时需要.value
    	{
        
    		if (t == null) {
        
    			return null;
    		} else if (t.left == null) {
        
    			return t;
    		} else
    			return (findmin(t.left));
    	}
    
    	public node findmax(node t)// 查找最大
    	{
        
    		if (t == null) {
        
    			return null;
    		} else if (t.right == null) {
        
    			return t;
    		} else
    			return (findmax(t.right));
    	}
    
    	public boolean isContains(int x)// 是否存在
    	{
        
    		node current = root;
    		if (root == null) {
        
    			return false;
    		}
    		while (current.value != x && current != null) {
        
    			if (x < current.value) {
        
    				current = current.left;
    			}
    			if (x > current.value) {
        
    				current = current.right;
    			}
    			if (current == null) {
        
    				return false;
    			} // 在里面判断如果超直接返回
    		}
    		// 如果在这个位置判断是否为空会导致current.value不存在报错
    		if (current.value == x) {
        
    			return true;
    		}
    		return false;
    	}
    
    	public node insert(int x)// 插入 t是root的引用
    	{
        
    		node current = root;
    		if (root == null) {
        
    			root = new node(x);
    			return root;
    		}
    		while (current != null) {
        
    			if (x < current.value) {
        
    				if (current.left == null) {
        
    					return current.left = new node(x);}
    				else current = current.left;}
    		    else if (x > current.value) {
        
    				if (current.right == null) {
        
    					return current.right = new node(x);}
    				else current = current.right;
    			}
    		}
    		return current;//其中用不到
    	}
    
    	public node remove(int x, node t)// 删除节点
    	{
        
    		if (t == null) {
        
    			return null;
    		}
    		if (x < t.value) {
        
    			t.left = remove(x, t.left);
    		} else if (x > t.value) {
        
    			t.right = remove(x, t.right);
    		} else if (t.left != null && t.right != null)// 左右节点均不空
    		{
        
    			t.value = findmin(t.right).value;// 找到右侧最小值替代
    			t.right = remove(t.value, t.right);
    		} else // 左右单空或者左右都空
    		{
        
    			if (t.left == null && t.right == null) {
        
    				t = null;
    			} else if (t.right != null) {
        
    				t = t.right;
    			} else if (t.left != null) {
        
    				t = t.left;
    			}
    			return t;
    		}
    		return t;
    	}
    }

### 结语 ###

这里我们学习了解了树、二叉树、以及二叉搜素树，对于二叉搜素树插入查找比较容易理解，但是实现的时候要注意函数参数的引用等等。

偏有难度的是二叉树的删除，利用一个递归的思想，分类讨论待删除情况，要找到特殊情况和普通情况，递归一定程度也是问题的转化(**转成自己相同问题，作用域减小**)需要思考。

下面还会介绍二叉树的三序遍历(**递归和非递归**)和层序遍历。这些都是比较经典热门的问题需要深入了解。

如果看了本文觉得有收获欢迎 **点赞、收藏、分享**一波，也欢迎加我v信好友(**q1315426911**)一起学习交流，我也创了一个力扣打卡群，里面很多热情的伙伴希望一起进步！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_16_color_FFFFFF_t_70]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[image-20210405113134193]: /images/20221022/e95bf4b0698740b896e4c2228da19d05.png
[image-20210402001215174]: /images/20221022/27bf65fcf20d40edad24ea7c1caaf9ec.png
[db88591de1680813bdec1bae2eb1a6dc.png]: /images/20221022/b2170d832bee4bfc97b8e78f93bb2a1d.png
[e5819847c73d55dbf1ed140f6c5fd8e8.png]: /images/20221022/841465ffe4274132809e15ec5e7c86a2.png
[56980b2dcf6f8dd9e8a8e8c7720dffbe.png]: /images/20221022/4eefdb755cf44a7c81e682b107dcbc9d.png
[1f59a2ad5419f6b47c4e788ff96c60e9.png]: /images/20221022/bee88f493f7245dda7e4ebd1ac9e1702.png
[image-20210405120743003]: /images/20221022/327e75b35f2149baac20bef559d8501c.png
[a974a2e2df669242bc4d0a6b3e1581e0.png]: /images/20221022/0eb7d7b1373645cdb03378062f763809.png
[51]: /images/20221022/a7e4dede73e94104b70ca7ecc4c7a2ba.png
[ff545b28213b0a60548bf6ce0a04f2d4.png]: /images/20221022/dd6e89e73e8f4d2d84c4c66a03f6750c.png
[1]: /images/20221022/61f6868f2c13444988489b18e7d8bc78.png
[cf2ce6083125dcf37b977b75c12d22d1.png]: /images/20221022/4c80a8e6966d43d5ae787d389b991b97.png
[18]: /images/20221022/f19e5ddcbd344b28af77e9cde835e92b.png
[a9dbdc72fa3686dc0745516862be7784.png]: /images/20221022/a04caf24973f401cb03aa60246c12a72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_16_color_FFFFFF_t_70]: /images/20221022/9bcbe2c71992404bb9c710c018856ca0.png