一,简介
二叉树的中序遍历在计算机行业有着重要的作用,其中一个应用就是判断一棵二叉树是否二叉排序树。
下面介绍递归和非递归两种方式实现中序遍历。
二,递归实现
递归实现非常简单,左根右依次进行即可。
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;
}
运行结果: