c++ - 二叉树的中序遍历遍历后给出垃圾值和段错误

Question

我正在尝试使用堆栈遍历二叉树，遍历成功但最后的程序显示垃圾值和段错误。我认为它不会一次又一次地到达顶部，但我无法解决这个问题。

struct Node
{
    int data;
    Node *left;
    Node *right;
    Node(int x) 
    {
        data = x;
        left = NULL;
        right = NULL;
    }
};

Node *STACK[10] = { NULL };
int TOP = -1;

void push(Node *ptr)
{
    if(TOP < 10) {
        STACK[++TOP] = ptr;
    }
}

void stackTraversal(Node *root)
{
    Node *ptr = root; bool flag = false;
    top:
    while(ptr != NULL)
    {
        push(ptr);
        ptr = ptr->left;
    }

    ptr = STACK[TOP];
    TOP--;
    while(ptr != NULL)
    {
        cout << ptr->data << " ";
        if(ptr->right != NULL)
        {
            ptr = ptr->right;
            flag = true;
            break;
        }
        ptr = STACK[TOP];
        TOP--;
    }
    if(flag)
        goto top;
    cout << "\nTHE END\n"; 
}

int main(int argc, char const *argv[])
{
    Node *R = new Node(2); 
    Node *a = new Node(0);
    Node *b = new Node(1);
    Node *c = new Node(4);
    Node *d = new Node(5);
    Node *e = new Node(3);

    R->right = c;
    R->left = a;

    a->right = b;

    c->right = d;
    c->left = e;

    stackTraversal(R);
    cout << endl;
    return 0;
}

它给出以下输出。

输出:-0 1 2 3 4 5 -786491 段错误(核心转储)

Answer 1

从你的输出可以看出，你已经遍历了所有元素，最后访问到的元素是d。

现在你在这个 block 中，其中 ptr 指向 d:

        if(ptr->right != NULL)
        {
            ptr = ptr->right;
            flag = true;
            break;
        }
        ptr = STACK[TOP];

好吧，d没有 child ，你不进入if block ，你计划访问的下一个节点是... STACK[ -1].

修改你的算法。我建议避免使用 goto，因为这是众所周知的错误做法。