Обход двоичного дерева вызывает переполнение стека

Итак, я создаю двоичное дерево поиска, реализованное через массивы (если индекс родителя - i, тогда индекс слева - (i * 2 + 1), а правый индекс ребенка - (i * 2 + 2).Обход двоичного дерева вызывает переполнение стека

Всякий раз, когда я пытаюсь обход дерева (предварительно упорядоченный), я получаю переполнение стека при вызове функции 3 предзаказа.

Вот мой код для предварительного заказа функция:

void traversePreOrder(Tree tree, int index) 
{ 
    printf("%d\n", index); //debug 
    if (tree.data[index].accNumber != 0) //all .accNumber values are initialized as 0 
            // at the start of the program to mark empty nodes. 
    { 
     printf("printing: %d\n", index); //debug 
     printNode(tree.data[index]); 

     if (tree.data[index * 2 + 1].accNumber != 0) 
     { 
      printf("will print: %d\n", index * 2 + 1); //debug 
      traversePreOrder(tree, index * 2 + 1); 
     } 

     if (tree.data[index * 2 + 2].accNumber != 0) 
     { 
      printf("will print: %d\n", index * 2 + 2); //debug 
      traversePreOrder(tree, index * 2 + 2); 
     } 
    } 
    else 
     return; 
}

Здесь выходной сигнал предварительного заказа обхода:

0 
printing: 0 
User: Dumbledore 
Account number: 53167 
Account type: public 
Account balance: 4597.54 
Is account in debt? Yes 

will print: 1 
1 
printing: 1 
User: Stark 
Account number: 13497 
Account type: private 
Account balance: 1549.50 
Is account in debt? No 

will print: 3 

Process returned 255 (0xFF) execution time : 5.856 s 
Press any key to continue.

Дерево должно выглядеть следующим образом:

(only accNumber values) 
        53167 
       /  \ 
       13457  74310 
       \  / \ 
       43158 71401 79473 
       / /  \ 
      14741 69690 99751

Спасибо за вашу помощь.

Update

Изменение максимальной мощности дерева от 1000 до 50 как-то решить эту проблему. Если бы кто-нибудь мог объяснить, почему это было бы хорошо.

источник

2015-05-13 Haris Vitunskas

У меня есть сильное подозрение, что вы читаете за пределами инициализированных данных в своем массиве и, следовательно, возвращаетесь навсегда. В качестве быстрого теста вы можете убедиться, что вся ваша структура tree.data [] очищена до 0 (так что чтение в данные, которые еще не написаны, возвращает 0 и изящно выходит из строя), чтобы это можно было исключить? –

Сразу после создания дерева я использую эту функцию: void initializeTree (Tree * tree) { if (tree == NULL) return; для (int i = 0; i data [i] .accNumber = 0; } } –

Вы не можете исследовать 'данные', если используемый индекс не известен * в пределах величины' data'. Просто потому, что у вас есть узел в вашем массиве, это не значит, что есть и его дети. Пример: ваше опубликованное дерево сохраняется в массиве из 16 узлов. Задайте себе, что делает ваш код, когда вы рекурсивно проверяете * детей * индекса 15. Проверка «tree.data [index * 2 + 1] .accNumber! = 0 'недостаточно. До этого вам нужно знать, что 'index * 2 + 1' находится в пределах' 0 .. (n-1) ', где' n' - это величина «данных» в первую очередь. – WhozCraig

Вы утверждаете, что:

все значения .accNumber инициализируются как 0 в начале программы , чтобы отметить пустые узлы.

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

Если вы хотите быть явным, вы должны сделать верхний индекс для индекса и не превышать его. Например: если tree.size IZ числа узлов в дереве, вы должны также Chack перед каждым шагом рекурсии, как это:

int left_child_idx = index * 2 + 1; 
    if (tree.data[left_child_idx].accNumber != 0 && left_child_idx < tree.size) 
    { 
     printf("will print: %d\n", index * 2 + 1); //debug 
     traversePreOrder(tree, index * 2 + 1); 
    }

Или, если вы не хотите, чтобы сделать это, вы должны убедиться, , что есть два оканчивающихся листа с 0 accNumber для все ваши последние узлы.

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

Выглядит некрасиво, но я надеюсь, что вы видите его:

     53167 
       /   \ 
       13457    74310 
      / \   /  \ 
      0  43158  71401  79473 
     /\ / \ / \ /\ 
     0 0 14741 0 69690 0 0 99751 
     /\ /\ /\ /\ /\ /\ /\ /\ 
     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

И как массив:

[53167, 13457, 74310, 0, 43158, 71401, 79473, 0, 0, 14741, 0, 69690, 0, 0, 99751, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Существует 31 элемент, 99751 является пятнадцатым. Будет ли любая вторая половина отличной от нуля, вы получите переполнение.

источник

2015-05-13 18:08:46

Обход двоичного дерева вызывает переполнение стека

ответ

Смежные вопросы