数据结构课程设计--二叉树的建立，层次，先序遍历

《数据结构课程设计--二叉树的建立，层次，先序遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计——二叉树的建立，层次、先序遍历系（院）:信息工程学院专业:计算机科学与技术班级:09级计科2班姓名:汪梦君学号:200910510232指导教师:李娟学年:2010~2011学年2011年6月28日摘要：本程序设计实现二叉树的层次遍历，该程序主要部分包括：创建二叉树，递归先序、中序、后序遍历二叉树，非递归先序、中序、后序二叉树和按层次遍历二叉树。关键词：二叉树，队列，二叉链表，先序遍历，中序遍历，后序遍历，层次遍历1.引言树型结构是一类重要的非线性数据结构，其中一树和二叉树最重要。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构够可以用

2、树来形象表示。树在计算机领域中也得到了广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。二叉树是一种非线性数据结构，对它进行操作时总需要对每个数据逐一进行操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作问题，所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程，这里的访问可以是输出.比较.更新.查看元素内容等各种操作。2.功能需求2.1行输入数据构造二叉树。2.2用队列存储二叉树结点。2.3算法实现遍历。3.数据结构设计3.1树的链式存储typedefstructBTNode/*树的链式存储*/{BitTreeElementTyped

3、ata;structBTNode*lchild;/*左孩子*/structBTNode*rchild;/*右孩子*/}BTnode,*BitTree;3.2队列定义QueueElemtypedata[QUEUESIZE];intfront;/*队列的头指针*/intrear;/*队列的尾指针*/}queue;4.算法设计4.1主函数模块main(){inti;b=NULL;charbt[20];for(i=0;i<20;i++)scanf("%c",&bt[i]);CreateBTNode(b,bt);printf("二叉树b:");DispBTNode(b);pri

4、ntf("");printf("层次遍历序列：");TravLevel(b);printf("");printf("先序遍历序列：");printf("");printf("递归算法：");Preorder(b);printf("");printf("非递归算法：");NPreorder(b);printf("");printf("中序遍历序列：");printf("");printf("递归算法：");Inorder(b);printf("");printf("非递归算法：");NInorder(b);printf("");print

5、f("后序遍历序列：");printf("");printf("递归算法：");Postorder(b);printf("");printf("非递归算法：");NPostorder(b);printf("");｝4.2初始化二叉树模块voidCreateBTNode(BTNode*b){为树指针T分配空间；输出“输入数据”；存储输入数据；if(出入数据==空字符){结点不存储信息；}else{结点存储输入的信息；输出“创建左子树”；CreateBTNode(&((*b)->lchild));输出“创建右子树”；CreateBTNode(&((*b)->r

6、child));}}4.3/***递归遍历二叉树***/先序遍历：voidPreOrder(BTNode*b){if(b!=NULL){访问根结点；先序遍历左子树；先序遍历右子树；}}中序遍历：voidInOrder(BTNode*b){if(b!=NULL){中序遍历左子树；访问根结点；中序遍历右子树；}}后序遍历：voidPostOrder(BTNode*b){if(b!=NULL){后序遍历左子树；后序遍历右子树；访问根结点；}}4.4/****非递归遍历*****/先序遍历：voidPreOrder1(BTNode*b){BTNode*St[MaxSize],

7、*p;inttop=-1;if(b!=NULL){根结点进栈；while(top>-1){p=St[top];top--;访问根结点；}if(p->rchild!=NULL){右孩子结点进栈；}if(p->lchild!=NULL){左孩子结点进栈；}}}}中序遍历：voidInOrder1(BTNode*b){BTNode*St[MaxSize],*p;inttop=-1;if(b!=NULL){p=b;while(top>-1

8、

9、p!=NULL){*p左子树孩子结点进栈；}if(top>-1){出栈*p结点；处理右孩子结点；}}}后序遍历：voi