1、先序遍历二叉树 递归实现

思想：若二叉树为空，返回。否则

1）遍历根节点；

2）先序遍历左子树；

3）先序遍历右子树；

代码：

复制代码 代码如下:

template<typename elemType>

void PreOrder(nodeType<elemType> *root)

{

if(root==NULL)

return ;

visit(root->data); // visit the data

PreOrder(root->lchild); //递归调用，先序遍历左子树

PreOrder(root->rchild); //递归调用，先序遍历右子树

}

2、先序遍历二叉树 非递归实现

思想：二叉树的非递归先序遍历，先序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作， 每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。

前序遍历二叉树的非递归算法思想

建立栈 Stack；

t 指向根；

当 t 不空 或 Stack 不空时反复做：

若 t 不空，访问t，t 入 栈；t 指向左子女；

否则：出栈顶元素到 t 中；

t 指向右子女；

结束

复制代码 代码如下:

void PreOrder_Nonrecursive(BinaryTree T) //先序遍历的非递归

{

if(!T) return ;

stack<BinaryTree> s;

s.push(T);

while(!s.empty())

{

BinaryTree temp = s.top();

visit(temp->data);

s.pop();

if(temp->rchild)

s.push(temp->rchild);

if(temp->lchild)

s.push(temp->lchild);

}

}