二叉树的遍历

目录一、设计思想……………………………………………………….01二、算法流程图…………………………………………………….01三、源代码………………………………………………………….04四、运行结果……………………………………………………….08五、遇到的问题及解决…………………………………………….09六、心得体会……………………………………………………….10一、设计思想遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。二、算法流程图下图是定义的二叉树的结构图图1二叉树结构图下图是递归算法的流程图，首先的到当前根结点，判断结点指针是否空，如果非空，判断左子指针是否为空，非空则指向左子，左子作为当前根结点，空则判断右子指针是否为空，非空则指向右子，右子作为当前根结点，如果空，输出相应的数据，结束递归。图2递归算法流程图ABCDEGF下图是非递归算法先序遍历的算法流程图，首先对结点指针进行判断，如果指针不为空，结点指针入栈，输出数据，指针指向左子，访问左子树，如果结点指针为空，栈顶结点指针出栈，指针指向右子，访问右子树，直至遍历整个二叉树。图3非递归先序遍历算法流程图下图是非递归中序遍历算法流程图，首先对结点指针进行判断，如果指针不为空，则指针入栈，指针指向其左子，对左子树进行访问，如果结点指针为空，栈顶结点指针出栈，输出相应的数据，指针指向右子，对右子树进行访问，直至遍历整个二叉树。图4非递归中序遍历算法流程图、下图是非递归后序遍历二叉树算法流程图，首先对结点指针进行判断，如果指针不为空，结点指针和相应的标志位同时入栈，指针指向左子，对左子树进行遍历，如果指针为空，栈顶指针和相应的标志位同时出栈，如果标志位的值为0，则结点再次入栈，标志位置1，随之入栈，指针指向右子，访问右子树，如果标志位的值为1，输出相应结点的数据，并将结点指针置为NULL，直至遍历结束。图5非递归后序遍历算法流程图三、源代码#include#defineMAX100//表示栈的最大容量#defineFULL99//表示栈满#defineEMPTY-1//表示栈空typedefstructTnode//定义结点{chardata;//存储结点数据structTnode*left;//定义结点左子指针structTnode*right;//定义右子指针}Tnode,*Pnode;//声明Tnode类型的变量和指针typedefstructStack//定义栈{Pnodepnode[MAX];//存放数据intp;//栈顶指针}Stack,*Pstack;//定义Stack类型的变量和指针voidPush(Pstackpstack,Pnodepnode)//入栈{pstack-p++;pstack-pnode[pstack-p]=pnode;//赋值}PnodePop(Pstackpstack)//出栈{returnpstack-pnode[pstack-p--];}PnodeTop(Pstackpstack)//看栈顶元素{returnpstack-pnode[pstack-p];}intIsempty(Pstackpstack)//栈判空{if(pstack-p==EMPTY)return1;elsereturn0;;}intIsfull(Pstackpstack)//栈满{if(pstack-p==FULL)return1;elsereturn0;}voidInitstack(Pstackpstack)//初始化栈{pstack-p=EMPTY;}voidInittnode(Pnoderoot,Pnodeleft,Pnoderight,chardata)//初始化结点{root-left=left;root-right=right;root-data=data;}voidPreorderR(Pnodeproot)//递归先序遍历算法{if(proot){printf(%2c,proot-data);PreorderR(proot-left);PreorderR(proot-right);}}voidInorderR(Pnodeproot)//递归中序遍历算法{if(proot){InorderR(proot-left);printf(%2c,proot-data);InorderR(proot-right);}}voidPostorderR(Pnodeproot)//递归后序遍历算法{if(proot){PostorderR(proot-left);PostorderR(proot-right);printf(%2c,proot-data);}}voidPreorderI(Pnodeproot,Pstackpstack)//非递归先序遍历算法{Initstack(pstack);//初始化栈while(proot||!Isempty(pstack))//如果栈空并且结点指针空，则结束循环{if(proot){printf(%2c,proot-data);if(Isfull(pstack))//如果栈满不能执行入栈操作{printf(栈满，不能执行入栈操作！！);return;}Push(pstack,proot);//入栈proot=proot-left;//指针指向左子}else{if(Isempty(pstack))//栈空时不能出栈{printf(栈空，不能执行出栈操作！！);return;}proot=Pop(pstack);//执行出栈操作proot=proot-right;//指针指向右子}}}voidInorderI(Pnodeproot,Pstackpstack)//非递归中序遍历算法{Initstack(pstack);//初始化栈while(proot||!Isempty(pstack))//循环结束条件{if(proot){if(Isfull(pstack)){printf(栈满，不能执行入栈操作！！);return;}Push(pstack,proot);//执行入栈操作proot=proot-left;//指针指向左子}else{if(Isempty(pstack)){printf(栈空，不能执行出栈操作！！);return;}proot=Pop(pstack);//出栈printf(%2c,proot-data);//打印数据proot=proot-right;//指针指向右子}}}voidPostorderI(Pnodeproot,Pstackpstack)//非递归后续遍历算法{intflags[MAX];//定义标志位栈intp=-1;//初始化标志位栈intflag;//存放标志位Initstack(pstack);//初始化栈while(proot||!Isempty(pstack))//循环结束条件{if(proot){if(Isfull(pstack)){printf(栈满，不能执行入栈操作！！);return;}flags[++p]=0;//标志位置0，并入栈Push(pstack,proot);//结点入栈proot=proot-left;//指针指向左子}else{proot=Pop(pstack);//指针出栈flag=flags[p--];//相应标志位出栈if(flag==0)//如果标志位为0表示右子还未访问过{flag=1;//将标志位置1，右子已访问flags[++p]=flag;//标志位入栈Push(pstack,proot);//结点入栈proot=proot-right;//指针指向右子}else{printf(%2c,proot-data);//打印数据proot=NULL;//将结点指针置空}}}}voidmain(){TnodeA,B,C,D,E,F,G;//声明结点变量Stackstack;//声明栈Inittnode(&A,&B,&C,'A');//初始化结点Inittnode(&B,NULL,&D,'B');Inittnode(&C,&E,&F,'C');Inittnode(&D,NULL,NULL,'D');Inittnode(&E,NULL,NULL,'E');Inittnode(&F,&G,NULL,'F');Inittnode(&G,NULL,NULL,'G');printf(你定义的树的结构是：\n);/*一下是调用相应的函数输出遍历结果*/printf(A(B(D)C(EF(G)))\n);printf(=====================下面是遍历结果====================\n);printf(=====================递归先序遍历：====================\n);PreorderR(&A);printf(\n);printf(=====================非递归先序遍历：==================\n);PreorderI(&A,&stack);printf(\n);printf(=====================递归中序遍历：====================\n);InorderR(&A);printf(\n);printf(=====================非递归中序遍历：==================\n);InorderI(&A,&stack);printf(\n);printf(=====================递归后序遍历：====================\n);PostorderR(&A);printf(\n);printf(=====================非递归后序遍历：==================\n);PostorderI(&A,&stack);printf(\n);}四、运行结果定义的树的结构为A(B(D)C(EF(G))),遍历的结果：图6程序运行结果五、遇到的问题及解决这部分我主要遇到如下两个问题，其内容和解决方法如下所列：●执行程序时程序停止运行，其效果如图：图7问