Блог

Итак, прямо сейчас я внедрил обход по порядку, и мне нужно напечатать глубину, на которой находится узел. Итак, если мое дерево представляет собой что-то вроде:

                                   5
                                 / 
                                2   9
                                   /
                                 3 7
  

Затем, когда он печатает 3, он должен иметь глубину 2.
Где я мог бы увеличить глубину, если я вызываю ее рекурсивно.И как бы мне уменьшить ее, если я поднимаюсь по дереву?

Мой код

 void post_order(BST* root,int level)
    if(root == NULL){
        return;
    }
    post_order(root -> left,level); 
    post_order(root -> right, level);
    //Here I would print the node info and depth
}
  

Я спрашиваю, где бы я увеличил уровень, чтобы показать соответствующие глубины узлов и почему?

Нет необходимости увеличивать / уменьшать уровень. Когда вы выполняете рекурсивный вызов, просто передайте значение, которое на единицу больше текущего уровня, когда стек развернется, уровень для предыдущего уровня по-прежнему будет тем значением, которое было до рекурсивного вызова.

Конечно, то, где вы печатаете уровень, будет определять порядок, в котором вы видите уровень, напечатанный по мере обхода дерева.

 void post_order(BST* root,int level)
    if(root == NULL){
        return;
    }
    post_order(root -> left,level   1); 
    post_order(root -> right, level   1);
    //Here I would print the node info and depth
}
  

Переменная level поможет вам отслеживать глубину. Если вы передаете значение текущего уровня 1 дочернему уровню каждый раз, когда выполняете рекурсивный вызов, вы получите правильную глубину в каждом узле. В зависимости от того, хотите ли вы, чтобы глубина корня была равна 1 или 0, выполните начальный вызов с корневым узлом и пунктом 2 как 0 или 1.

 void post_order(BST* root,int level)
if(root == NULL){
    return;
}
post_order(root -> left,level 1); 
post_order(root -> right, level 1);
//print node info, depth = level
}