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

1、精选优质文档-倾情为你奉上#include<stdio.h>#include<stdlib.h>#include<process.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;

2、typedef BiTree QElemType; #include"LinkQueue.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=(

3、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->

4、data); / 先访问根结点 PreOrderTraverse(T->lchild ); / 再先序遍历左子树 PreOrderTraverse(T->rchild); / 最后先序遍历右子树 void InOrderTraverse(BiTree T) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数 / 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) InOrderTraverse(T->lchild); / 先中序遍历左子树 printf("%c",(T->data); / 再访问根结点 InOrd

5、erTraverse(T->rchild); / 最后中序遍历右子树 void PostOrderTraverse(BiTree T) / 初始条件：二叉树T存在，Visit是对结点操作的应用函数 / 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) PostOrderTraverse(T->lchild); / 先后序遍历左子树 PostOrderTraverse(T->rchild); / 最后后序遍历右子树 printf("%c",(T->data); / 再访问根结点 void LevelOrderTravers

6、e(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有左孩

7、子 EnQueue(q,a->lchild); / 入队a的左孩子 if(a->rchild!=NULL) / a有右孩子 EnQueue(q,a->rchild); / 入队a的右孩子 printf("n"); void main() BiTree T;printf("按先序顺序输入二叉树中结点的值，#代表空n"); CreateBiTree(T); printf("先序遍历二叉树结果为："); PreOrderTraverse(T); printf("n中序遍历二叉树的结果为："); InOrderTraverse(T); printf("n后序