二叉树遍历C语言递归非递归六种算法.doc

《二叉树遍历C语言递归非递归六种算法.doc》由会员分享，可在线阅读，更多相关《二叉树遍历C语言递归非递归六种算法.doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业： 班 级： 指导教师： 姓 名： 学 号： 目 录一、设计思想.01二、算法流程图.02三、源代码.04四、运行结果.11五、遇到的问题及解决.11六、心得体会.12一、设计思想二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。递归算法：1先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束

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

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

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

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

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

7、直至当前结点的左右子都为空，且栈为空时，遍历结束。图3 非递归二叉树遍历 中序中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点

8、右子为空，且栈空，遍历结束。图4 非递归二叉树遍历 后序首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右

9、栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。三、源代码下面给出的是用递归算法实现的程序的源代码：#include#include/用递归的方式遍历二叉树typedef struct node /定义二叉树的结点int data;/结点的数据struct node*lChild,*rCh

10、ild;/结点左右子Node;int i=-1;/控制下面函数中循环的Node *buildTree(int *b) /产生二叉树(利用先序递归产生)Node *p;/创建一个根结点指针if(b+i=0)p=NULL;/如果传入的当前值为0 则设其为空结点elsep=(Node*)malloc(sizeof(Node); /开辟内存p-data=bi;/设置当前结点的数据p-lChild=buildTree(b);/左子结点p-rChild=buildTree(b);/右子return p;/把创建的树的根节点返回void preOrder(Node *root)/前序遍历if(root!=0

11、)/如果根节点不为0printf(%d ,root-data); /打印当前结点preOrder(root-lChild);/指向左子preOrder(root-rChild);/指向右子void inOrder(Node *root)/中序遍历if(root!=0)/如果根节点不为0inOrder(root-lChild);/指向左子printf(%d ,root-data);/打印当前结点inOrder(root-rChild);/指向右子void postOrder(Node *root)if(root!=0)postOrder(root-lChild);/指向左子postOrder(r

12、oot-rChild);/指向右子printf(%d ,root-data); /打印当前结点void main()/按先序次序输入树的结点(非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(用递归方法 nn前序遍历: );/打印提示内容preOrder(root); /调用前序遍历函数printf(n中序遍历: );/打印提示内容inOrder(root);

13、 /调用中序遍历函数printf(n后序遍历: );/打印提示内容postOrder(root); /调用后序遍历函数getch();下面给出的是用非递归算法实现的程序的源代码：#include#include/用非递归的方式遍历二叉树typedef struct node/定义二叉树的结点int data;/结点的数据struct node *lChild,*rChild;/结点左右子Node;typedef struct /创建栈Node *bottom;/栈底指针Node *top;/栈顶指针Stack;void init(Stack *s)/初始化栈s-bottom=(Node *)m

14、alloc(100*sizeof(Node);/为指针开辟内存s-top=s-bottom;/栈顶指针指向栈底指针int isEmpty(Stack s)/判断栈是否为空的函数if(s=s.bottom)return 1;/栈空 返回1elsereturn 0;/不为空返回 0void push(Stack *s,Node node)/栈的push方法*(s-top+)=node;/给栈顶赋值 然后top+1Node pop(Stack *s)/出栈函数Node node;/声明一Node类型遍量node=*(-(s-top);/node 为栈顶元素 然后top-1return node;/返

15、回pop出的结点Node peek(Stack *s)/看栈顶元素return *(s-top-1);/返回栈顶元素 typedef struct /创建栈(MyStack)结构体Node *bottom;/栈底指针Node *top;/栈顶指针MyStack;void init1(MyStack *s)/初始化栈s-bottom=(Node *)malloc(100*sizeof(Node);/开辟内存s-top=s-bottom;/栈顶指针指向栈底指针void push1(MyStack *s,Node node)/进栈方法*(s-top+)=node;/给栈顶赋值 然后top+1Node

16、 pop1(MyStack *s)/出栈函数Node node;/声明一Node类型遍量node=*(-(s-top);/node 为栈顶元素然后top-1return node;/返回pop出的结点Node peek1(MyStack *s)/查栈顶元素return *(s-top-1);/返回栈顶元素 int isEmpty1(MyStack s)/判断栈是否为空if(s=s.bottom)return 1;/栈空了 返回1elsereturn 0;/不为空返回 0int temp=-1;Node *buildTree(int *b)/产生二叉树Node *p;/创建一个根结点指针if(b

17、+temp=0)p=NULL;/如果传入的当前值为0 则设其为空结点elsep=(Node*)malloc(sizeof(Node);/开辟内存p-data=btemp;/设置当前结点的数据p-lChild=buildTree(b);/左子结点p-rChild=buildTree(b);/右子return p;/把创建的树的根结点返回void preOrder(Node *root)/前序遍历Stack po; /声明一个栈Node curr = *root;/当前结点为根结点init(&po);/初始化找while(curr.data!=0|!isEmpty(po)/当前结点不为空 且 栈不

18、为空if(curr.data=0)/如果当前结点为空curr=pop(&po);/当前结点指向 pop出栈的结点if(curr.rChild!=NULL)/如果右子为空push(&po,*curr.rChild);/将右子进栈printf(%d ,curr.data);/打印当前结点的内容if(curr.lChild!=NULL)/如果左子不为空curr=*curr.lChild;/当前子指向左子elsecurr=pop(&po);/当前子指向pop出栈结点if(curr.lChild=NULL)&(curr.rChild=NULL)/如果左子右子都为空printf(%d ,curr.data

19、);/打印当前结点的内容curr.data=0;/当前结点置空void inOrder(Node *root)/中序遍历Stack ms;/声明一个栈Node curr = *root;/当前结点指向根结点int flag = 0;/设置一个标志 0:当前结点指向了右结点 1:当前结点指向了左结点init(&ms);/初始化栈while(curr.data!=0|isEmpty(ms)/当前结点不为空且栈不为空if(curr.lChild!=NULL&flag=0) /左子不为空且没去过左子push(&ms,curr);/当前子进栈curr=*curr.lChild;/当前结点指向左子else

20、printf(%d ,curr.data);/打印当前结点的内容if(curr.rChild!=NULL)/左子为空curr=*curr.rChild;/指向左子flag=0;/flag 置 0if(curr.rChild=NULL&curr.lChild=NULL)/如果左右子都为空printf(%d ,curr.data);/打印当前结点的内容if(isEmpty(ms)=1) break;/栈空 则结束循环curr = pop(&ms);/当前子指向pop出栈的结点flag=1;/flag 置 1void postOrder(Node *root)/后序遍历/声明左右栈 如果当前结点有左

21、子则进左栈 若没左子但是有右子则进右栈Stack msl;/声明左栈MyStack msr;/声明右栈Node curr = *root;/结点指向树的根结点int flag=0;/设置一个标志 0:进左栈 1:进右栈/设置一个标志 0:没去过左右子树 1:去过左子树 2:去过右子树(两子树都去过)int status=0;init(&msl);/初始化左栈init(&msr);/初始化右栈while(curr.data!=0|isEmpty(msl)!=0|isEmpty1(msr)!=0)/当前结点不为空且左右栈都不为空if(status=0&curr.lChild!=NULL)/没去过左

22、右子树 且右子不为空push(&msl,curr);/当前子进左栈curr = *curr.lChild;/当前子指向左子flag=0;/flag置0else if(status!=2&curr.rChild!=NULL)/没去过右子树且右子不为空push1(&msr,curr);/当前子进右栈curr=*curr.rChild; /当前子指向右子flag=1;/flag置1status=0;/status 置0elseprintf(%d ,curr.data);/打印当前结点内容curr.data=0;/当前结点置空if(curr.data=0)/如果当前子为空if(flag=0)/如果fl

23、ag标志为0if(isEmpty(msl)=0)/如果左栈不为空curr = pop(&msl);/指向左栈弹出的元素status=1;/status标志置为1else if(isEmpty1(msr)=0)curr = pop1(&msr);/指向右栈弹出的元素status=2;/status标志置为2elseif(isEmpty1(msr)=0)/如果右栈为空curr=pop1(&msr);/指向右栈弹出的元素status=2;else if(isEmpty(msl)=0)curr=pop(&msl);/指向左栈弹出的元素status=1;/status标志置为1if(curr.data=

24、0) break; /若当前结点为空，结束循环void main()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);/创建一个结点指向创建的树的根结点printf(用非递归方法 n前序遍历: );/打印提示内容preOrder(root);/调用前序遍历函数printf(n中序遍历: );/打印提示内容inOrder(root); /调用中序遍历函数printf(n后序遍历: ); /打印提示内容postOrder(root); /调用后序遍历函数ge

25、tch();四、运行结果图5 递归算法运行结果图图6 非递归算法运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 二叉树的建立在刚开始进行时，如何建立二叉树难住了我，上课时听老师讲的是java的，在建立二叉树时和C语言不一样，在网上查阅了一部分资料后，找到了合适的办法，就是用结构体来储存二叉树，结构体内定义了二叉树的值和左右子，用0代表null，这样就可以用先序算法遍历输入了 l 在进行非递归遍历时，编译不报错，但运行出现下面的错误到网上查询后，得知出现“Access Violation”错误，有两种可能，第一种：出现这个错误是因为试图访问一块已经被释

26、放的内存,第二种是想使用一个还未创建对象的指针。解决的办法是为指针分配内存，用(Node*)malloc(sizeof(Node)语句，这样就能解决这个问题。六、心得体会大一就开始学习C语言，可是，当时学的时候就觉得语言好像是学会了，可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自己一个不得不动手操作的机会，在十一的这几天中，复习了以前学过的C的基本知识，然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较，从中找出自己的差距在哪里。第 21 页