C# BST二叉搜索树全树遍历及Map、Filter方法实现求助

遍历丢近半数节点的核心原因是递归逻辑没有覆盖完整的三个处理环节：左子树递归、当前节点处理、右子树递归，缺任意一个分支都会丢失对应子树的全部节点。
下面直接给可落地的实现，基于你现有代码扩展即可。 #

前置修改 #

你原有代码中入口级的单参数add(T element)是private修饰，需要先改成public，方便后续构建新树时调用插入逻辑：

// 把原来的private修饰改成public
public void add(T element)
{
    if (root == null)
        root = new Node(element);
    else
    {
        add(element, root);
    }
}

第一步：实现无遗漏的核心遍历辅助方法 #

用深度优先中序遍历实现，遍历顺序为「左子树->当前节点->右子树」，天然适配BST的有序特性，且只要递归逻辑写对就不会丢节点：

/// <summary>
/// 递归遍历整棵树，把所有节点值按中序收集到传入的列表
/// </summary>
private void Traverse(Node current, List<T> valueCollector)
{
    // 递归终止条件：当前节点为空直接返回
    if (current == null) return;
    
    // 先遍历整个左子树
    Traverse(current.left, valueCollector);
    // 收集当前节点的值
    valueCollector.Add(current.value);
    // 最后遍历整个右子树
    Traverse(current.right, valueCollector);
}

不要提前判断子节点是否存在再决定是否递归，把空节点判断交给递归终止条件处理，能最大程度避免写漏分支。

第二步：实现Map方法 #

Map方法会将树中所有元素按传入的转换规则映射为新类型值，返回一颗全新的、符合BST规则的新树，不会修改原树数据：

public BST<TResult> Map<TResult>(Func<T, TResult> convertFunc) where TResult : IComparable<TResult>
{
    // 先拿到原树所有节点值
    var allOriginalValues = new List<T>();
    Traverse(root, allOriginalValues);
    
    // 构建新BST
    var mappedTree = new BST<TResult>();
    foreach (var originalVal in allOriginalValues)
    {
        mappedTree.add(convertFunc(originalVal));
    }
    return mappedTree;
}

第三步：实现Filter方法 #

Filter方法会按传入的筛选条件保留符合要求的元素，同样返回全新的BST：

public BST<T> Filter(Predicate<T> matchCondition)
{
    var allOriginalValues = new List<T>();
    Traverse(root, allOriginalValues);
    
    var filteredTree = new BST<T>();
    foreach (var val in allOriginalValues)
    {
        if (matchCondition(val))
        {
            filteredTree.add(val);
        }
    }
    return filteredTree;
}

常见遍历漏节点的错误写法避坑 #

• 递归时只写了左/右单侧子树的递归调用，会直接丢失另一侧整棵子树的节点
• 处理完当前节点就直接返回，没有继续递归子节点，最终只能拿到根节点到某一个叶子节点单条路径上的值
• 终止条件写错，比如遇到叶子节点就直接返回，没有收集叶子节点本身的值

内容的提问来源于stack exchange，提问作者Bartolinio Kooperinio