test.cpp

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

#include "binarytree.h"                   // 关于二叉树的头文件

void InOrder_iter(BiTree, void(*)(BiTree)); // 待测试程序的说明 
 
/****************************** 测试主程序 **************************/
    
void main()                              
{
 BiTree T;
 Stack S;
 InitStack(S);
 cout<<"inputing data for CreateBiTree:"<<endl; 
 CreateBiTree(T);                         // 生成二叉树
 cout<<endl;
 cout<<"Preorder travel:"<<endl;
 Preorder(T,output);                      // 递归前序遍历该二叉树
 cout<<endl;
 cout<<"Inorder travel:"<<endl;
 Inorder(T,output);                       // 递归中序遍历该二叉树
 cout<<endl;
 cout<<"Preorder_iter travel:"<<endl;
 InOrder_iter(T, output);                 //非递归前序遍历该二叉树
 cout<<endl;
 cout<<"Bye bye!\n";
} //main


/****************************** 待测试程序的定义 **************************/
    
void InOrder_iter(BiTree BT, void(*visit)(BiTree))
{
	//利用栈实现中序遍历，BT为指向二叉树根结点的指针
    Stack S;                            // 栈说明
	BiTree  p;
    InitStack(S);                         // 栈初始化
	SElemType e;                          // 栈元素说明
	e.ptr=BT; e.task=Travel;              // 栈元素初值
	if(BT)Push(S,e);                      // 布置初试任务
	while(!StackEmpty(S))                 // 每次处理一项任务
	{
		Pop(S,e);   
		if(e.task==Visit) visit(e.ptr);   // 处理访问任务
		else if(e.ptr){                   // 处理非空树的遍历任务
			    p=e.ptr;
				e.ptr=p->rchild;                Push(S,e);//最不迫切任务（遍历右子树）进栈
				e.ptr=p;         e.task=Visit;  Push(S,e);//处理访问任务的工作状态进栈
                e.ptr=p->lchild; e.task=Travel; Push(S,e);//当前最迫切任务（遍历左子树）进栈
			  }//if
	}//while
}//InOrder_iter