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 ? 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;
}

?