《二叉树遍历C语言(递归,非递归)六种算法》由会员分享，可在线阅读，更多相关《二叉树遍历C语言(递归,非递归)六种算法（15页珍藏版）》请在金锄头文库上搜索。
1、word数据结构双语项目文档报告用两种方式实现表达式自动计算专 业：班 级：指导教师：姓 名：学 号：目 录一、设计思想.01二、算法流程图.02三、源代码.04四、运行结果.11五、遇到的问题与解决.11六、心得体会.12一、设计思想二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。递归算法：1先序遍历：先序遍历就是首先判断根结点是否为空，为空如此停止遍历，不为空如此将左子作为新的根结点重新进展上述判断，左子遍历完毕后，再将右子作为根结点判断，直至完毕。
2、到达每一个结点时，打印该结点数据，即得先序遍历结果。2.中序遍历：中序遍历是首先判断该结点是否为空，为空如此完毕，不为空如此将左子作为根结点再进展判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进展判断，打印右子，直至完毕。3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空如此停止遍历，不为空如此将左子作为新的结点参数进展判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。非递归算法：1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的
3、根结点进展判断，方法同上。假如当前结点没有左子，如此直接将右子打印，同时将右子作为新的根结点判断。假如当前结点没有右子，如此打印左子，同时将左子作为新的根结点判断。假如当前结点既没有左子也没有右子，如此当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进展。直至当前结点的左右子都为空，且栈为空时，遍历完毕。2.中序遍历：首先建立一个栈，定义一个常量flagflag为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 非递归二叉树遍历 中序中序遍历：首先建立一个栈，定义一个常量flagflag为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
9、，假如flag为0，如此从左栈出栈一个元素作为当前结点，重新判断；假如flag为1如此从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，假如status为1，如此判断该结点有没有右子，假如有右子，如此将该结点入右栈，status置1，flag置1，假如没有右子，如此打印当前结点，并将指针置空，然后再次判断flag。假如当前结点status为2，且栈为空，如此遍历完毕。假如指针指向了左子，如此将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历完毕。三、源代码下面给出的是用递归算法实现的程序的源代码：#include#include/用递归的方式遍历二叉树typedef stru
10、ct node /定义二叉树的结点int data;/结点的数据struct node*lChild,*rChild;/结点左右子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);/右子retur
11、n p;/把创建的树的根节点返回void preOrder(Node *root)/前序遍历if(root!=0)/如果根节点不为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 *
12、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(用递归方法 nn前序遍历: );/打印提示内容preOrder(
13、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;/栈顶
14、指针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;/栈空 返回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;/返回pop出的结点
