二叉树的各种遍历的实现(程序已测试).doc

#includestdio.h #includestdlib.h #includeprocess.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; BiTNode *lchild,*rchild; // 左右孩子指针 }BiTNode,*BiTree; typedef BiTree QElemType; #includeLinkQueue.h void Visit(TElemType e) { printf(%c,e); } void CreateBiTree(BiTree T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)， // 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。有改动 TElemType ch; scanf(%c,ch); if(ch==#) // 空 T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点 if(!T) exit(OVERFLOW); T-data=ch; CreateBiTree(T-lchild); // 构造左子树 CreateBiTree(T-rchild); // 构造右子树 } } void PreOrderTraverse(BiTree T ) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。算法6.1，有改动 // 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) // T不空 { printf(%c,(T-data)); // 先访问根结点 PreOrderTraverse(T-lchild ); // 再先序遍历左子树 PreOrderTraverse(T-rchild); // 最后先序遍历右子树 } } void InOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { InOrderTraverse(T-lchild); // 先中序遍历左子树 printf(%c,(T-data)); // 再访问根结点 InOrderTraverse(T-rchild); // 最后中序遍历右子树 } } void PostOrderTraverse(BiTree T) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { PostOrderTraverse(T-lchild); // 先后序遍历左子树 PostOrderTraverse(T-rchild); // 最后后序遍历右子树 printf(%c,(T-data)); // 再访问根结点 } } void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：层序递归遍历T(利用队列)，对每个结点调用函数Visit一次且仅一次 LinkQueue q; QElemType a; if(T) { InitQueue(q); // 初始化队列q EnQueue(q,T); // 根指针入队 while(!QueueEmpty(q)) // 队列不空 { DeQueue(q,a); // 出队元素(指针),赋给a Visit(a-data); // 访问a所指结点 if(a-lchild!=NULL) // a有左孩子 EnQueue(q,a-lchild); // 入队a的左孩子 if(a-rchild!=NULL) // a有右