c++ - 从前序遍历迭代构建二叉搜索树(非递归)

Question

以下是将二叉搜索树的前序遍历转换为原始树的代码。

以下代码采用整数数组，表示二叉搜索树的前序遍历。返回构造树的根。

struct Node* constructTree(int pre[], int size)
{
    stack<struct Node* > s;
    int i;
    struct Node* root=newNode(pre[0]);
    struct Node* temp;
    struct Node* top_node;
    s.push(root);
    for(i=1;i<size;i++)
    {
        temp=NULL;
        while(!s.empty()&&pre[i]>(s.top()->data))
            {
                temp=s.top();
                s.pop();
            }
            if(temp==NULL)
            {
                top_node=s.top();
                top_node->left=newNode(pre[i]);
                s.push(top_node->left);
            }else
            {
                temp->right=newNode(pre[i]);
                s.push(temp->right);
            }
    }


    return root;
}

来源:http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/

我无法理解这段代码。谁能帮助我理解以下内容:

1. 在任何给定迭代中，堆栈中存储的值与 pre[i]

指出的当前值相关

2. 是否有任何其他迭代方法可以从给定的前序遍历构造 BST？

谢谢。

Answer 1

在构建包含 pre[i] 的节点的迭代之后，堆栈在顶部包含该节点，其下从最叶到最根的祖先和恰好一个子节点从上到下存储。