参考：二叉树的先序遍历

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

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

//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();}}
}