C#二叉搜索树插入算法解析

结果与目标

将一个新的整数值 data 插入到以 root 为根的 BST 中，保持树的二分查找性质（即左小右大），并确保不会重复插入已存在的节点（本例逻辑倾向于覆盖或追加到最右侧，具体取决于业务对重复值的定义，此处仅演示位置定位过程）。

准备条件

• 节点类定义：需要预先定义包含左右指针和数据字段的节点类。
• 非空根节点：该方法假设传入的 root 引用不为 null。若根为空，需特殊处理创建首个根节点。

public class BinaryTreeNode
{
 public BinaryTreeNode Left { get; set; }
 public BinaryTreeNode Right { get; set; }
 public int Data { get; set; }
 
 // 构造函数用于初始化节点数据
 public BinaryTreeNode(int data)
 {
   this.Data = data;
 }
}

真实操作顺序

第1步：初始化遍历指针

为了不影响外部原始根节点的引用，同时追踪当前路径，我们需要两个辅助指针：_current 指向正在检查的节点，_previous 始终指向 _current 的前驱节点。

// 创建待插入的新节点
BinaryTreeNode _newNode = new BinaryTreeNode(data);
// _current 从根开始向下遍历
BinaryTreeNode _current = root;
// _previous 初始化为根，用于最后挂载新节点
BinaryTreeNode _previous = _current;

第2步：定位插入位置

进入循环，只要 _current 不为空，就根据大小比较决定走向：
1. 若 data < _current.Data：说明新值应在左侧，将前驱设为当前，并向左移动。
2. 若 data > _current.Data：说明新值应在右侧，将前驱设为当前，并向右移动。
注意：如果 data == _current.Data，当前代码逻辑会继续循环直到找到空位（通常不会发生除非树不平衡或逻辑有漏洞，标准BS中相等的值通常不插入或放在某一侧）。在本示例代码中，由于没有 else 分支处理相等情况，它可能会陷入死循环或行为未定义，因此建议在实际应用中明确处理重复值。

while (_current != null)
{
 if (data < _current.Data)
 {
   _previous = _current;
   _current = _current.Left;
 } else if (data > _current.Data)
 {
   _previous = _current;
   _current = _current.Right;
 }
}

第3步：建立连接

当循环结束时，_current 变为 null，_previous 即为新节点应挂载的父节点。根据大小关系，将新节点赋值给其左子节点或右子节点。

if (data < _previous.Data)
 _previous.Left = _newNode;
else
 _previous.Right = _newNode;

完成判断

执行上述步骤后，可以通过中序遍历（In-order Traversal）验证 BST 的正确性。输出结果应为有序序列。若树中原本不存在该值，且插入成功，树的节点数将增加1。

简要总结

C# 中的二叉搜索树插入核心在于“寻找空位”。通过维护前后指针，我们可以高效地定位新节点的位置。需要注意的是，上述代码并未处理 root 为空的边界情况，实际工程中应先判断根节点是否存在。以上就是C#二叉搜索树插入算法实例分析的详细内容，更多关于C#数据结构与算法的资料请关注本站其它相关文章！