PostOrder (int *a,int len,tree *t); Pass an array (of any length) to determine whether a binary tree and its subtrees are traversed in subsequent order.
Analysis: the book is using recursion, I am using non-recursive order traversal solution, so it is relatively simple. Non-recursive traversal binary tree is to create two stacks, stack A as the auxiliary stack, stack B to record the order of traversal, and then output stack B at the same time with the input array A to judge, solved.
#include <stdio.h> #include <stdlib.h> #define max 100 typedef struct d{ int data; struct d *left; struct d *right; }tree; tree *buildTree(int *a,int &n) { int num=a[n++]; if(num==NULL) { return NULL; } tree *t=(tree *)malloc(sizeof(tree)); t->data=num; t->left=buildTree(a,n); t->right=buildTree(a,n); return t; } void post(tree *t) {if(t==NULL) {return; } post(t->left); post(t->right); printf("%d->",t->data); } bool postOrder(tree *t,int *orderArray,int len) {tree *stack1[Max]; tree *stack2[max]; int top1,top2; bool ret=false; top1=top2=-1; tree *tmp=t; while(top1! =-1||tmp! =NULL) { for(; tmp! =NULL;) { stack1[++top1]=tmp; stack2[++top2]=tmp; tmp=tmp->right; } if(top1! =-1) { tmp=stack1[top1--]; tmp=tmp->left; } } int i; if(len>top2) { ret=false; }else { for(i=0; top2! = 1; top2--) { if(orderArray[i]==(stack2[top2]->data)) { i++; } } if(i==len) { ret=true; } } return ret; } int main () {int a [] = {,2,4,8,0,0,0,5,0,0,3,6,0,0,7,0,0, 1}; Int order[]={8,4,5,2}; Int orlen=sizeof(order)/sizeof(order[0]); int n=0; tree *t=buildTree(a,n); post(t); printf("\n"); bool ret=postOrder(t,order,orlen); printf("%d",ret); / * -- -- -- -- -- -- -- -- -- -- * / int order2 [] = {1, 2, 3}; Ret =postOrder(t,order2,orlen); printf("\n%d",ret); }Copy the code