# 数据结构与算法： C语言实现 前/中/后序的递归/非递归遍历

### 1.递归遍历

##### 1.1前序遍历
``````void preOrderTraverse(BSTreeNode *root)
{
if (root != NULL)
{
printf("%d \n", root->data);
preOrderTraverse(root->left);
preOrderTraverse(root->right);
}
}``````
##### 1.2中序遍历
``````void InOrderTraverse(BSTreeNode *root)
{
if (root != NULL)
{
InOrderTraverse(root->left);
printf("%d \n", root->data);
InOrderTraverse(root->right);
}
}``````
##### 1.3后序遍历
``````void PostOrderTraverse(BSTreeNode *root)
{
if (root != NULL)
{
PostOrderTraverse(root->left);
PostOrderTraverse(root->right);
printf("%d \n", root->data);
}
}``````

### 2.非递归遍历

##### 2.1前序遍历
``````void preOrderTraverseNR(BSTreeNode *root)
{
//建立栈
Stack = initStack();
while(NULL != root){
printf("%d \n", root->data);
if (NULL != root->right)
{
push(Stack, root->right);
}
if (NULL != root->left)
{
push(Stack, root->left);
}
root = pop(Stack);
}
free(Stack);
Stack = NULL;
}``````

ok，继续

##### 2.2中序遍历
``````void InOrderTraverseNR(BSTreeNode *root)
{
//建立栈
Stack = initStack();
while(NULL != root || Stack->size > 0){
if (root != NULL)
{
push(Stack, root);
root = root->left;
}else{
root = pop(Stack);
printf("%d \n", root->data);
root = root->right;
}
}
free(Stack);
Stack = NULL;
}``````
##### 2.3后序遍历
``````void PostOrderTraverseNR(BSTreeNode *root)
{
//建立栈
Stack    = initStack();
StackTmp = initStack();
while(NULL != root || StackTmp->size > 0){
while (root != NULL)
{
push(Stack, root);
push(StackTmp, root);
root = root->right;
}
if (StackTmp->size > 0)
{
root = pop(StackTmp);
root = root->left;
}
}
while(Stack->size > 0){
root = pop(Stack);
printf("%d \n", root->data);
}
free(Stack);
free(StackTmp);
Stack = NULL;
StackTmp = NULL;
}``````