2.二又树的遍历算法(3)后序遍历 void postorder (btree root) if(root!=NULL 递归算法 postorder(root-Ichild); postorder(root->rchild); printf(od", root->data)
17 遍历二叉树(cont’d) 2. 二叉树的遍历算法 (3)后序遍历 void postorder(BTREE root) { if(root!=NULL) { postorder(root→lchild); postorder(root→rchild); printf("%d",root→data); } } 递归算法
2.二又树的遍历算法(4)后序遍历 菲递归算法 算法思想: 开始时栈空,当前处理的结点指向根,只要遍历未完成, 则执行下面的操作 (1)递归:只要当前不空,就将当前结点入栈,向左孩子 推进一步,直到最左端 (2)循环执行以下操作 如果栈顶结点有右子树,则向右推进一步,进入右 子树并跳出循环,转到(1)。 如果栈顶是叶子,开始返回(出栈,并输出结点信息) 这时需要区分从左子树返回还是从右子树返回。如 果从左边返回,则寻找栈顶结点的右子树,继续递 归;否则继续循环出栈返回,直到不再是右边返回 或者返回到根
18 算法思想： 开始时栈空，当前处理的结点指向根，只要遍历未完成， 则执行下面的操作： (1) 递归：只要当前不空，就将当前结点入栈，向左孩子 推进一步，直到最左端 (2) 循环执行以下操作： 如果栈顶结点有右子树，则向右推进一步，进入右 子树并跳出循环，转到(1)。 如果栈顶是叶子，开始返回(出栈，并输出结点信息)， 这时需要区分从左子树返回还是从右子树返回。如 果从左边返回，则寻找栈顶结点的右子树，继续递 归；否则继续循环出栈返回，直到不再是右边返回 或者返回到根。 遍历二叉树(cont’d) 2.二叉树的遍历算法 (4)后序遍历 非递归算法
2.二又树的遍历算法(4)后序遍历 while(1) 非递归算法 if(s[top]- rchild!==NULL)∥如果是左返回 i p=s[]>rchild; break; j ∥向右进一步,跳出循环,进入递归 /开始从右边返回包括右子树不空的右返回 while(top!=0&& (s[top]->rchild-NULLIp=s[top]->rchild)) ip=s[top; top--; printf("%od"p>data); 1 if(top==0)return y//while(l) j//while(1)
19 #define N 50 //定义二叉树最大结点数 void postorder(BTREE root) {TREENODEPTR p,s[N]; int top=0; //s是栈，top是栈顶下标 p=root; while(1) { while(p!=NULL) //递归的循环 {top++; s[top]=p; p=p→lchild; } //一直向左递归,直到最左端 遍历二叉树(cont’d) 2. 二叉树的遍历算法 (4)后序遍历 while(1) { if(s[top]→rchild!=NULL) //如果是左返回 { p=s[top]→rchild; break; } //向右进一步，跳出循环，进入递归 //开始从右边返回,包括右子树不空的右返回 while(top!=0&& (s[top]→rchild==NULL||p==s[top]→rchild)) {p= s[top]; top--; printf("%d ",p→data);} if(top==0) return; }//while(1) }//while(1) } 非递归算法