返回多个int值

Question

我创建了一个包含两个整数列

Node

和

Parent

的 BST 表。我在这个表中插入一些值，我想检测叶节点、内部节点和根节点。

代码：

CREATE TABLE BST 
(
    Node int,
    Parent int
);

INSERT INTO BST (Node, Parent) VALUES (1, 2);
INSERT INTO BST (Node, Parent) VALUES (3, 2);
INSERT INTO BST (Node, Parent) VALUES (6, 8);
INSERT INTO BST (Node, Parent) VALUES (9, 8);
INSERT INTO BST (Node, Parent) VALUES (2, 5);
INSERT INTO BST (Node, Parent) VALUES (8, 5);

INSERT INTO BST (Node) VALUES (5);

我写了这个查询：

SELECT
    Node,
    CASE
        WHEN Parent IS NULL THEN 'Root'
        WHEN Node_ IS NOT NULL AND Parent IS NOT NULL
             AND (SELECT Node_ FROM BST) NOT IN (SELECT Parent FROM BST) 
            THEN ('Leaf')
        WHEN Node IS NOT NULL AND Parent IS NOT NULL
             AND (SELECT Parent FROM BST) NOT IN (SELECT Node FROM BST)
            THEN ('Inner')
    END
FROM
    BST;

我期待得到这样的结果：

1 Leaf
2 Inner 
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf

但我收到此错误：

子查询返回超过 1 个值。当子查询跟在 =、!=、<, <= , >、>= 后面或子查询用作表达式时，这是不允许的。

有人对这个问题有任何想法吗？这是语法错误还是逻辑错误？或者我的算法不正确...

Answer 1

如果您不需要递归查询来进行树遍历，您可以使用此查询（按照您的初始风格，但 OUTER APPLY 选项更适合我的口味=）：

select node,
        case
            when Parent IS NULL then 'Root'
            when not exists(select * from bst sub where sub.parent = r.node) then 'Leaf'
            else 'Inner'
        end type
    from bst r

在这里，“内部”项目不需要特殊条件 - 它们只是不是根也不是叶。 Leaf 你可以检查一下它是否没有一个孩子。

Answer 2

最初的问题是您的

AND (SELECT Node_ FROM BST) NOT IN (SELECT Parent FROM BST)

状况。左侧需要是单个值，并且您似乎打算引用当前

main

Node 行中的

FROM BST

列值。在这种情况下，您需要类似

AND Node NOT IN (SELECT Parent FROM BST)

的东西。

下一个

WHEN

案例类似，但到那时，我认为您所需要的只是

ELSE 'Inner'

。

还有一个问题是

NOT IN (subselect)

。如果子选择产生任何空值，则

NOT IN

条件实际上将为 false，即使其他值匹配也是如此。这可以通过向子选择添加

NOT NULL

过滤器来解决 -

AND Node NOT IN (SELECT Parent FROM BST WHERE Parent IS NOT NULL)

，但最好使用

NOT EXISTS()

，如

NOT EXISTS (SELECT * FROM BST C WHERE C.Parent = B.Node)

（带有表别名）。

向所有表引用添加别名并使用这些别名限定所有列引用是最佳实践，尤其是对于子选择。

条件中的

Node IS NOT NULL AND Parent IS NOT NULL

部分是不必要的，可以删除。

结果会是这样的：

SELECT
    B.Node,
    CASE
        WHEN B.Parent IS NULL
            THEN 'Root'
        WHEN NOT EXISTS (SELECT * FROM BST C WHERE C.Parent = B.Node) 
            THEN 'Leaf'
        ELSE 'Inner'
    END
FROM
    BST B
ORDER BY
    B.Node;

参见这个数据库<>小提琴。

Answer 3

我假设您正在寻找 sql server 中的递归 CTE？您的查询不起作用，因为您无法在子查询中调用查询本身。我在这里只是添加一个粗略的想法，如果你想了解更多关于Recursive CTE，请查看msdn https://learn.microsoft.com/en-us/sql/t-sql/queries/with-common-table-expression-transact-sql?view=sql-server-ver16

WITH Root AS (
  SELECT
    Node,
    1 AS level
  FROM BST
  WHERE parent IS NULL
  UNION ALL
  SELECT
    b.parent,
    level + 1
  FROM BST b
  INNER JOIN Root r
    ON b.Parent = r.Node
)
SELECT *
FROM Root;

Answer 4

正如我的评论一样，这个表的设计对于 BST 来说很糟糕。但这并非不可能，我们可以通过使用从表到自身的横向连接来获得所需的答案（不需要正式的完整遍历！）：

SELECT p.Node, CASE WHEN p.Parent IS NULL THEN 'Root'
                    WHEN fc.Node IS NULL THEN 'Leaf'
                    ELSE 'Inner' END As NodeType
FROM BST p -- parent
OUTER APPLY (SELECT TOP 1 c.Node FROM BST c WHERE c.Parent = p.Node) fc -- first child
ORDER BY p.Node

也可以在

NOT EXISTS()

子句中使用相关子查询（和

SELECT

）来完成此操作，但我发现这更容易编写和推理。

在这里查看它的工作原理：

https://dbfiddle.uk/wNFbOdl4