树的非递归遍历

   树是递归定义的，利用递归算法遍历树实现起来比较简单，然而难的是非递归遍历。非递归遍历需要借助栈这一数据结构来完成。

首先定义树的结点和构建链表栈：

创建树：

遍历：

1.非递归前序遍历：

思想：（1）访问结点p，并将节点p进栈。如p的左孩子不为空，这将p的左孩子置为结点p，重复（1）；若p的左孩子为空，这获取栈顶值并出栈，栈顶结点的右孩子赋给p，重复（1），如栈为空且p==NULL，则遍历结束。

2.非递归中序遍历：

思想：

对于任意结点p

（1）若左孩子不为空，则将p进栈并将p的左孩子置为当前的p，然后对当前结点p进行同样处理。

（2）若左孩子为空，这访问该结点，并将栈顶元素出栈且将p置为栈顶元素的右孩子，进行（1）操作。

（3）知道p为空且栈顶元素为空时遍历结束。