一，简介

二叉树的中序遍历在计算机行业有着重要的作用，其中一个应用就是判断一棵二叉树是否二叉排序树。

下面介绍递归和非递归两种方式实现中序遍历。

二，递归实现

递归实现非常简单，左根右依次进行即可。

void mid_scan2(node* now)
{if(now->left != NULL)mid_scan2(now->left);cout<<now->num<<",";if(now->right != NULL)mid_scan2(now->right);
}

三，非递归实现

约定：

如果当前二叉树的某个结点没有左(右)孩子，那么该结点的左(右)孩子为NULL。

指针指向的结点，被称为当前结点。

1，实现思路

（1）如果根节点为空，则退出函数，否则将当前指针指向根节点，并进行以下的步骤：

（2）如果当前结点非空，将当前元素压栈，指针向左孩子。循环该步骤直至指针指空。

（3）如果当前指针指空，则：

a,退栈，将指针指向退栈出来的元素，输出这个元素的数据。

b,判断当前结点的右子树是否为空。

b(1) 如果非空，则指针指向当前结点的右孩子，跳转到步骤（2）

b(2)如果为空，退栈，将指针指向退栈出来的元素，输出这个元素的数据。

b(2-2)让指针指向当前结点右子树根结点。

（4）重复执行以上操作。

2，具体代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
typedef struct node0{ int num;node0* left;node0* right;
}node;void layer_scan(node* head,int n)//层次遍历 ，用来验证二叉排序树的生成是否成功 
{cout<<"层次遍历的结果:"<<endl; node* queue = (node*)malloc(sizeof(node)*(n+1));//层次遍历所需队列 int size = n+1;int i;int front=0,rear=0;//队空时，front和rear相等；队满时rear的下一个就是front//node* now = (node*)malloc(sizeof(node));queue[rear++] = *head;while(front != rear) {if(queue[front].left != NULL){queue[rear] = *(queue[front].left);rear = (rear + 1)%size;}if(queue[front].right != NULL){queue[rear] = *(queue[front].right);rear = (rear + 1)%size;}cout<<queue[front].num<<",";front = (front + 1)%size;}cout<<endl;
}int* mid_scan(node* head,int n)//中序非递归遍历，并将遍历顺序存储在数组中然后返回 
{cout<<"中序非递归遍历的结果是："<<endl; if(head == NULL){cout<<"该树为空!"<<endl;return NULL; }int* result = (int*)malloc(sizeof(int)*(n+1));//存储结果的栈 node* stack = (node*)malloc(sizeof(node)*(n+1));//实现非递归遍历的栈 int top=0;//stack的栈顶指针 int top2=0;//result的栈顶指针 node* now;//当前指针 now = head;//初始化当前指针 while(top>=0){while(now != NULL)//当前指针非空，那么就入栈，向左子树前进 {stack[top++] = *now;now = now->left;}top--;if(top<0)return result;now = &stack[top] ;//出栈，并让当前指针指向出栈的元素 cout<<now->num<<",";result[top2++] = now->num;if(now->right != NULL)//右子树非空就往右前进一步，然后continue {now = now->right;continue;}else{top--;if(top<0)return result;now = &stack[top] ;cout<<now->num<<",";result[top2++] = now->num;now = now->right;}}return result;
}
void mid_scan2(node* now)//中序递归遍历算法 
{if(now->left != NULL)mid_scan2(now->left);cout<<now->num<<",";if(now->right != NULL)mid_scan2(now->right);
}
node* BST_tree(int n)//建立一颗二叉排序树，该二叉树的结点个数为n，结点的值是随机的.
{//中序遍历二叉排序树的结果序列是一个有序序列,该函数最后返回该二叉排序树的根结点指针 node* head;//根结点指针 node* now; int i,num;srand(time(0));//随机改变下面的随机种子 for(i=0;i<n;i++){num = rand() % (n*n);node* p = (node*)malloc(sizeof(node));p->num = num;//cout<<num<<",";if(i==0) {head = p;head->left = NULL;head->right = NULL;}now = head;while(now->left!=NULL || now->right!=NULL)//未到达叶子结点时 {if(p->num > now->num){if(now->right == NULL)break;now = now->right;}else {if(now->left == NULL)break;now = now->left;}}if(p->num > now->num)//该if-else语句用来实现新结点在当前叶子结点的插入 now->right = p;else now->left  = p;p->left = NULL;p->right = NULL;}cout<<endl;return head;//返回根结点指针 
}void question_285_06()//验证答案 
{int n,i;node* head;int* mid_serial;//接收中序非递归遍历序列 n=10;head = BST_tree(n);//生成二叉排序树 cout<<"层次遍历，验证二叉排序树，"; layer_scan( head, n);//层次遍历，验证二叉排序树的生成是 cout<<"中序递归遍历的结果是:"<<endl;mid_scan2(head);//中序递归遍历 cout<<endl;mid_serial = mid_scan( head, n);//中序非递归遍历序列 cout<<endl;cout<<"mid_serial数组中的内容是:"<<endl;for(i=0;i<n;i++)cout<< *(mid_serial+i)<<",";cout<<endl;
}
int main()
{question_285_06();return 0;
}

运行结果：