二叉树遍历C语言(递归,非递归)六种算法

1、文档文档数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业：班 级：指导教师：姓 名：实用标准文案实用标准文案文档文档号: TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 一、设计思想.01 HYPERLINK l bookmark6 o Current Document 二、算法流程图2 HYPERLINK l bookmark8 o Current Document 三、源代码.04 HYPERLINK l bookmark10 o Current Document 四、运行结果.11 HYPERLINK l boo

2、kmark12 o Current Document 五、遇到的问题及解决. HYPERLINK l bookmark14 o Current Document 六、心得体会.12一、设计思想二叉树的遍历分为三种方式， 分别是先序遍历，中序遍历和后序遍历。 先序遍历实现的 顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算 法分，又分为递归遍历和非递归遍历。递归算法：1 先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将 左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即

3、得先序遍历结果。2中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为 根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断， 打印右子，直至结束。3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则 将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。非递归算法：1先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有 左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有

4、左子， 则直接将右子打印，同时将右子作为新的根结点判断。 若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点， 打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。2中序遍历：首先建立一个栈，定义一个常量flag （flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为

5、空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点 入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点， 一直到结束，使得当前结点右子为空，且栈空，遍历结束。3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断 根结点是否有左子，有左子则，将根结点入左栈，status置0

6、，flag置0 ,若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0 , flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0,则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点， 判断其左右子情况，按上述方法处理，直

7、至遍历结束。、算法流程图图1二叉树的建立用先序方法建立二叉树，为每个结点定义左右子，用0代表空，得到上述二叉树首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子， 则直接将右子打印，同时将右子作为新的根结点判断。 若当前结点没 有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子， 则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素， 同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空

8、时，遍历结束。君和話吝兔司檢济比弱歳寺 flng 耳为rtrue补忖化th韵匕纯点拒W梅吋吏*雪（fifrUS老傥阳0毎君和話吝兔司檢济比弱歳寺 flng 耳为rtrue补忖化th韵匕纯点拒W梅吋吏*雪（fifrUS老傥阳0毎到当誇 空.岂切性yes当F?荃点-入栈 当岂结士花习苗 左于拒它蚩H建.GE吉于*藉F当甫档点fla 9为 fdse图3非递归二叉树遍历中序中序遍历：首先建立一个栈，定义一个常量flag （flag为0或者1），用flag记录结点的左子是否去过，没有去过为0,去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后

9、再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入 栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一 直到结束，使得当前结点右子为空，且栈空，遍历结束。11JncnoFiacjO?nc当前蚂点退右 崔，当砒融 向其扫子” iajE斗前带占茴 做*単出的姑 11JncnoFiacjO?nc当前蚂点退右 崔，当砒融 向其扫子” iajE斗前带占茴 做*単出的姑 占3O1U3Hn=Ii洛审朽 直启国阳呦 站点，stain HX3岂

10、前烷环向 谡；七，鼻 自,和生焯出狭 負 -taluuS卽怕伊杖 6t.- 宅站號（fif即 和丸3和$和导当齡占图4非递归二叉树遍历后序首先建立两个栈，然后定义两个常量。第一个为status，取值为0, 1 , 2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1， 0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左 子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判

11、断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情 况，按上述方法处理，直至遍历结束。三、源代码F面给出的是用递归算法实现的程序的源代码:#in clude#in clude/用递归的方式遍历二叉树typedef struct nod

12、e/用递归的方式遍历二叉树typedef struct node int data;struct n ode*IChild,*rChild;Node;int i=-1;Node *buildTree( int *b)Node *p;if(b+i=O)p=NULL;占八、else p=(Node*)malloc(sizeof(Node);p_data=bi;p-IChild=buildTree(b);/结点的数据/结点左右子/控制下面函数中循环的/产生二叉树（利用先序递归产生）/创建一个根结点指针/如果传入的当前值为0则设其为空结/开辟内存/设置当前结点的数据/左子结点p-rChild=buil

13、dTree(b);return p;void preOrder(Node *root)if(root!=0)prin tf(%d ”,root-data);preOrder(root-lChild);preOrder(root-rChild);void in Order(Node *root)if(root!=0)in Order(root-lChild); prin tf(%d ,root-data);in Order(root-rChild);/右子/把创建的树的根节点返回/前序遍历/如果根节点不为0/打印当前结点/指向左子/指向右子/中序遍历/如果根节点不为0/指向左子/打印当前结点/指

14、向右子void postOrder(Node *root)if(root!=0)/指向左子/指向左子/指向右子/打印当前结点postOrder(root-IChild); postOrder(root-rChild); prin tf(%d ”,root-data); void mai n()/按先序次序输入树的结点(非 0整数)来创建一个树空结点用0表示int a = 1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0;int *b = a;将指向数组首地址的指针传给bulidTree 函数来创建树Node *root = buildTree(b);printf(用递

15、归方法nn前序遍历：”)；/打印提示内容preOrder(root);/调用前序遍历函数printf(n中序遍历：”);in Order(root);函数printf(n后序遍历：);postOrder(root);getch();/打印提示内容/调用中序遍历/打印提示内容/调用后序遍历函数/定义二叉树的结点/结点的数据/结点左右子/创建栈/栈底指针/栈顶指针/初始化栈下面给出的是用非递归算法实现的程序的源代码:#in clude#in clude/用非递归的方式遍历二叉树typedef struct node int data;struct node *IChild,*rChild;Node

16、;typedef structNode *bottom;Node *top;Stack;void in it(Stack *s)s-bottom=(Node *)malloc(100*sizeof(Node);s-top=s-bottom;int isEmpty(Stack s)/为指针开辟内存/栈顶指针指向栈底指针/判断栈是否为空的函数if(s.top=s.bottom)return 1;else/栈空返回1return 0;void push(Stack *s,Node node)*(s-top+)=no de;Node pop(Stack *s)Node no de;no de=*(_(

17、s_top);后 top-1retur n no de;/不为空返回 0/栈的push方法/给栈顶赋值然后top+1/出栈函数/声明一 Node类型遍量n ode为栈顶元素然II返回pop出的结点Node peek(Stack *s)return *(s-top-1);typedef structNode *bottom;Node *top;MyStack;void in it1(MyStack *s)s-bottom=(Node *)malloc(10C s-top=s-bottom;void push1(MyStack *s,Node node)*(s-top+)=no de;Node p

18、op1(MyStack *s)Node no de;no de=*(_(s_top);/看栈顶元素/返回栈顶元素/创建栈(MyStack)结构体/栈底指针/栈顶指针/初始化栈/开辟内存/栈顶指针指向栈底指针/进栈方法/给栈顶赋值然后top+1/出栈函数/声明一 Node类型遍量n ode为栈顶元素然后top-1retur n no de;Node peek1(MyStack *s)return *(s-top-1);int isEmpty1(MyStack s)if(s.top=s.bottom)return 1;elsereturn 0;int temp=-1;Node *buildTree

19、( int *b)Node *p;针if(b+temp=0) p=NULL;elseII返回pop出的结点/查栈顶元素II返回栈顶元素II判断栈是否为空II栈空了返回1II不为空返回 0II产生二叉树II创建一个根结点指II如果传入的当前值为 0则设其为空结点/开辟内存/设置当前结点的数/左子结点/右子/把创建的树的根结点返/前序遍历/声明一个栈/当前结点为根结点/初始化找/当前结点不为空且栈不为/如果当前结点为空/当前结点指向pop出栈的结点/如果右子为空 p=(Node*)malloc(sizeof(Node); p_data=btemp;据p-IChild=buildTree(b); p

20、-rChild=buildTree(b);return p;回void preOrder(Node *root)Stack po;Node curr = *root;in it(&po);while(curr.data!=0|!isEmpty(po)空if(curr.data=0)curr=pop(&po);if(curr.rChild!=NULL)push(&po,*curr.rChild);/将右子进栈prin tf(%d ”,curr.data);/打印当前结点的内容if(currChild!=NULL)/如果左子不为空curr=*currChild;/当前子指向左子elsecurr=p

21、op(&po);/当前子指向pop出栈结占八、if(curr.lChild=NULL) &(curr.rChild=NULL)/如果左子右子都为空prin tf(%d ”,curr.data);/打印当前结点的内容curr.data=0;/当前结点置空void inOrder(Node *root)Stack ms;Node curr = *root;占八、int flag = 0;/设置一个标志 0:当前结点指向了右结点/中序遍历/声明一个栈/当前结点指向根结1:当前结点指向了左结点in it (&ms);while(curr.data!=O|isEmpty(ms)为空if(currChil

22、d!=NULL&flag=0)左子push(&ms,curr); curr=*currChild;elseprin tf(%d ”,curr.data);容if(curr.rChild!=NULL)/初始化栈/当前结点不为空且栈不/左子不为空且没去过/当前子进栈当前结点指向左子/打印当前结点的内/左子为空/指向左子/指向左子/flag 置 0/如果左右子都为空/打印当前结点的内/栈空则结束循环当前子指向pop出栈的/flag 置 1/后序遍历curr=*curr.rChild;flag=0;if(curr.rChild=NULL&currChild=NULL)printf(%d ”,curr.

23、data);容if(isEmpty(ms)=1) break;curr = pop(&ms);结点flag=1;void postOrder(Node *root)/声明左右栈如果当前结点有左子则进左栈右没左子但是有右子则进右栈Stack msl;/声明左栈MyStack msr;/声明右栈Node curr = *root;/结点指向树的根结占八、/初始化左栈/初始化左栈/初始化右栈/没去过左右子树且右子不为int flag=0;/设置一个标志0:进左栈 1:进右栈/设置一个标志0:没去过左右子树1:去过左子树 2:去过右子树(两子树都去过)int status=O;in it (&msl)

24、;in it (&msr);while(curr.data!=0|isEmpty(msl)!=0|isEmpty1(msr)!=0)/当前结点不为空且左右栈都不为空if(status=0&currChild!=NULL)push(&msl,curr);curr = *currChild;flag=0;else if(status!=2&curr.rChild!=NULL)为空push1(&msr,curr);/当前子进左栈/当前子指向左子/flag 置 0/没去过右子树且右子不/当前子进右栈/当前子指向右子/flag 置 1/status 置 0/打印当前结点内容/当前结点置空/如果当前子为空

25、/如果flag标志为0/如果左栈不为空/指向左栈弹出的元/status标志置为1/指向右栈弹出的元/status标志置为2curr=*curr.rChild;flag=1;status=O;elseprintf(%d ”,curr.data);curr.data=0;if(curr.data=0)if(flag=0)if(isEmpty(msl)=O)curr = pop(&msl);素status=1;else if(isEmpty1(msr)=0)curr = pop1(&msr);素status=2;/如果右栈为空/如果右栈为空/指向右栈弹出的元/指向左栈弹出的元素/status标志置为

26、1/若当前结点为空，结束elseif(isEmpty1(msr)=0)curr=pop1(&msr);素status=2;else if(isEmpty(msl)=0)curr=pop(&msl);status=1;if(curr.data=O) break;循环void mai n()int Tree = 1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0;int *tree = Tree;Node *root = buildTree（tree）;II创建一个结点指向创建的树的根结点printf（”用非递归方法n前序遍历：）;/打印提示内容preOrder(root);/调用前序遍历函数printf（n中序遍历：”）；/打