Глубина печати в обходе почтового заказа BST

Question

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

                                  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
}

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

Answer 1

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

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

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
}

Answer 2

Переменная уровня поможет вам отслеживать глубину.Если вы передаете текущий уровень + 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
}