如何在C#二叉搜索树（BST）中实现多数元素查找算法？

我尝试在自己的二叉搜索树（BST）中查找多数元素，但未能成功。我认为自己的BST代码是正常的，但完全不清楚如何基于二叉搜索树实现多数元素的查找算法。以下是我的C#代码：

class BinarySearchTree { 
    private Node root = null; 
    public Node Root { get => root; set => root = value; } 
    private int size = 0; 

    public BinarySearchTree() { //empty } 

    public Node getNodeByValue(int v, Node start) { 
        //if start node is empty value not found. 
        if (start == null) { 
            return null; 
        } 
        if (v == start.Value) { 
            return start; //Value found at start 
        } else if (v < start.Value) { 
            return getNodeByValue(v, start.LeftChild); 
        } else if (v > start.Value) { 
            return getNodeByValue(v, start.RightChild); 
        } else { 
            return null; //value not found 
        } 
    } 

    public void AddNode(Node start, int v) { 
        //Insert the new node in the tree 
        InsertNewNode(v, start); 
    } 

    public Node InsertNewNode(int v, Node start) { 
        Node newNode = new Node(v); 
        if (root == null) { 
            root = newNode; 
        } 
        if (start == null) { 
            start = newNode; 
            size++; 
            return start; 
        } 
        if (v < start.Value) { 
            if (start.LeftChild == null) { 
                start.LeftChild = newNode; 
            } else { 
                InsertNewNode(v, start.LeftChild); 
            } 
        } else if (v > start.Value) { 
            if (start.RightChild == null) { 
                start.RightChild = newNode; 
            } else { 
                InsertNewNode(v, start.RightChild); 
            } 
        } else { 
            InsertNewNode(v, start); 
            size++; 
        } 
        return start; 
    } 

    public void IncrementNodeFrequency(Node n) { 
        //If the node is not null 
        if (n != null) { 
            n.Frequency = n.Frequency + 1; 
        } 
    } 

    public int getMajorityElement(Node start) { 
        if(start!=null) { 
            // 不知道怎么实现 
        } 
        // 这里应该返回什么？ 
        return -1; // 临时占位 
    } 
}

// 假设Node类的定义大概是这样：
class Node {
    public int Value { get; set; }
    public int Frequency { get; set; }
    public Node LeftChild { get; set; }
    public Node RightChild { get; set; }

    public Node(int value) {
        Value = value;
        Frequency = 1;
        LeftChild = null;
        RightChild = null;
    }
}

首先得先修正你BST代码里的一个关键问题：你的InsertNewNode方法在遇到重复值时会无限递归调用自己（else { InsertNewNode(v, start); }），这会导致栈溢出。正确的做法应该是找到对应节点后调用IncrementNodeFrequency来增加频率，而不是重复插入。修改后的InsertNewNode应该是这样：

public Node InsertNewNode(int v, Node start) {
    if (root == null) {
        root = new Node(v);
        size++;
        return root;
    }
    if (start == null) {
        size++;
        return new Node(v);
    }
    if (v < start.Value) {
        start.LeftChild = InsertNewNode(v, start.LeftChild);
    } else if (v > start.Value) {
        start.RightChild = InsertNewNode(v, start.RightChild);
    } else {
        // 重复值，增加频率即可，不需要新增节点
        IncrementNodeFrequency(start);
    }
    return start;
}

接下来讲如何实现多数元素的查找。多数元素的定义是出现次数超过总节点数一半的元素，利用BST的特性（中序遍历结果是有序序列），我们可以用两种高效的思路来实现：

思路1：中序遍历 + 摩尔投票法 #

摩尔投票法是专门用来找多数元素的经典算法，核心思想是遍历过程中维护一个候选元素和计数器：

• 遇到和候选元素相同的值，计数器+1
• 遇到不同的值，计数器-1
• 当计数器为0时，更换候选元素为当前值
  因为多数元素的出现次数超过一半，所以最终剩下的候选元素就是多数元素。

结合BST的中序遍历（有序），我们可以在遍历过程中应用这个算法：

private int candidate = -1;
private int count = 0;

private void InOrderTraversalForVoting(Node node) {
    if (node == null) return;

    InOrderTraversalForVoting(node.LeftChild);

    // 摩尔投票逻辑
    if (count == 0) {
        candidate = node.Value;
        count = node.Frequency;
    } else if (candidate == node.Value) {
        count += node.Frequency;
    } else {
        count -= node.Frequency;
    }

    InOrderTraversalForVoting(node.RightChild);
}

public int getMajorityElement(Node start) {
    if (start == null) return -1; // 空树返回-1或其他标识值

    candidate = -1;
    count = 0;
    InOrderTraversalForVoting(start);

    // 验证候选元素是否真的是多数元素（避免没有多数元素的情况）
    int totalFrequency = GetFrequencyOfElement(candidate, start);
    if (totalFrequency > size / 2) {
        return candidate;
    } else {
        return -1; // 没有多数元素
    }
}

// 辅助方法：统计某个元素的总出现次数
private int GetFrequencyOfElement(int value, Node node) {
    if (node == null) return 0;
    if (value == node.Value) {
        return node.Frequency;
    } else if (value < node.Value) {
        return GetFrequencyOfElement(value, node.LeftChild);
    } else {
        return GetFrequencyOfElement(value, node.RightChild);
    }
}

思路2：中序遍历统计最大频率元素 #

因为BST中序遍历是有序的，相同元素会连续出现（对应的节点频率累加），所以我们可以在遍历过程中跟踪当前元素的总频率，记录最大频率的元素，最后判断它是否超过size/2：

private int maxFreq = 0;
private int currentVal = -1;
private int currentFreq = 0;
private int majorityCandidate = -1;

private void InOrderTraversalForFrequency(Node node) {
    if (node == null) return;

    InOrderTraversalForFrequency(node.LeftChild);

    if (node.Value == currentVal) {
        currentFreq += node.Frequency;
    } else {
        currentVal = node.Value;
        currentFreq = node.Frequency;
    }

    if (currentFreq > maxFreq) {
        maxFreq = currentFreq;
        majorityCandidate = currentVal;
    }

    InOrderTraversalForFrequency(node.RightChild);
}

public int getMajorityElement(Node start) {
    if (start == null) return -1;

    maxFreq = 0;
    currentVal = -1;
    currentFreq = 0;
    majorityCandidate = -1;

    InOrderTraversalForFrequency(start);

    if (maxFreq > size / 2) {
        return majorityCandidate;
    } else {
        return -1; // 无多数元素
    }
}

补充说明 #

• 两种思路的时间复杂度都是O(n)（n是BST的节点数），空间复杂度是O(h)（h是树的高度，递归调用栈的深度）
• 一定要记得验证候选元素的频率是否真的超过总节点数的一半，因为如果树中没有多数元素，摩尔投票法或频率统计得到的候选元素是无效的
• 如果你想避免递归，可以把中序遍历改成迭代实现，用栈来模拟递归过程，这样空间复杂度可以优化到O(1)（如果用莫里斯遍历的话）

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