使用堆栈进行前序遍历

Question

我正在尝试实现二叉树，使用堆栈进行预排序遍历。这里弹出最后一个左节点，之后 root=root->right 似乎不起作用。请帮助。这里 7 被弹出并显示，程序结束后。

所有的功能都在工作，但不是预期的输出

            #include<stdio.h>
            #include<stdlib.h>
            #define maxsize 100
            int a[maxsize];
            int top=-1;
            struct node{
                int data;
                struct node *left, *right;
            };
            struct node *newNode(int data)
            {
                struct node *nn;
                nn=(struct node *)malloc(sizeof(struct node));
                if(!nn)
                    return;
                nn->data=data;
                nn->left=nn->right=NULL;
                return nn;
            };
            void push(struct node *root)
            {
                printf("pushcalled\n");
                if(top!=maxsize-1)
                    a[++top]=root;
            }
            int isempty()
            {
                return(top==-1);
            }
            struct node *pop()
            {
                printf("popcalled\n");
                if(top!=-1)
                {
                    return a[top];
                    top--;
                }
            }
            void deleteStack()
            {
                free(a[top--]);
            }
            void preorder(struct node *root)
            {
                while(1)
                {
                    while(root)
                    {
                        printf("%d\t",root->data);
                        push(root);
                        root=root->left;
                    }
                    printf("hello\n");
                    if(isempty())
                        break;
                    printf("hello\n");
                    root=pop();
                    printf("Popped data is:%d\n",root->data);
                    root=root->right;
                    printf("right data is:%d\n",root->data);
                }
                deleteStack();
            }
            int main()
            {
                int data;
                struct node *root=newNode(10);
                root->left = newNode(11);
                root->left->left = newNode(7);
                root->right = newNode(9);
                root->right->left = newNode(15);
                root->right->right = newNode(8);
                preorder(root);
                return 0;
            }

Answer 1

您的逻辑是正确的，但您的代码中存在一些错误。

 root=root->right;
 printf("right data is:%d\n",root->data);

在尝试访问 root->data 之前，您应该检查 root 是否为 null。这就是您遇到分段错误的原因。所以在 printf() 语句上面放一个条件 if(root!=NULL)。

另外一个错误是栈的出栈实现

       struct node *pop()
       {
            printf("popcalled\n");
            if(top!=-1)
            {
                return a[top];
                top--;
            }
        }

应该是这样的,

        struct node *pop()
        {
            printf("popcalled\n");
            if(top!=-1)
            {
                struct node* temp = a[top];
                top--;
                return temp;
            }
        }

在您的代码中，当您 return a[top]; 它下面的行即 top--; 永远不会执行并且 top 的值保持不变。

使用堆栈进行前序遍历

preorder traversal using stack

data-structures

tree

stack

iteration

preorder