二叉查找树

二叉查找树(Binary Search Tree),简写BST,是满足某些条件的特殊二叉树。任何一个节点的左子树上的点,都必须小于当前节点。任何一个节点的右子树上的点,都必须大于当前节点。任何一棵子树,也都满足上面两个条件。另外二叉查找树中,是不存在重复节点的。

p001801_BSTSearch

上图中的二叉查找树,我们从Root节点3开始看,它的左子树(1,2) 和右子树(6,4,9,7)分别满足条件,左子树上的点,都小于当前节点,右子树上的点,都大于当前节点。

继续,我们以6作为起点,来看一下这棵子树,6的左子树(4),右子树(9,7)也满足上面两条规则。

整棵树中,任何一个点下面的子树,都满足上面提到的两条规则。你现在是不是对Binary Search Tree已经有一个大概的形象概念了。

为什么叫做 Binary Search Tree呢?

因为在BST中搜索一个值是非常简单和高效的。

p001802_BST-Delete1

看上面的树,假设要搜索7这个节点。首先从Root节点出发,我们知道7大于3,所以会走到右子树6,然后因为7也大于6,所以会继续往右子树走,到了9,因为7小于9,所以会向左子树走,走到7,发现7等于7,所以找到要搜索的节点。

二叉树的一些性质

  • 将任何一个点看作Root节点,则这个点的左子树也是 Binary Search Tree
  • 将任何一个点看作Root节点,则这个点的右子树也是 Binary Search Tree
  • Binary Search Tree中的最小节点,一定是整棵树中最左下的叶子节点(从Root开始一直顺着左子树往下走,直到某一个点没有左子节点,则这个点就是最小的)
  • Binary Search Tree中的最大节点,一定是整棵树中最右下的叶子节点(从Root开始一直顺着右子树往下走,直到某一个点没有右子节点,则这个点就是最大的)

怎样构建和插入节点

向BST中插入一个节点,也是一个构建的过程,和上面的搜索思路基本一样。首先从Root开始,如果Root点为空,则直接构建Root点。如果Root点不为空,则要判断要插入的值,比Root点的值大还是小,如果小,则往左子树走,如果大,则往右子树走。直到走到某一个点,我们称为点X,发现要插入的值,小于那个点X的值,并且点X没有左子树,则要插入的点作为X的左子节点。或者,要插入的点大于X,并且X没有右子树,则要插入的点作为X的右子节点。

下面是代码实现(为了方便后面的删除逻辑,我们每一个点,包含了指向左子树,右子树,以及父节点的引用)

// 这里先定义出节点的结构
class Node
{
public int data;
public Node parent;
public Node left;
public Node right;

public Node(int _data)
{
this.data = _data;
}
}
// 定义二叉搜索树结构
class BST
{
private Node root;

// 这个函数是 private 的,递归调用,插入节点
private Node RecursionInsert(Node node, int data)
{
if (node == null)
{
return new Node(data);
}

if (data < node.data)
{
node.left = RecursionInsert(node.left, data);
node.left.parent = node;
}
else if (data > node.data)
{
node.right = RecursionInsert(node.right, data);
node.right.parent = node;
}

return node;
}

// 对外开放的 插入 接口
public void Insert(int data)
{
if (root == null)
{
root = RecursionInsert(root, data);
}
else
{
RecursionInsert(root, data);
}
}

// 按层序打印二叉树
public void LevelOrderTraversal()
{
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);

while (q.Count > 0)
{
Node currNode = q.Dequeue();

if (currNode.left != null)
{
q.Enqueue(currNode.left);
}

if (currNode.right != null)
{
q.Enqueue(currNode.right);
}
// 括号里面是父节点的值
string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");
Debug.Log(msg);
}
}
}
// 创建一个二叉搜索树
class Program
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */

static void Main(string[] args)
{
BST bst = new BST();
bst.Insert(50);
bst.Insert(30);
bst.Insert(20);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);

bst.LevelOrderTraversal();
}
}

上面的代码,首先定义了每一个 Node 节点的数据结构,然后定义了二叉查找树的结构类,最后是C#调用BST的插入和打印方法。插入节点这里使用了递归的机结构,还可以使用非递归,循环的形式去插入。

从最简单的开始,删除一个节点

从 BST 中删除节点,是相比来说比较复杂的,复杂,也只是相对于插入来说。只要理清几种不同的情况,也就不复杂了。看过很多教程,一上来就是罗列各个情况,然后上代码展示,如果是第一次学习 BST,可能会有一点抽象。我们先不考虑代码怎么实现,先从语言上把这个事情讲明白,最后再看代码。

从 BST 中删除节点其实很容易,只要改变一下指针就可以了,重点是,删除了一个节点后,还要让整棵 BST 依然保持一个正确的结构,这就是我们要做的。一切从最简单开始。

p001803_BST-Delete2

上面的图中,我们要删除一个叶子节点,就是左边的数据为3的那个节点。这个节点的父节点是4,我们只需要将4这个节点中指向左子树的指针设置为空,就可以了。这是很容易理解的。而删除右边的叶子节点,也是一样的。就像下面的图。

我们删除18这个节点,只需要将13这个节点中指向右子树的指针设置为空,即可。

上面说的,就是删除操作中最简单的一种情况,删除叶子节点。还有一个很重要的点要注意,在删除的时候,要判断要删除的节点是不是 Root 节点,也就是说,整棵树只有一个节点的情况,这样的话还需要将 Root 节点设为空。Root节点的父节点,是永远为空的。

注意: 记住,现在不要考虑代码实现的问题,一定要先理解思路,文章的最后,会上代码的。

关于节点删除,加大一点点难度

接下来我们加大一点点难度。看下面的图 (可以忽略图中的红色字,只看树的节点结构)

p001804_BST-Delete3

我们要删除左边图中5这个节点,而5这个节点只拥有一个子树,就是左子树。而5的父节点是2,它是2的右子树。我们要删除5,只需要将2的右子树,指向5的子树就可以 (这里其实不太关心5的子树是左子树还是右子树)。简单来说,就是将2原本指向5的指针,改为指向5的子树,即可。就是右边图的样子。

我们刚才删除的5节点,只有左子树,再看一个要删除的节点只有右子树的情况。

p001805_BST-Delete4

上面的图中, 我们要删除3这个节点,而这个节点只有右子树。3的父亲节点是2,所以,我们只需要将2原本指向3节点的指针,改为指向3的子树即可。就像右边的图那样。

不要着急,慢慢体会一下。在上面两种情况没有彻底理解思路之前,先不要往下看,否则可能会更困惑。

注意: 因为我们的 Node 结构中加入了一个指向父节点的指针,所以在删除节点的时候,还要注意更新某些节点的 parent 指针指向。

更复杂的情况,先聊一下后继节点

如果上面只是小打小闹,那接下来,就是直面恐惧,噢不,直面复杂时刻啦,哈哈哈~

最复杂的一种情况,就是要删除的节点,即有左子树,又有右子树。在说这种情况怎么操作之前,我们先来说一个前提概念,叫做后继节点。一个节点的后继节点,严肃点说就是在中序遍历的时候,遍历完当前节点后,下一个要访问的节点,就是当前的节点的后继节点。好吧,通俗点来讲,就是假设在遍历一棵树时,访问完 1 号节点,如果接下来访问的是3号节点,那3号节点就是1的后继节点。

那一个点的后继节点怎么找呢?这个就很简单了。假设我们要找节点 A 的后继节点,那就是从 A 这个点的右子树开始,一路向左走,走到某一个节点没有左子树可以往下走了,那这个节点,就是 A 的后继节点 (注意,这个后继节点有可能是叶子节点,也有可能不是)。看下面的图。

p001806_BST-Delete5

我们先看左边部分的图,我们要找节点 9 的后继节点。按上面的规则,从节点 9 的右子树 15 开始,依次往左走,先到达 15 判断一下是否可以走,可以,我们走到 13,再判断一下是否可以继续往左走,可以,走到 11,然后再看是否可以继续往左走,发现不可以了,那 11 就是节点 9 的后继节点。

再看右边部分的图,我们要找节点 6 的后继节点。按上面的规则从右子树 11 开始,判断是否可以往左走,可以,走到 8,再判断是一下是否可以继续往左走,发现 8 已经没有左子树可以往下走了,所以 8 就是节点 6 的后继节点。

最后一种删除节点的情况

理解了后继节点,就可以来说最后一种,也是最复杂的一种删除节点的情况了。就是要删除的节点,即有左子树,又有右子树。操作的流程是这样的。假设我们要删除的节点是 A,第一步,我们要找到 A 的后继节点。第二步,用 A 的后继节点数据,替换要删除的节点 A 的数据。第三步,删除后继节点。(因为后继节点要么是叶子节点,要么只有右子树,所以删除比较简单,就按之前聊过的删除方法即可)。下面用示例解释

p001807_BST-Delete6

上图中,从第一个图开始看,我们要删除数据为 9 的节点。第一步,将要删除的节点使用一个指针指向。第二步,看第二个图,找到 9 节点的后继节点,也就是 11。第三步,看第三张图,用后继节点的数据,替换要删除的节点的数据,也就是用 11 替换 9。第四步,也就是最后一个图,删除后继节点 11。到此,删除操作完成。

接下来再看一个示例

p001808_BST-Delete7

上图中,我们要删除节点 6,还是先找到 6 的后继节点 8,然后用节点 8 的数据,替换我们要删除的节点 6 的数据(第三个小图)。接下来就是删除后继节点 8,这里要注意,我们跟着箭头的方向,看第四个小图。在删除后继节点 8 时,我们发现节点 8 不是叶子节点,而是有右子树,所以我们需要将节点 8 的父节点,原本指向 8 的指针,改为指向 8 的右子树。也就是上图中将节点 11 的左指针,改为指向节点 9,然后就是最后一个小图的情况。(因为我们的 Node 结构中拥有 parent 指针,所以要记得把节点 9 的parent 指针从原来指向 8 改为现在指向 9)。到此,删除节点结束。

接下来,我们展示完整的代码

using System;
using System.Collections.Generic;

static class Debug
{
public static void Log(string msg)
{
Console.WriteLine(msg);
}
}

class Node
{
public int data;
public Node parent;
public Node left;
public Node right;

public Node(int _data)
{
this.data = _data;
Console.WriteLine("Insert: " + this.data);
}
}

class BST
{
private Node root;


private Node RecursionInsert(Node node, int data)
{
if (node == null)
{
return new Node(data);
}

if (data < node.data)
{
node.left = RecursionInsert(node.left, data);
node.left.parent = node;
}
else if (data > node.data)
{
node.right = RecursionInsert(node.right, data);
node.right.parent = node;
}

return node;
}

// 插入一个数据
public void Insert(int data)
{
if (root == null)
{
root = RecursionInsert(root, data);
}
else
{
RecursionInsert(root, data);
}
}

// 删除节点
public void DeleteNode(int data)
{
Node delNode = root;

// 首先要找到待删除的节点
while (delNode != null)
{
if (delNode.data == data)
{
break;
}

if (data < delNode.data)
{
delNode = delNode.left;
}
else if (data > delNode.data)
{
delNode = delNode.right;
}
}

if (delNode == null)
{
Debug.Log("Not found " + data);
return;
}

// 要删除的节点即没有左子树,也没有右子树,是叶子节点,或者是 Root 节点
if (delNode.left == null && delNode.right == null)
{
Node parent = delNode.parent;
if (parent == null)
{
root = null;
}
else
{
if (parent.left == delNode)
{
parent.left = null;
}
else
{
parent.right = null;
}
}
}
else if (delNode.left != null && delNode.right == null)
{
// 要删除的节点只有左子树的情况
Node parent = delNode.parent;
Node child = delNode.left;
if (parent == null)
{
root = child;
root.parent = null;
}
else
{
if (parent.left == delNode)
{
parent.left = child;
}
else
{
parent.right = child;
}
child.parent = parent;
}
}
else if (delNode.right != null && delNode.left == null)
{
// 要删除的节点只有右子树的情况
Node parent = delNode.parent;
Node child = delNode.right;

if (parent == null)
{
root = child;
root.parent = null;
}
else
{
if (parent.left == delNode)
{
parent.left = child;
}
else
{
parent.right = child;
}
child.parent = parent;
}
}
else if (delNode.left != null && delNode.right != null)
{
// 要删除的节点即有左子树,也有右子树的情况

// 首先找到后继节点
Node successorNode = FindMinimumLeftValue(delNode.right);
delNode.data = successorNode.data;

// 如果后继节点是叶子节点,则直接删除即可
if (successorNode.left == null && successorNode.right == null)
{
if (successorNode.parent.left == successorNode)
{
successorNode.parent.left = null;
}
else
{
successorNode.parent.right = null;
}
}
else
{
// 如果后继节点不是叶子节点,要将后继节点的父节点指向后继节点的子树,
// 同时,修改子树父节点的指针
Node successorChild = successorNode.left != null ? successorNode.left : successorNode.right;
Node parent = successorNode.parent;
if (parent.left == successorNode)
{
parent.left = successorChild;
}
else
{
parent.right = successorChild;
}
successorChild.parent = parent;
}
}

}

// 找到一颗子树的最小左节点
public Node FindMinimumLeftValue(Node fromNode)
{
Node opt = fromNode;
while (opt.left != null)
{
opt = opt.left;
}

return opt;
}

public void LevelOrderTraversal()
{
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);

while (q.Count > 0)
{
Node currNode = q.Dequeue();

if (currNode.left != null)
{
q.Enqueue(currNode.left);
}

if (currNode.right != null)
{
q.Enqueue(currNode.right);
}
string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");
Debug.Log(msg);
}
}
}


class Program
{

/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */

static void Main(string[] args)
{
BST bst = new BST();
bst.Insert(50);
bst.Insert(50);
bst.Insert(30);
bst.Insert(20);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);

bst.LevelOrderTraversal();

bst.DeleteNode(70);

bst.LevelOrderTraversal();

}
}

好了,终于讲完了二叉查找树最基本的知识。这篇博客内容很长,如果第一遍没读懂,也没关系,先休息一下,过段时间再读一遍,可能就会更容易理解。

Author: Moeif Studio

Permalink: http://blog.moeif.com/2019/12/26/data-structure-06-binary-search-tree/

任何技术问题,可加微信交流,微信: ifloop

搜索并关注微信公众号 [ 萌一小栈 ] 可及时订阅最新技术文章

Comments