Блог

Двоичное дерево чисел со структурой узлов

 type def numbernode
{
    unsigned value;
    numbernode * left;
    numbernode * right;
}
  

и внешний указатель (на корневой узел)
напишите функцию
в наибольшем (numbernode * tree)
вернет наибольшее число в дереве, если дерево не пустое. ваша функция должна возвращать -1, если дерево пустое.

это практический вопрос для теста, я потратил часы, пытаясь разобраться в этом, мне нужна помощь в написании кода!!

Проблемы рекурсии действительно легко решить, как только вы начнете думать о них правильным образом, особенно в отношении деревьев. «Какое наибольшее число в дереве? Ну, это самый высокий показатель для меня, моего левого дочернего элемента и моего правого дочернего элемента…какой самый высокий из моих левых дочерних элементов? ну, это самое высокое из этого дочернего элемента, его левое и правое ….» и так далее.

действительно простая задача рекурсии.

 int largest( node* root )
{
    if ( root == null )
        return -1;

    int left = largest(root->left);
    int right = largest ( root->right);
    if( root->value > left amp;amp; root->value > right )
       return root->value;
    else
       return max ( left, right );
}
  

рекурсия — ваш друг — вот схема

 int maxValue(Node n) {

    if(n == null) return -1 // if this is a null node, get out with -1

    // each time you call this, it spawns a new version of this function
    // calling maxValue(root) could end up calling maxValue on a .left node
    // dozens of times before it calls one on a .right node!
    int left = maxValue(n.left) // get the left value's max
    int right = maxValue(n.right) // get the right value's max

    return max(this.value, left, right) // return the highest of the three values
}
  

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

P.S. синтаксис в моем коде просто неправильный. Например, здесь нет точек с запятой. Он также игнорирует указатели или что-либо еще. Думайте об этом только как о псевдокоде, удобном для C .

Просто выполните обход дерева, используя любой из известных методов inorder, preorder или postorder. Вы обязательно столкнетесь с самым большим элементом во время обхода.

Просто пройдитесь по правой части дерева и верните последний ненулевой узел.

Знаете ли вы алгоритмы обхода дерева (по порядку, перед заказом, после заказа)?

Нарисуйте простое дерево и выполните шаги карандашом. В какой-то момент в поддереве попробуйте «обобщить» описание, которое работает для поддерева, а затем посмотрите, сможете ли вы придумать описание, которое «продолжало» бы работать для всего дерева.