2022年数据结构课程方案二叉树遍历.docx

《2022年数据结构课程方案二叉树遍历.docx》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案二叉树遍历.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用数据结构课程设计报告题目： 二叉树的遍历 日期： 2022-12-22 年级：班级：姓名：学号：一实习目的 更好的明白二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍 历算法的实现流程及操作步骤；加深理论学问,提高实践才能；二问题描述 二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的 实现,建树的实现；三概要设计 1.创建二叉树 2.二叉树的递归遍历算法 前、中、后）3.二叉树的层次遍历算法 4.二叉树的非递归遍历算法 定义二叉树结点值的类型为字符型；2结点个数不超过 10 个；

2、3按先序次序输入,构造二叉链表表示的二叉树 T,空格表示空树；2.二叉树的递归遍历算法 拜访根结点；2先序遍历根结点的左子数；3先序遍历根结点的右子数；LDR 1先序遍历根结点的左子数；2拜访根结点；3先序遍历根结点的右子数；名师归纳总结 - - - - - - -第 1 页,共 8 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用LRD 1先序遍历根结点的左子数；2先序遍历根结点的右子数；3拜访根结点；3.二叉树的层次遍历算法 1 拜访该元素所指结点；2 如该元素所指结点的左右孩子结点非空,就该元素所指结点的左孩子指针和右孩子指 针次序入队；4.二叉树的非递归遍

3、历算法 前、中、后）1）非递归的先序遍历算法 a.拜访结点的数据域；b.指针指向 p 的左孩子结点；c.从栈中弹出栈顶元素；d.指针指向 p 的右孩子结点；2）非递归的中序遍历算法 a.指针指向 p 的左孩子结点；b.从栈中弹出栈顶元素；c.拜访结点的数据域；d.指针指向 p 的右孩子结点；第一将 bt 和 tag为 1入栈,遍历左子树；返回后,修改栈顶 tag为 2,遍历右子树；最终拜访根结点；5.退出 五测试数据与分析a d b e f c g 名师归纳总结 - - - - - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - 名师归纳总结 个人资料整理仅限学习

4、使用第 3 页,共 8 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用六源代码 #include iostream.h #include stdlib.h #include stdio.h typedef char ElemType ；/定义二叉树结点值的类型为字符型 const int MaxLength=10 ；/结点个数不超过 10 个typedef struct BTNode ElemType data； struct BTNode *lchild,*rchild；BTNode,* BiTree ；void CreateBiTr

5、eeBiTree &T/按先序次序输入,构造二叉链表表示的二叉树T,空格表示空树/ ifT return ； char ch； ch=getchar ； /不能用 cin 来输入,在 cin 中不能识别空格； ifch= T=NULL； else ； if.T=BTNode *mallocsizeofBTNode coutdata=ch； CreateBiTreeT-lchild ； CreateBiTreeT-rchild ； void PreOrderTraverseBiTree T/ 先序遍历 ifT coutdatalchild ； PreOrderTraverseT-rchild ；

6、 中序遍历 void InOrderTraverseBiTree T/ ifT 名师归纳总结 - - - - - - -第 4 页,共 8 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 InOrderTraverseT-lchild ； coutdatarchild ； void PostOrderTraverseBiTree T/ 后序遍历 ifT PostOrderTraverseT-lchild ； PostOrderTraverseT-rchild ； coutdata/ 层序遍历 BiTree QMaxLength ； int front=0,rea

7、r=0 ； BiTree p ； ifT / 根结点入队 Qrear=T ； rear=rear+1%MaxLength ； whilefront.=rear p=Qfront ； /队头元素出队 front=front+1%MaxLength； coutdatalchild / 左孩子不为空,入队 Qrear=p-lchild ； rear=rear+1%MaxLength ； ifp-rchild / 右孩子不为空,入队 Qrear=p-rchild ； rear=rear+1%MaxLength ； /非递归的先序遍历算法 void NRPreOrderBiTree bt BiTree

8、stackMaxLength,p； int top ； if bt.=NULL top=0；p=bt； whilep.=NULL|top0 whilep.=NULL 名师归纳总结 - - - - - - -第 5 页,共 8 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 coutdata； stacktop=p ； top+ ； p=p-lchild ； if top0 top- ； p=stacktop ； p=p-rchild ； /非递归的中序遍历算法 void NRInOrderBiTree bt BiTree stackMaxLength,p； in

9、t top ； if bt.=NULL top=0；p=bt； whilep.=NULL|top0 whilep.=NULL stacktop=p ； top+ ； p=p-lchild ； if top0 top- ； p=stacktop ；coutdata ； p=p-rchild ； /非递归的后序遍历算法 typedef struct BiTree ptr ； int tag；stacknode；void NRPostOrderBiTree bt stacknode sMaxLength,x ； BiTree p=bt ； int top ； ifbt.=NULL top=0；p=b

10、t；名师归纳总结 - - - - - - -第 6 页,共 8 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 do while p.=NULL / 遍历左子树 stop.ptr = p ； stop.tag = 1 ； /标记为左子树 top+ ； p=p-lchild ； while top0 & stop-1.tag=2 x = s-top ； p = x.ptr ； coutdata ； /tag 为 R,表示右子树拜访完毕,故拜访根结点 if top0 stop-1.tag =2 ； /遍历右子树 p=stop-1.ptr-rchild ； while

11、 top0 ； /PostOrderUnrec void main BiTree T ； T=NULL ； int select； /cout: ； while1 coutnn 请挑选要执行的操作 :n； cout1. 创建二叉树 n； cout2. 二叉树的递归遍历算法 前、中、后） n；n； cout3. 二叉树的层次遍历算法 cout4. 二叉树的非递归遍历算法 前、中、后） n；coutselect ； switchselect case 0:return； case 1: cout: ；名师归纳总结 - - - - - - -第 7 页,共 8 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 break； case 2: if.T cout 未建立树,请先建树！； else cout； cout ； cout； break； case 3: cout ； break； case 4: if.T cout 未建立树,请先建树！； else cout ； cout ； cout ； break； default: cout 请确认挑选项 :n ； /end switch /end while 名师归纳总结 - - - - - - -第 8 页,共 8 页