Блог

Главная - Вопросы по программированию - вычислить количество левых и правых дочерних элементов в двоичном дереве в sql server 2008 r2

вычислить количество левых и правых дочерних элементов в двоичном дереве в sql server 2008 r2

#sql-server #binary-tree

#sql-сервер #двоичное дерево

Вопрос:

У меня есть двоичное дерево, реализованное в sql server 2008 r2 в следующей форме

Информация о двоичном коде таблицы

Идентификатор родителя—-LeftChildID—-RightChildID

1—————2—————3

2—————4—————5

3—————6—————-7

       1(Root)    
  2   |    3     
4   5 |  6   7

и так далее. Теперь мне нужно вычислить общее количество элементов с левой и правой стороны элемента, например, 1 имеет 3 левых дочерних элемента и 3 правых дочерних элемента. 2 имеет 1 левый дочерний элемент и 1 правый дочерний элемент.

вероятно, я могу сделать это на c #, но есть ли способ сделать это на sql server с использованием процедур или функций?

Я не могу использовать heirarchyid, потому что данные уже заполнены в этой таблице.

P.S количество должно учитываться отдельно, т.е. общее количество левых дочерних элементов и общее количество правых дочерних элементов.

Ответ №1:

Вы могли бы создать рекурсивную процедуру, подобную этой:

 CREATE PROCEDURE BinaryTreeCount
    @ParentId int,
    @HowMany int OUTPUT
as
BEGIN
    DECLARE @childenCount int
    SET @childenCount = 0
    SET @HowMany = 0

    SET @LeftChildId = null
    SET @RightChildId = null

    SELECT @LeftChildId = LeftChildID
         , @RightChildId = RightChildID
      FROM yourTableName
     WHERE ParendId = @ParentId

    if (@LeftChildId is not null) begin
        @howMany = @howMany   1
        exec BinaryTreeCount @ParentId = @LeftChildId
                           , @HowMany  = @childenCount OUTPUT
        @howMany = @howMany   @childenCount
    end 

    if (@RightChildId is not null) begin
        @howMany = @howMany   1
        exec BinaryTreeCount @ParentId = @RightChildId
                           , @HowMany  = @childenCount OUTPUT
        @howMany = @howMany   @childenCount
    end 
END

Это просто идея, я ее не тестировал.

Комментарии:

1. большое спасибо… приведенная выше процедура возвращает общую совокупную сумму дочерних элементов, и мне нужно было отдельно подсчитать общее количество слева и справа. я предполагаю, что выполнение этого сделает процесс сложным для понимания и более подверженным ошибкам. Я всегда могу запустить эту процедуру для прямого левого и правого дочерних элементов отдельно, чтобы получить правильное общее количество и 1 к ним … еще раз спасибо

Ответ №2:

Поскольку вы используете SQL 2008, я совершенно уверен, что вы можете сделать это с помощью рекурсивного CTE (Common Table Expression):http://msdn.microsoft.com/en-us/library/ms186243.aspx

Боюсь, что без копии SQL передо мной мне было бы трудно показать код.