Как изменить программу обхода дерева, написанную на C, чтобы она не зависела от рекурсии?

Question

У меня есть программа, написанная на C, которая перебирает дерево в обратном, обратном порядке и обратном порядке, отдельные функции которого сильно зависят от рекурсии.Как мне изменить эти функции, чтобы они выполняли одну и ту же задачу, но без использования какой-либо рекурсии?Я потратил много часов, пытаясь выяснить это, используя переменные, которые временно хранят значения, но, к сожалению, я продолжаю рисовать пустым.Я использую компилятор GCC в Ubuntu Linux BTW.

Вот мой код:

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


struct node 
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 


struct node* newNode(int data) 
{ 
    struct node* node = (struct node*) 
                                malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 

    return(node); 
} 


void reversePostOrder(struct node* node) 
{ 
    if (node == NULL) 
        return; 


    reversePostOrder(node->right);


    reversePostOrder(node->left); 



    printf("%d ", node->data); 
} 


void reverseInOrder(struct node* node) 
{ 
    if (node == NULL) 
        return;  


    reverseInOrder(node->right);


    printf("%d ", node->data); 


    reverseInOrder(node->left);


} 


void reversePreOrder(struct node* node) 
{ 
    if (node == NULL) 
        return; 


    printf("%d ", node->data); 


    reversePreOrder(node->right);


    reversePreOrder(node->left); 


}    


int main() 
{ 


    struct node *root = newNode(1);
    root->left           = newNode(-2);
    root->right      = newNode(-3);
    root->left->left     = newNode(4);
    root->left->right = newNode(5);
    root->right->left =newNode(6);
    root->right->right=newNode(7);
    root->left->right->left=newNode(-8);
    root->left->right->right=newNode(-9);
    root->right->right->left=newNode(10);
    root->right->right->right=newNode(11);
    root->right->right->right->left=newNode(-12);
    root->right->right->right->right=newNode(-13);
    root->right->right->right->right->left=newNode(14);
    printf("\nReverse Preorder traversal of binary tree is \n"); 
    reversePreOrder(root); 

    printf("\nReverse Inorder traversal of binary tree is \n"); 
    reverseInOrder(root); 

    printf("\nReverse Postorder traversal of binary tree is \n"); 
    reversePostOrder(root); 

    getchar(); 
    return 0; 
} 

Answer 1

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

Существует два основных подхода к проблеме:

1. Поддерживайте явный стек, который позволяет процедуре перейти к родительскому элементу.

2. Временно изменяйте само дерево, чтобы обеспечить путь возврата.То есть временно перезаписать ссылки left и right обратными указателями на родительский;затем восстановите значения при возврате вверх по дереву.

Если дерево является сбалансированным деревом с гарантированной максимальной глубиной, то (1) может быть реализовано с достаточно малым фиксированным размероммассив.

Answer 2

вы можете использовать стек для хранения родительского элемента и массива, если узел был ранее обработан или нет ранее.пример для заказа

push(root)
while stack is not empty()
   parent=stack.top()
   if parent->left and done[parent->left]==false
       left=parent->left
       push(parent)
       done[left]=true
       continue
   if done[parent]==false
       process(parent)
       done[parent]=true
   if parent->right and done[parent->right]==false
       right=parent->right
       push(right)
       done[right]=true
       continue
   stack.pop()