binarytree.h

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

/***************************  头文件及类型定义 ************************/
#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


/*********************** 作为被visit导入的指针函数 *******************/

void output(BiTree p)                  
{
	cout<<p->data<<",";
} // output


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

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
 
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);          // 递归遍历右子树
   }
} //Ineorder