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

二叉树遍历C语言(递归,非递归)六种算法数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算专业：班级：指导教师：姓名：学号：目录一、设计思想……………………………………………………….01 二、算法流程图…………………………………………………….02 三、源代码…………………………...

数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算专业：班级：指导教师：姓名：学号：目录一、设计思想……………………………………………………….01 二、算法流程图…………………………………………………….02 三、源代码………………………………………………………….04 四、运行结果……………………………………………………….11 五、遇到的问题及解决…………………………………………….11 六、心得体会 ……………………………………………………….12 一、设计思想二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为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则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。二、算法流程图图1 二叉树的建立用先序方法建立二叉树，为每个结点定义左右子，用0代表空，得到上述二叉树图2 非递归二叉树遍历先序首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。图3 非递归二叉树遍历中序中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。图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则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。三、源代码下面给出的是用递归算法实现的程序的源代码： #include #include //用递归的方式遍历二叉树 typedef struct node //定义二叉树的结点 { int data; //结点的数据 struct node*lChild,*rChild; //结点左右子 }Node; int i=-1; //控制下面函数中循环的 Node *buildTree(int *b) //产生二叉树(利用先序递归产生) { Node *p; //创建一个根结点指针 if(b[++i]==0)p=NULL; //如果传入的当前值为0 则设其为空结点 else { p=(Node*)malloc(sizeof(Node)); //开辟内存 p->data=b[i]; //设置当前结点的数据 p->lChild=buildTree(b); //左子结点 p->rChild=buildTree(b); //右子 } return p; //把创建的树的根节点返回 } void preOrder(Node *root) //前序遍历 { if(root!=0) //如果根节点不为0 { printf("%d ",root->data); //打印当前结点 preOrder(root->lChild); //指向左子 preOrder(root->rChild); //指向右子 } } void inOrder(Node *root) //中序遍历 { if(root!=0) //如果根节点不为0 { inOrder(root->lChild); //指向左子 printf("%d ",root->data); //打印当前结点 inOrder(root->rChild); //指向右子 } } void postOrder(Node *root) { if(root!=0) { postOrder(root->lChild); //指向左子 postOrder(root->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("用递归方法 \n\n前序遍历: "); //打印提示内容 preOrder(root); //调用前序遍历函数 printf("\n中序遍历: "); //打印提示内容 inOrder(root); //调用中序遍历函数 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 *)malloc(100*sizeof(Node)); //为指针开辟内存 s->top=s->bottom; //栈顶指针指向栈底指针 } int isEmpty(Stack s) //判断栈是否为空的函数 { if(s.top==s.bottom) return 1; //栈空返回1 else return 0; //不为空返回 0 } void push(Stack *s,Node node) //栈的push方法 { *(s->top++)=node; //给栈顶赋值然后top+1 } Node pop(Stack *s) //出栈函数 { Node node; //声明一Node类型遍量 node=*(--(s->top)); //node 为栈顶元素然后top-1 return node; //返回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+1 } Node pop1(MyStack *s) //出栈函数 { Node node; //声明一Node类型遍量 node=*(--(s->top)); //node 为栈顶元素然后top-1 return node; //返回pop出的结点 } Node peek1(MyStack *s) //查栈顶元素 { return *(s->top-1); //返回栈顶元素 } int isEmpty1(MyStack s) //判断栈是否为空 { if(s.top==s.bottom) return 1; //栈空了返回1 else return 0; //不为空返回 0 } int temp=-1; Node *buildTree(int *b) //产生二叉树 { Node *p; //创建一个根结点指针 if(b[++temp]==0) p=NULL; //如果传入的当前值为0 则设其为空结点 else { p=(Node*)malloc(sizeof(Node)); //开辟内存 p->data=b[temp]; //设置当前结点的数据 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)) //当前结点不为空且栈不为空 { 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; //当前子指向左子 }else { curr=pop(&po); //当前子指向pop出栈结点 } if((curr.lChild==NULL)&&(curr.rChild==NULL)) //如果左子右子都为空 { printf("%d ",curr.data); //打印当前结点的内容 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 { printf("%d ",curr.data); //打印当前结点的内容 if(curr.rChild!=NULL) //左子为空 { curr=*curr.rChild; //指向左子 } flag=0; //flag 置 0 } if(curr.rChild==NULL&&curr.lChild==NULL) //如果左右子都为空 { printf("%d ",curr.data); //打印当前结点的内容 if(isEmpty(ms)==1) break; //栈空则结束循环 curr = pop(&ms); //当前子指向pop出栈的结点 flag=1; //flag 置 1 } } } void postOrder(Node *root) //后序遍历 { //声明左右栈如果当前结点有左子则进左栈若没左子但是有右子则进右栈 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) //没去过左右子树且右子不为空 { push(&msl,curr); //当前子进左栈 curr = *curr.lChild; //当前子指向左子 flag=0; //flag置0 }else if(status!=2&&curr.rChild!=NULL) //没去过右子树且右子不为空 { push1(&msr,curr); //当前子进右栈 curr=*curr.rChild; //当前子指向右子 flag=1; //flag置1 status=0; //status 置0 }else { printf("%d ",curr.data); //打印当前结点内容 curr.data=0; //当前结点置空 } if(curr.data==0) //如果当前子为空 { if(flag==0) //如果flag标志为0 { if(isEmpty(msl)==0) //如果左栈不为空 { curr = pop(&msl); //指向左栈弹出的元素 status=1; //status标志置为1 }else if(isEmpty1(msr)==0) { curr = pop1(&msr); //指向右栈弹出的元素 status=2; //status标志置为2 } }else { if(isEmpty1(msr)==0) //如果右栈为空 { curr=pop1(&msr); //指向右栈弹出的元素 status=2; }else if(isEmpty(msl)==0) { curr=pop(&msl); //指向左栈弹出的元素 status=1; //status标志置为1 } } if(curr.data==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); //调用后序遍历函数 getch(); } 四、运行结果图5 递归算法运行结果图图6 非递归算法运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列： ● 二叉树的建立在刚开始进行时，如何建立二叉树难住了我，上课时听老师讲的是java的，在建立二叉树时和C语言不一样，在网上查阅了一部分资料后，找到了合适的办法，就是用结构体来储存二叉树，结构体内定义了二叉树的值和左右子，用0代表null，这样就可以用先序算法遍历输入了 ● 在进行非递归遍历时，编译不报错，但运行出现下面的错误到网上查询后，得知出现“Access Violation”错误，有两种可能，第一种：出现这个错误是因为试图访问一块已经被释放的内存,第二种是想使用一个还未创建对象的指针。解决的办法是为指针分配内存，用(Node*)malloc(sizeof(Node))语句，这样就能解决这个问题。六、心得体会大一就开始学习C语言，可是，当时学的时候就觉得语言好像是学会了，可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自己一个不得不动手操作的机会，在十一的这几天中，复习了以前学过的C的基本知识，然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较，从中找出自己的差距在哪里。

                    本文档为【二叉树遍历C语言(递归,非递归)六种算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

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

你可能还喜欢