Количество узлов в BST в C - PullRequest
Новая
       2

Количество узлов в BST в C

1 голос
/ 25 марта 2020 
int numOfNodes(struct node* rootPtr){
    if(rootPtr== NULL) return 0;

    int r = numOfNodes(rootPtr->right);
    int l = numOfNodes(rootPtr->left);
    return r+l+1; 
}

Может кто-нибудь объяснить мне, как это работает? Рекурсия немного смущает меня, так как я только начинаю. Я понимаю, что это +1 для узла root, но я не понимаю, как увеличиваются r и l.

Ответы [ 2 ]

0 голосов
/ 26 марта 2020

Давайте шаг за шагом перейдем к вашему коду с некоторыми примерами деревьев, становясь все более и более сложными.

Первый пример: пустое дерево

Это своего рода крайний случай. Если дерево пустое, его узел root равен NULL, вы можете видеть, что функция немедленно вернет 0, что является правильным результатом.

Второй пример: дерево с одним узлом

В этом случае наше дерево - это всего лишь один узел root, назовем его «A». Структура дерева выглядит следующим образом: 

     (A)
  /       \
NULL     NULL

Мы используем NULL указатели в качестве листьев, чтобы отметить, что у узла root нет дочерних элементов. Давайте перейдем к вызову функции.

  • Вы вызываете numOfNodes с A в качестве аргумента.
  • Сначала мы проверим, что аргумент не NULL, это не ' В этом случае мы продолжаем.
  • Затем мы вызываем numOfNodes с A->right в качестве аргумента.
    • Мы вводим другую numOfNodes функцию, на этот раз с rootNode = A->right
    • Оказывается, A->right равно NULL. Таким образом, этот вызов numOfNodes не go после первого if и возвращает 0.
  • Мы возвращаемся к первоначальному вызову numOfNodes, где r теперь имеет значение 0.
  • Затем мы вызываем numOfNodes в третий раз, на этот раз с rootNode = A->left в качестве аргумента.
    • Аналогично, этот вызов numOfNodes немедленно возвращает 0, потому что A->left равен NULL.
  • Мы возвращаемся к первоначальному вызову numOfNodes, где l теперь имеет значение 0
  • Теперь мы можем вернуть конечный результат: количество узлов слева (0), количество узлов справа (0) плюс тот, в котором мы сейчас находимся (1). Итого r+l+1 = 1, что является правильным результатом>

Возможно, вы заметили, что во время выполнения функция вызвала другую версию самой себя , но с аргумент, отличный от того, с которым он был первоначально вызван. Эта идея является очень мощной техникой программирования, называемой recursion , и особенно полезна при работе с деревьями.

По сути, вы начинаете с root дерева и просите его подсчитать количество узлов справа и количество узлов слева, а затем добавить один. Узнать количество узлов справа, очень просто. Вы используете ту же функцию , как если бы узел справа был root нового дерева . Это может привести к все большему количеству обращений к одной и той же функции подсчета, каждый раз с более глубоким узлом, как «fake root». Каскадные вызовы прекращаются, когда они достигают узла NULL. В конечном итоге результаты «всплывают» вверх по дереву, поскольку каждая функция возвращается к той, которая ее вызвала.

Третий пример: более полное дерево

Предположим, у нас теперь есть двоичное дерево с большим количеством узлов. Скажем, у нас есть это дерево высоты 3: 

        __(A)__
     /          \ 
    (B)         (C)
   /   \       /   \
 NULL  (D)   NULL  NULL
      /   \             
    NULL  NULL
  • Мы начинаем с вызова numOfNodes на root дерева, то есть A. A не NULL, поэтому мы продолжаем.
  • Мы называем numOfNodes с A->right аргументом.
  • Таким образом, мы вводим другую версию (# 2) из ​​numOfNodes с A->right в качестве аргумента. Оказывается, A->right - это C, а не NULL. Эта версия numOfNodes не возвращает 0 сразу.
  • Мы введем третью версию из numOfNodes, на этот раз с C->right в качестве аргумента.
  • Оказывается, C->right - это NULL, поэтому эта версия (# 3) numOfNodes возвращает 0
  • Так что переменная r во второй версии numOfNodes теперь имеет значение 0
  • То же самое происходит, когда мы вычисляем переменную l, потому что C->left также NULL.
  • Вторая версия numOfNodes, вызванная с C, достигает своей последней инструкции и возвращает r+l+1, что равно 0+0+1=1 (0 узлов слева, 0 узлов справа , плюс "фальшивка root" C).
  • Затем мы возвращаемся к first numOfNodes, поскольку теперь мы знаем, что r равно 1.
  • Теперь мы собираемся вычислить l для этой версии. Для этого мы снова вызовем numOfNodes, на этот раз с A->left (т.е. B) в качестве аргумента.
  • Я не буду подробно описывать это (я призываю вас сделать это на бумаге), на этот раз мы назовем numOfNodes еще четыре раза), и вычисляется l, равное 2.
  • Таким образом, общий результат равен 4 (1 узел справа, 2 слева плюс узел root).
0 голосов
/ 26 марта 2020

Давайте посмотрим на это простое дерево: 

  Root
 / \
A   B
   / \
  C   D

Тогда вызовы и возвраты следующие: 

numOfNodes( Root )  
    numOfNodes(B)
        numOfNodes(D)
        return 1
        numOfNodes(C)
        return 1
    return 3    
    numOfNodes(A)
    return 1
return 5
...