前文二叉查找树图解以图文相结合的方式,对二叉查找树添加、查找和删除数据结点底层原理进行解读,本文来聊聊二叉查找树添加、查找和删除数据结点算法实现,采用 C#
语言进行呈现。
首先,根据二叉树的定义,构建其结点模型,代码如下:
public class BinaryTreeNode
{
public int Data { get; set; }
public BinaryTreeNode LeftChild { get; set; }
public BinaryTreeNode RightChild { get; set; }
public BinaryTreeNode(int data)
{
Data = data;
}
}
接下来,根据二叉查找树的性质,定义其模型,分别实现二叉查找树添加、查找和删除数据结点算法。
添加数据结点
添加数据结点的逻辑:从二叉查找树的顶端结点开始寻找添加数字的位置,将要添加的数字与结点中的值(假设为 x)进行比较,小于 x 则往左移(左子树),大于 x 则往右移(右子树)。
关键实现算法如下:
public BinaryTreeNode Insert(BinaryTreeNode node, int data)
{
if (node == null)
{
return new BinaryTreeNode(data);
}
if (data < node.Data)
{
node.LeftChild = Insert(node.LeftChild, data);
return node;
}
if (data > node.Data)
{
node.RightChild = Insert(node.RightChild, data);
return node;
}
throw new ArgumentException("There is a node value equal to the parameter", nameof(data));
}
查找数据结点
查找数据结点的逻辑:在二叉查找树中查找目标结点,是从根结点出发,将二叉查找树结点中的值逐个与目标数据比较,小于该结点的值则往该结点左子树查找,大于则往该结点右子树查找。
关键实现算法如下:
public BinaryTreeNode Search(BinaryTreeNode binaryTreeNode, int data)
{
if (binaryTreeNode == null || data == binaryTreeNode.Data)
{
return binaryTreeNode;
}
if (data < binaryTreeNode.Data)
{
return Search(binaryTreeNode.LeftChild, data);
}
return Search(binaryTreeNode.RightChild, data);
}
删除数据结点
在二叉查找树上搜索(删除)数据对应的结点,如找到则删除该结点,反之则删除失败。删除二叉查找树中已有的结点,必须确保整棵树还是二叉查找树,即删除的同时需要妥善处理它的左、右子树。相应地,实现删除二叉查找树数据结点算法实现也较为复杂,可分两步进行实现。
首先是二叉查找树上搜索(删除)数据对应的结点,如找到则删除该结点,反之则删除失败。实现算法如下:
public BinaryTreeNode Delete(BinaryTreeNode binaryTree, int data)
{
if (binaryTree == null)
{
throw new ArgumentException("The node to be deleted does not exist.");
}
if (data == binaryTree.Data)
{
return Delete(ref binaryTree);
}
if (data < binaryTree.Data)
{
binaryTree.LeftChild = Delete(binaryTree.LeftChild, data);
return binaryTree;
}
binaryTree.RightChild = Delete(binaryTree.RightChild, data);
return binaryTree;
}
其次是删除找到的二叉查找树结点,并妥善处理结点删除后二叉查找树的左、右子树。其处理逻辑可以参考[二叉查找树图解][1]中,关于删除数据结点部分的解读。实现算法如下:
private static BinaryTreeNode Delete(ref BinaryTreeNode treeNode)
{
if (treeNode.LeftChild == null && treeNode.RightChild == null)
{
treeNode = null;
return treeNode;
}
if (treeNode.LeftChild != null && treeNode.RightChild != null)
{
BinaryTreeNode parentPreNode = treeNode; BinaryTreeNode preNode = treeNode.LeftChild;
while (preNode.RightChild != null)
{
parentPreNode = preNode;
preNode = preNode.RightChild;
}
treeNode.Data = preNode.Data;
if (parentPreNode != treeNode)
{
parentPreNode.RightChild = preNode.LeftChild;
}
else
{
parentPreNode.LeftChild = preNode.LeftChild;
}
return treeNode;
}
if (treeNode.LeftChild != null)
{
treeNode = treeNode.LeftChild;
return treeNode;
}
if (treeNode.RightChild != null)
{
treeNode = treeNode.RightChild;
return treeNode;
}
return treeNode;
}
二叉查找树删除结点算法的关键,是如何找到被删除结点的前驱结点,并将前驱结点转移到被删除结点的位置进行“补空”,上述代码中也提供了算法说明。
二叉查找树算法实现完整代码地址:前往 github。