二叉树：先序遍历（前序遍历），递归和非递归方式实现

1、二叉树节点定义typedef struct BTreeNodeElement_t_ {
void *data;
} BTreeNodeElement_t;typedef struct BTreeNode_t_ {
BTreeNodeElement_t *m_pElemt;
struct BTreeNode_t_ *m_pLeft;
struct BTreeNode_t_ *m_pRight;
} BTreeNode_t;2、前序遍历定义：先访问根节点，在访问左子树，最后访问右子树；（1）递归实现如果根节点为NULL，返回。如果根节点不为NULL，则先访问根节点，然后再访问左子树，最后访问右子树void PreorderTraverse（ BTreeNode_t *pRoot）{
if（ pRoot == NULL ）
return ; Visit（ pRoot）;
PreorderTraverse（ pRoot->m_pLeft ）;
PreorderTraverse（ pRoot->m_pRight）;
return;
}（2）非递归实现借助STL的栈实现第一步：首先判断pRoot是否为空，若不为空，则进行第二步；若为空，则进行第三步。第二步：访问pRoot，然后将pRoot入栈，将pRoot左结点赋给pRoot，然后对新pRoot进行第一步。第三步：判断栈是否为空，如果不为空，则取出栈顶元素，并出栈，然后将栈顶元素的右结点赋给pRoot，然后进行第一步；如果pRoot为NULL并且栈空，则结束。void PreorderTraverse（ BTreeNode_t *pRoot）{
if（ pRoot == NULL ）
return ; stack <BTreeNode_t *> st;
while（ pRoot ！= NULL || ！st.empty（））{
while（ pRoot ！= NULL ）{
Visit（ pRoot ）;
st.push（ pRoot ）;
pRoot = pRoot->m_pLeft;
} if（！st.empty（））{
pRoot = st.top（）;
st.pop（）;
pRoot = pRoot->m_pRight;
}
} return;
} 二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-01/111633.htm