小璐在機緣巧合之下獲得了一個二叉搜索樹，這個二叉搜索樹恰好有n個節點，每個節點有一個權值，每個節點的權值都在[1,n]這個區間內，并且兩兩不相同，真是優美的性質啊 但是命運的不公又讓她失去了這個二叉搜索樹 幸運的是，她還記得自己丟失的二叉搜索樹的前序遍歷序列。 在丟了二叉搜索樹之后，小璐無比想念她的這個樹的后序遍歷 那么問題來了，聰明的你在知道這個二叉搜索樹的前序遍歷的序列的情況下，能幫她找到這個二叉搜索樹的后序遍歷嘛? Input
多組輸入，以文件結尾 每組數據第一行為一個整數n，代表這個二叉搜索樹的節點個數(1<=n<=100) 接下來一行n個整數，代表這個二叉搜索樹的前序遍歷序列 Output
輸出n個整數 表示這個二叉樹的后序遍歷序列 Example Input
5 4 2 1 3 5 Example Output
1 3 2 5 4 Hint
二叉查找樹是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值 它的左、右子樹也分別為二叉排序樹 Author
2016暑假集訓結訓賽 by QAQ
#include<stdio.h>#include<stdlib.h>#include<string.h>struct node{ int data; struct node *l, *r;};struct node *creat(struct node *root, int number){ if(root == NULL) { root = (struct node*) malloc(sizeof(struct node)); root -> data = number; root -> l = NULL; root -> r = NULL; } else { if(root -> data > number) root -> l = creat(root -> l, number); else root -> r = creat(root -> r, number); } return root;};int k;int a[1111];void houxu(struct node *root){ if(root) { houxu(root -> l); houxu(root -> r); a[k++] = root -> data; }}int main(){ int n, i, number; while(scanf("%d", &n) != EOF) { k = 0; struct node *root = NULL; for(i = 0; i < n; i++) { scanf("%d", &number); root = creat(root, number); } houxu(root); for(i = 0; i < k; i++) { printf("%d%c", a[i], i == k - 1? '/n' : ' '); } } return 0;}根據先序遍歷和二叉排序樹可以重新建樹，然后求后序遍歷
新聞熱點
疑難解答
