Post-order 树遍历中的分段错误

Question

我正在尝试使用单个堆栈实现树的后序遍历。我现在遇到 分段错误 有人可以解释一下原因吗？

这是算法：

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

例子

。右 child 的 1 存在。推 3 堆叠。按 1 堆叠。向左移动 child。堆栈: 3, 1

右侧 child 存在 2 个。推 5 堆叠。推 2 堆叠。向左移动 child。堆栈：3、1、5、2
右 child 4 个不存在。 ' 推 4 堆叠。向左移动 child。堆栈：3、1、5、2、4
当前节点为 NULL。从堆栈中弹出 4。右 child 4 不存在。打印 4. 将当前节点设置为 NULL。堆栈：3、1、5、2
当前节点为 NULL。从堆栈中弹出 2。由于 right child of 2 等于栈顶元素，从堆栈中弹出 5。现在将 2 压入堆栈。
将当前节点向右 child 移动 2 即 5 堆栈：3、1、2
右边 child 5 个不存在。推 5 堆叠。向左移动 child。堆栈：3、1、2、5
当前节点为 NULL。从堆栈中弹出 5。右child共5个不存在。打印 5. 将当前节点设置为 NULL。堆栈：3、1、2
当前节点为 NULL。从堆栈中弹出 2。右 child of 2 不等于栈顶元素。打印 2. 将当前节点设置为 NULL。堆栈: 3, 1
当前节点为 NULL。从堆栈中弹出 1。因为 right child of 1 等于栈顶元素，从栈中弹出 3。现在将 1 推入堆栈。将当前节点向右 child 移动 1 即 3 堆栈：1
重复上述步骤，打印6、7、3。弹出 1 和打印 1。

代码：问题出在 Ipostorder 函数中。如果您发表评论并且运行您将不会遇到分段错误。

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int data;
    struct node *left,*right;

}node;
typedef struct stack
{
    node *data;
    struct stack *next;
}stack;
stack *top=NULL;
int isEmpty()
{
    if(top==NULL)
        return 1;
    else
        return 0;
}

node *pop()
{
    node *p=top->data;
    top=top->next;
    return p;
}
void push(node *num)
{
    stack *p;
    p=malloc(sizeof(stack));
    p->data=num;
    p->next=top;
    top=p;

}


node *newNode(int key)
{
    node *p=malloc(sizeof(node));
    p->left=p->right=NULL;
    p->data=key;
    return p;
}
void insert(node **head,int key)
{
    node *p;
    p=*head;
    if(!p)
    {
        *head=newNode(key);
        return;
    }
    if(p->data>key)
        insert(&(p->left),key);
    else
        insert(&(p->right),key);
}
void inorder(node *head)
{
    if(head)
    {
        inorder(head->left);
        printf("%d ",head->data);
        inorder(head->right);
    }
}
int search(node *head,int key)
{
    if(head==NULL)
        return 0;
    if(head->data==key)
        return 1;
    if(head->data>key)
        search(head->left,key);
    else
        search(head->right,key);
}   

void Ipostorder(node *head)
{
    do
    {
        while(head)
        {
            if(head->right) //If right child is present
                push(head->right);  //Push right child first
            push(head);     //Push root
            head=head->left;    //Goto left
        }
        head=pop();
        if(head->right && top->data==head->right)
        {   
            pop(); //Remove right child from stack
            push(head); //Push root onto the stack
            head=head->right;

        }
        else
        {
            printf(" %d",head->data);
            head=NULL;
        }

    }while(!isEmpty());
}
void postorder(node *head)
{
    if(head)
    {
        postorder(head->left);
        postorder(head->right);
        printf(" %d",head->data);
    }
}
int main()
{
    node *head;
    int opt,choice=1,key;
    while(choice!=5)
    {
        printf("\n\nBST\n1.Insert into BST\n2.Inorder Traversal\n3.Search\n4.Iterative preorder\n5.Exit\n\nChoice - "); 
        scanf("%d",&choice);

        switch(choice)
        {
            case 1: printf("\nEnter the no of elements to be inserted - ");
                scanf("%d",&opt);
                printf("\nEnter the elements - ");          
                while(opt--)
                {           
                    scanf("%d",&key);
                    insert(&head,key);
                }
                printf("\nElement successfully inserted");
                break;
            case 2: printf("\nThe inorder traversal is  - ");
                inorder(head);
                break;
            case 3: printf("\nEnter the item to be searched - ");
                scanf("%d",&key);
                if(search(head,key))
                    printf("\nItem found");
                else 
                    printf("\nItem not found");
                break;
            case 4: printf("\nThe iterative postorder is - ");
                Ipostorder(head);
                printf("\nThe recursive postorder is - ");  
                postorder(head);

                break;
            case 5: exit(0);
                break;

        }
        getchar();
        getchar();
    }   
}

Input/Output

BST
1.Insert into BST
2.Inorder Traversal
3.Search
4.Iterative preorder
5.Exit

Choice - 1   

Enter the no of elements to be inserted - 7

Enter the elements - 30 20 40 15 25 35 45

Element successfully inserted


BST
1.Insert into BST
2.Inorder Traversal
3.Search
4.Iterative preorder
5.Exit

Choice - 2

The inorder traversal is  - 15 20 25 30 35 40 45 


BST
1.Insert into BST
2.Inorder Traversal
3.Search
4.Iterative preorder
5.Exit

Choice - 4

Segmentation fault (core dumped)

Answer 1

Ipostorder 在验证它不为 NULL 之前取消引用 top。同样，它在第一个 pop.

之后取消引用 head

Post-order 树遍历中的分段错误

Segmentation Fault in Post-order Tree traversal

c

tree

segmentation-fault

tree-traversal

binary-search-tree