Бинарное дерево поиска, не рекурсивный обход дерева, переполнение

Question

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

#include <stdio.h>
#include <stdlib.h>


typedef struct tree {
   struct tree *right;
   struct tree *left;
   int value;
} BinTree;

typedef struct LinkedList {
   struct LinkedList *upper;
   BinTree *tree;
} List;

BinTree *createNode(value)
{
   BinTree *newNode = (BinTree*) malloc(sizeof(BinTree));
   newNode->value = value;
   newNode->left = NULL;
   newNode->right = NULL;

   return newNode;
}

BinTree *insert(BinTree *tree, int value) {

   if (tree == NULL) return createNode(value);

   if (value < tree->value)
       tree->left = insert(tree->left, value);
   else if(value >= tree->value)
       tree->right = insert(tree->right, value);

   return tree;
}

List *add(List *list, BinTree *tree) {
   List *newNode = (List*) malloc(sizeof(List));
   newNode->tree = tree;
   newNode->upper = list;
   return newNode;
}

BitTree *delet(List *list) {
   List *previous = list->upper;
   free(list);
   return previous;
}

void Show(BinTree *tree)
{
   printf("1");
   List *list = NULL;
   list = add(list, tree);
   while (list != NULL)
   {
       printf("2");
       BinTree *temp = delet(list);
       printf("%d ", temp->value);
       if (temp->right != NULL)
       {
           list = add(list, temp->right);
           printf("3");
       }

       if (temp->left != NULL)
       {
           list = add(list, temp->left);
           printf("4");
       }
   }
}


int main(int argc, char *argv[]) {
   BinTree *tree = NULL;
   tree = insert(tree, 8);
   insert(tree, 3);
   insert(tree, 1);
   insert(tree, 6);
   insert(tree, 7);
   insert(tree, 10);
   insert(tree, 14);
   insert(tree, 4);

   Show(tree);
   return 0;
}

Answer 1

Да на первой же итерации цикла после

BinTree *temp = delet(list);

в temp будет NULL, и все дальнейшие проверки не имеют смысла.

Answer 2

Самый простой способ избавиться от рекурсии - использовать стек в цикле. Берете вершину дерева, указатели left и right (если не нулевые) заносите в стек, значение - в список. Затем из стека берете указатель с вершины и повторяете действия. Так значения из дерева переносятся в список.

typedef struct LinkedList {
   LinkedList *upper;
   int value;  // в список нужно помещать только значения, а не указатели на узлы дерева
} List;

void TreeToList(BinTree* tree_node, List* my_list)
{
    if(tree_node == NULL)
        return;
    vector<BinTree*> mystack;
    
    if(tree_node->left != NULL)
        mystack.push_back(tree_node->left);
    if(tree_node->right!= NULL)
        mystack.push_back(tree_node->right);
    add( my_list, tree_node->value); // в список нужно помещать только значения, а не указатели на узлы дерева
    delete tree_node;
    
    while( !mystack.empty() )
    {
        tree_node = mystack.back();
        mystack.pop_back();
        if(tree_node->left != NULL)
            mystack.push_back(tree_node->left);
        if(tree_node->right!= NULL)
            mystack.push_back(tree_node->right);
        add( my_list, tree_node->value);
        delete tree; // удаляет узел дерева
        
    }; 
}

По сути здесь вместо системного стека мы создаем свой стек в памяти.

Answer 3

Функция должна выглядеть так:

BitTree* delet(List* &list) 
{
   List *previous = list->upper;
   BitTree* new_tree = list->tree;
   free(list);
   return new_tree;
}

БЛОГ НА HUSL

Бинарное дерево поиска, не рекурсивный обход дерева, переполнение

Ответы (3 шт):