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 InorderTraverse( BTreeNode_t *pRoot){
if( pRoot == NULL )
return ;
InorderTraverse( pRoot->m_pLeft);
Visiste( pRoot );
InorderTraverse( pRoot->m_pRight);
}
（2）非递归实现
第一步：给定根节点pRoot，判断pRoot是否为空，如果不为空，然后进行第二步；如果为空，则进行第三步；
第二步：将pRoot入栈，将pRoot的左结点赋给pRoot，然后进行第一步；
第三步：判断栈是否为空；如果为空，则结束，如果不为空，则取出栈顶元素给pRoot，并出栈，访问pRoot，然后将pRoot的右结点赋给pRoot，然后进行第一步。
void InorderTraverse( BTreeNode_t *pRoot){
if( pRoot == NULL )
return ;
stack < BTreeNode_t *> st;
while( pRoot != NULL || !st.empty() ){
while( pRoot != NULL ){
st.push( pRoot);
pRoot = pRoot->m_pLeft;
}
if( !st.empty() ){
pRoot = st.top();
st.pop();
Visit( pRoot );
pRoot = pRoot->m_pRight;
}
}
return;
}
在Java中实现的二叉树结构