/* 在后续遍历中最后结点4就是根，在中续中找到它，左边是左树，右是右，在4的左子树中一共有3个元素，后续中打印出来前3个元素也是根的左子树，由于后序的性质所以左子树的根会最后输出，所以我们只要知道左子树有多少元素就可以在后序中找到左子树的根， 怎么找呢，在中序中找到根的位置减1就知道左树有多少元素了。 左子树元素中序下标找到后怎么找右子树根呢 假设有N个元素，左子树有p个元素，那么在后序中就是N-p-1就是右子数根 */ #include #include #define MAXN 30 typedef struct TNode *Position; typedef Position BinTree; struct TNode{ int data; BinTree Left; BinTree Right; }; void PreorderTraversal(BinTree T) { if(T) { printf(" %d",T->data); PreorderTraversal(T->Left); PreorderTraversal(T->Right); } } BinTree BuildTree(int Inorder[],int Postorder[], int N) { BinTree T; int p; if(!N) return NULL;//递归终止条件 T = (BinTree)malloc(sizeof(struct TNode)); T->data = Postorder[N-1]; T->Left = T->Right = NULL; for(p=0;p<n;p++) if(inorder[p]="=" postorder[n-1])="" break;="" t-="">Left = BuildTree(Inorder,Postorder,p); T->Right = BuildTree(Inorder+p+1,Postorder+p,N-p-1); return T; } int main(void) { BinTree T; int Inorder[MAXN],Postorder[MAXN],N,i; scanf("%d",&N); for(i=0;i