2025年二叉树遍历算法实践与数据结构深度解析教程

题目：二叉树的遍历和子树互换需求分析a)中序递归遍历算法、前序递归遍历算法【选】b)中序遍历非递归算法c)先序或后序遍历非递归算法d)建立中序线索，并进行中序遍历和反中序遍历6.设计一种测试用的二叉树并创立对应的内存二叉树，可以测试自己算法的边界(包括树节点数为0、1以及>1的不一样情形)。概要设计阐明：本程序在递归调用中用到了链表，在操作成果：若S为空栈，则返回OK,否则返回ERROR。操作成果：删除S的栈顶元素，并用e返回其值。}数据对象D:D是具有相似特性的数据元素的集合。数据关系R:若D≠φ,则R={H},H是如下二元关系；(2)若D-{root}≠φ,则存在D-{root}={D1(3)若Dl≠φ,则D1中存在惟一的元素x1,<root,x1>∈H,且存在D1上的关系H1SH;若Dr≠D,则Dr且存在上的关系HrEH;H={<root,x1>,<root,xr>,H1,Hr};操作成果：按规定构造二叉树T。PreOrderTraverse_re操作成果：先序递归遍历T,对每个结点调用函数print一次且仅一次。一操作成果：中序非递归遍历T,对每个结点调用函数print一次且仅一次。InOrderTraverse_re(操作成果：中序递归遍历T,对每个结点调用函数print一次且仅一次。一操作成果：先序非递归遍历T,对每个结点调用函数print一次且仅一次。操作成果：分层遍历二叉树T,并输出。InOrderTraverse_Thr(初始条件：二叉树T在在。操作成果：中序非递归遍历二叉线索树T初始条件：结点p在在。操作成果：结点p及子树线索化。{}4.本程序包括三个模块1)主程序模块{接受命令；}}2)链表模块。递归调用时实现链表抽象数据类型。3)栈模块。非递归调用时实现栈的抽象数据类型。1.宏定义及全局变量#defineTElemType#defineERROR0BiThrTreepre;intCreateBiTree(BiTree&voidInOrderTraverse(BiTreeT,int(*print)(TElemTypee);//中序非递归遍历二叉树voidInOrderTraverse_re(BiTreeT,int(*print)(TElemTypeevoidPreOrderTraverse(BiTreeT,int(*print)(TElemTypee));//先序非递归遍历二叉树voidInOrderThreading(BiThrTree&Thrt,BiThrTreintInOrderTraverse_Thr(BiThrTreeT,int(*print)(TEvoidInThreading(BiThrTreep);typedefstructBiTNode{PointerTagLTag,RTag;a)构造二叉树T{{if(!(T=(BiTNode*)malloc(sizeof(if(CreateBiTree(T->lchild))T->LTag=Link;if(CreateBiTree(T->rchild))T->RTag=Link;}}b)先序递归遍历二叉数T,并输出所有结点值。voidPreOrderTraverse_re(BiTreeT,i{{PreOrderTraverse_re(T->lchildPreOrderTraverse_re(T->rchild}}c)中序非递归遍历二叉树T,并输出所有结点值voidInOrderTraverse(BiTreeT,i{{}}d)中序递归遍历二叉树T,并输出所有结点值voidInOrderTraverse_re(BiTreeT,int(*print)(TE{InOrderTraverse_re(T->lchiInOrderTraverse_re(T->rchil}e)中序遍历二叉树T,并将其中序线索化，Thrt指向头结点Thrt=(BiThrTree)malloc(sizeof(Thrt->LTag=Link;//建头结点f)结点p线索化InThreading(p->lchild);//左子树线索化if(!p->lchild)//建前驱线索if(!pre->rchild)//建后继线索pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化intInOrderTraverse_Thr(BiThrwhile(p->RTag==Thread&}}typedefstruct{a)创立一种空栈{S.base=(SElemType*)malloc(STACK_INIT_SIZE}b)栈顶插入元素{if(S.top-S.base>=S.S.base=(SElemType*)realloc(S.base,(STACK_INIT_c)栈顶删除元素}d)判断栈与否为空栈{}printf("*************************:**********************\n"printf("**试验12二叉树的遍历**\n");printf("**1.实现二叉树的不一样遍历算法和二叉树的中序线索化算法**\n");printf("**c)printf("**d)先序或后序遍历非递归算法之一；**\n"):printf("**e)建立中序线运用线索进行中序遍历和反中序遍历。**\n");printf("**2.实现二叉树的按层遍历算法。**\n");printf("**********************************************************\n"printf("\n选择操作：\n\t1.先序与中序遍历算法\n\t2.中序线索的中序遍历和反中序遍printf("前序递归创立二叉树(空格表达此结点为空):\n");InOrderTraverse_re(printf("\n前序递归遍历输出：");PreOrderTraverse_re(T,printf("\n中序非递归遍历输出：");printf("\n前序非递归遍历输出：");PreOrderTraverse(T,case2:printf("前序递归创立二叉树(空格表达此结点为空):\n");InOrderTraverse_Thr(Thrcase3:printf("前序递归创立二叉树(空格表达此结点为空):\n");printf("\n按层遍历输出：");6.函数间调用关系作调试分析C:\C:\Users\dudu\Desktop\我的学习资料\第二学期数据结构\作业实验报告二\Debug\BiTree.ex.口回实验12_二叉树的遍历**1.实现二又树的不同遍历算法和二叉树的中序线索化算法**中序递归遍历算法；先序递归遍历算法：中序遍历的非递归算法先序或后序遍历非递归算法之一；**e)建立中序线利用线索进行中序遍历和反中序遍历。**2.实现二叉树的按层遍历算法。选择操作：1.先序与虫序遍历算法2.中序线索的中序遍历和反中序遍历算法3.按层遍历算法三X1.顾客需根据顾客提醒信息操作，输入二叉树(以空格表达空结点),输入完毕后按回车键，C:\C:\Users\dudu\Desktop\我的学习资料\第二学期数据结构\作业\实验报告二\Debug\BiTree.ex..**1.实现二叉树的不同遍历算法和二叉树的中序线索化算法先序或启**e)建立中序线利用线索进行中序遍历和反中序遍历。**2.买现二叉树的按层遍历算法。*W***KN*K**N*KK*W**前序递归创建二叉树(空格表示此结点为空):+a*h-cd-ef中序递归遍历输出：a+b*c-d前序递归遍历输出：+a*b-cd前序非递归遍历输出：+a*b-cd按层遍历输出：+a*h-cd按任意键退出…Pressanykeytocontinue一中序递归遍历输出：a+b*c-d前序递归遍历输出：+a*b-cd前序非递归遍历输出：+a*b-cd按层遍历输出：+a*b-cd七、附录#defineQElemTypeBiTNodetypedefstructBiTNode{structBiTNode*#defineQElemTypeBiTNode#defineSElemTypetypedefstruct{BiThrTreepre;intCreateBiTree(BiTree&T);voidPreOrderTraverse_re(BiTreeT,void(*print)(TElemTypee);//先序递归遍历二叉树voidInOrderTraverse(BiTreeT,int(*print)(TElemTypee));//中序非递归遍历二叉树voidInOrderTraverse_re(BiTreeT,int(*print)(TElemTypee));//中序递归遍历二叉树voidPreOrderTraverse(BiTreeT,int(*print)(TElemTypee));//先序非递归遍历二叉树intprint(TElemTypee);voidInitStack(SqStack&S);voidPop(SqStack&S,SElemType&e);voidPush(SqStack&S,SElemType&e);voidInOrderThreading(BiThrTintInOrderTraverse_Thr(BiThrTreeT,int(*print)(TElemTypee));voidInThreading(BiT/*二叉树的创立递归创立*/intCreateBiTree(B{if(CreateBiTree(T->lchild))T->LTag=Link;if(CreateBiTree(T->rchild))T->RTag=Link;}/************************************/*先序递归遍历输出*//************************************voidPreOrderTraverse_re(BiTreeT,int(*print)(TElemTypee))PreOrderTraverse_re(T->lchPreOrderTraverse_re(T->rchild,}}/*************************************/*中序非递归遍历输出*//*************************************voidInOrderTraverse(BiTreeT,int(*print)(TElemType{}/*******************:******************/*中序递归遍历输出*//*************************************voidInOrderTraverse_re(BiTreeT,int(*print)(TEle{InOrderTraverse_re(T->lchildInOrderTraverse_re(T->rchild}}/************************************/*按照前序非递归遍历二叉树：栈*//************************************SElemTypep=T;/p指向目前访问的结点while(pl!StackEmpty{}{}}voidInOrderThreading(BiThr//中序遍历二叉树T,并将其中序线索化，Thrt指向头结点Thrt=(BiThrTree)malloc(sizeThrt->LTag=Link;//建头结点Thrt->rchild=Thrt;//右指针回指{pre->RTag=Thread;/最终一种结点线索化}voidInThreading(BiTInThreading(p->lchild);//左子树线索化if(!p->lchild)//建前驱线索if(!pre->rchild)//建后继线索pre=p;InThreading(p->rchild);//右子树线索化}intInOrderTraverse_Thr(BiThrT{while(p->RTag==Thread&&p->rc}}}/***************************如下为辅助函数***************************************/{}/*栈的初始化*/voidInitStack(SqStack&S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*s}voidPush(SqStack&S,SElemif(S.top-S.base>=S.s{S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMEN}}voidPop(SqStack&S,SElemType&e){{/*若栈为空栈，则返回OK,否则返回ERROR*/}intGetTop(SqStack{/******************************************************/*按层次次序建立一棵二叉树*//*******************************************************voidLevelorder(BiTreeT)}BiTNode*q[20],*p;/*q[20]用于模拟队列，存储入队的结点*/}/*i为队首位置，j为队尾位置*/if(p->lchild!=NULL)j++;}/*若队首元素左链域不为空，则将其入队列*/if(p->rchild!=NULL){j++;}/*若队首元素右链域不为空，则将其入队列*/i++;/*将队首移到下一种位置*/{printf("***********************************************************\n");printf("**试验12二叉树的遍历**\n");printf("**1.实现二叉树的不一样遍历算法和二叉树的中序线索化算法**\n");printf("**a)中序递归遍历算法；printf("**b)先序递归遍历算法