binarytree.cpp

数据结构各种算法原代码及图形示例

/***************************  头文件及类型定义 ************************/
#include "common.h"                        // 共同头文件

typedef char TElemType;                    // 树结点数据域暂且为字符类型

typedef enum {Travel=1, Visit=0}TaskType;  // 任务状态类型

typedef struct BiTNode{                    // 二叉树的类型定义 
   TElemType    data;
   struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef struct {                           // 栈元素由指向二叉树结点的指针及任务状态构成
	BiTree ptr;
	TaskType task;
} SElemType;

#include "stack.h"                         // 栈类型的头文件


/*************************** 封装输入数据的操作 ***********************/

 
TElemType Getdata()                        
{
    TElemType data;
    cin>>data;
    return data;
} //Getdata

/************************** 二叉树类型的相关操作 **********************/

 
status CreateBiTree(BiTree &T)             // 输入前序序列,以#作空结点标志
{                                          // 递归生成二叉树
	char ch;
	ch=Getdata();                          // 输入数据,例如AB#C##D##
    if (ch == '#')T = NULL;                 
    else {
             if (!(T = new BiTNode))       
                 return ERROR;
             T->data = ch;                 // 生成当前树的根结点
             CreateBiTree(T->lchild);      // 递归构造左子树
             CreateBiTree(T->rchild);      // 递归构造右子树
	     }
    return OK;
} //CreateBiTree
 
// 作为被visit导入的指针函数 
void output(BiTree p)                  
{
	cout<<p->data<<",";
} // output

void Preorder(BiTree T, void(*visit)(BiTree))
{                                         // 前序递归遍历二叉树并输出结点 
   if (T) {
      visit(T);                           // 访问结点
      Preorder(T->lchild, visit);         // 递归遍历左子树
      Preorder(T->rchild, visit);         // 递归遍历右子树
   }
} //Preorder

void Inorder(BiTree T, void(*visit)(BiTree))
{                                         // 前序递归遍历二叉树并输出结点 
   if (T) {
     
      Inorder(T->lchild, visit);          // 递归遍历左子树
	  visit(T);                           // 访问结点
      Inorder(T->rchild, visit);          // 递归遍历右子树
   }
} //Preorder

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


/****************************** 测试程序 ******************************/
     
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