[数据结构与算法]二叉树的先序遍历（C++）

参考：二叉树的先序遍历

先序遍历，简而言之就是：根、左、右。

?按照先序遍历的访问顺序，肯定会把最左边那条路全部遍历完——终止条件是访问到了最左下角的空节点，再往回走。

//T是指向二叉树顶端节点的结构体指针，BiTree定义参考下面的完整代码
void PreOrderTraversal(BiTree T) 
{
    stack<BiTree> s;
    //先让 p 指向顶端节点
    BiTree p=T;
    //指针不为空 or 栈不为空，就还有可访问的元素
    //若两者都为空，说明指针访问到了最右下角的空指针了，就可以结束遍历了
    while(p != NULL || !s.empty())
    {
        //把当前特殊节点的左下角那条线全部访问完，直到遇到最左下角的空节点
        if(p)
        {
            cout<<p->data<<" ";
            //入栈是为了访问到最左下角的空节点时，方便回退
            s.push(p);
            //竭泽而渔，将当前节点的左下角那条线全部访问完，直到遇到空节点，回退
            p=p->lchild;
        }
        //遇到左下角空的节点，往回走，寻找下一个特殊节点
        else
        {
            //此时，指针已经访问到最左下角的空节点，要回退一格了
            p=s.top();
            //找到下一个特殊节点，又把它的左下角直线全访问掉
            p=p->rchild;
            //如果不pop出去，下一次s.top（）又会指向这个节点，就没法回退了
            s.pop();
        }
    }
}