二叉树的生成和遍历.docx

《二叉树的生成和遍历.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计报告———二叉树的生成和遍历专业信息管理与信息系统班级110514小组成员110514128汤文莹110514129王玉珏110514130张蓓蕾110514131张慕琦课程设计：二叉树的生成和遍历一、任务描述1.将二叉树以广义表形式存储在一个TXT文件上，通过读取TXT文件，建立二叉树；2.求树的高度3.实现二叉树的前序、中序和后序遍历；4.将输出结果存储在文件内。二、问题分析1.设计思想以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链表树；通过先、中、后访问根结点递归算法遍历二叉树；

2、利用队列的入队、出队操作实现二叉树的层次遍历。例如：a(c(,d)，f(g,))建立如下图所示二叉树。cadfg2.数据结构定义队列数组长度#defineQueueMaxSize20定义栈数组长度#defineStackMaxSize10定义二叉树数据类型typedefcharElemType;structBTreeNode{ElemTypedata;structBTreeNode*left;structBTreeNode*right;}BTreeNode;3.主要模块设计初始化二叉树voidInitBTree(structBT

3、reeNode**BT)根据a所定义的二叉树广义表字符串建立对应的存储结构voidCreateBTree(structBTreeNode**BT,char*a)前序遍历二叉树voidPreorder(structBTreeNode*BT){if(BT!=NULL){printf("%c",BT->data);/*访问根结点*/Preorder(BT->left);/*前序遍历左子树*/Preorder(BT->right);/*前序遍历右子树*/}}中序遍历二叉树voidInorder(structBTreeNode*BT){i

4、f(BT!=NULL){Inorder(BT->left);/*中序遍历左子树*/printf("%c",BT->data);/*访问根结点*/Inorder(BT->right);/*中序遍历右子树*/}}后序遍历二叉树voidPostorder(structBTreeNode*BT){if(BT!=NULL){Postorder(BT->left);/*后序遍历左子树*/Postorder(BT->right);/*后序遍历右子树*/printf("%c",BT->data);/*访问根结点*/}}由指针指向的一颗二叉树的深

5、度intBTreeDepth(structBTreeNode*BT)按层遍历由BT指针所指向的二叉树voidLevelorder(structBTreeNode*BT中序遍历二叉树深度主菜单先序遍历后序遍历广度优先遍历结束将以广义表形式输入的二叉树接收到数组str[80]中，成功建立二叉树4.详细设计1）二叉树的建立其中mark的值1、2、3、4分别指str[i]为字母、‘(’、‘，’、‘)’；tag为左、右孩子的标志；root=null检查str[1~’’]‘(’‘)’‘，’‘mark=1；root->data=str[0

6、],root->lchild=root->rchild=null;p=root;str[0]是否为字母YNNmark==2?mark=2str[i]入栈tag=0mark==3?mark=3tag=1Nmark=4pop为空returnnullNYY‘)’‘mark==1&&栈不空新建结点pp->data=str[i]p->lchild=p->rchild=nulltag==0?'循环结束后returnroot栈顶->rchild=p栈顶->lchild=pYN2.二叉树的层次遍历访问元素所指结点，若该元素所指结点的左右孩子结点

7、非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。初始化队列，root入队队列非空出队p；打印p->dataYp->lchild!=nullYp->lchild入队p->lchild!=nullNYNp->rchild入队结束N函数实现#include#include#defineQueueMaxSize20/*定义队列数组长度*/#defineStackMaxSize10/*定义栈数组长度*/typedefcharElemType;structBTreeNode{ElemTypeda

8、ta;structBTreeNode*left;structBTreeNode*right;}BTreeNode;voidInitBTree(structBTreeNode**BT)/*初始化二叉树，即把树根指针置空*/{*BT=NULL;}voidCreate