如何移除二叉搜索树（BST）中的多余边？

问题解答 #

先看你描述的BST结构：节点1连接2和3，节点2连接4和5，节点3也连接5。这里的核心问题是节点5有两个父节点（2和3），这完全违反了二叉树（包括BST）的基本定义——除根节点外，每个节点只能有一个父节点。

要修复这个合法的BST结构，你确实只需要移除其中一条指向5的边：

• 若移除2->5：此时5成为3的子节点，注意要调整为3的右子节点（假设节点值是1、2、3、4、5），这样才符合BST“右子树节点值大于父节点”的规则。
• 若移除3->5：此时5成为2的右子节点，完美契合BST规则（5>2，且2的左子节点4<2，结构完全有序）。

两种选择都能让树回归合法结构，具体选哪一种取决于你期望的最终BST形态。

用BFS检测树结构异常 #

你附上的这段Java代码是标准的**广度优先搜索（BFS）**实现，我们可以基于它来检测树中的异常（比如重复父节点、环结构）。下面是格式化后的代码，补充了逻辑说明：

void BFS(int s) {
    // 初始化所有顶点为未访问状态（默认值为false）
    boolean visited[] = new boolean[V];
    // 创建BFS遍历所需的队列
    LinkedList<Integer> queue = new LinkedList<Integer>();

    // 标记起始节点为已访问，并加入队列
    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
        // 从队列中取出一个节点并打印
        s = queue.poll();
        System.out.print(s + " ");

        // 获取当前节点的所有邻接节点
        Iterator<Integer> i = adj[s].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            // 如果邻接节点未被访问过，标记为已访问并加入队列
            if (!visited[n]) {
                visited[n] = true;
                queue.add(n);
            }
            // 这里可以添加检测逻辑：如果邻接节点已访问且不是当前节点的父节点
            // 说明这条边就是多余的（比如你场景中的2->5或3->5），可在此记录并后续移除
        }
    }
}

你可以给这段代码加一个父节点数组，记录每个节点的父节点。遍历过程中，如果发现某个邻接节点已被访问，且不是当前节点的父节点，那这条边就是需要移除的多余边——刚好能解决你遇到的问题。

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