时间戳

首页 > 解决方案 > 如何修改我用 C 编写的树遍历程序，使其不依赖递归？

c - 如何修改我用 C 编写的树遍历程序，使其不依赖递归？

问题描述

我有一个用 C 编写的程序，它以反向前序、反向中序和反向后序遍历树，其各个函数严重依赖递归。我将如何修改这些函数以使它们执行完全相同的任务但不使用任何递归？我花了很多时间试图通过使用临时存储值的变量来解决这个问题，但不幸的是我一直在画一个空白。我在 Ubuntu Linux BTW 上使用 GCC 编译器。

这是我的代码：

#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; 
}

标签： crecursiontree

解决方案

这个问题很困难，因为您的列表节点没有指向其父节点的指针。当一个迭代/命令式过程沿着当前节点的左或右链路行进以导航到另一个节点时，它没有反向路径。

解决这个问题的一般方法有两种：

  1. 维护一个显式堆栈，使过程能够导航到父级。

  2. 暂时改变树本身以提供返回路径。也就是说，暂时用指向父级的反向指针覆盖leftand链接；right然后在返回树时恢复值。

如果树是具有保证的最大深度的平衡树，那么 (1) 可以用一个相当小的、固定大小的数组来实现。

推荐阅读