轉自： http://www.liuchuo.net/archives/2087
已知前序（先序）與中序輸出后序： 前序：1, 2, 3, 4, 5, 6（根左右） 中序：3, 2, 4, 1, 6, 5（左根右） 分析：因為前序（根左右）最先出現的總是根結點，所以令root為前序中當前的根結點下標（并且同時把一棵樹分為左子樹和右子樹）。start為當前需要打印的子樹在中序中的最左邊的下標，end為當前需要打印的子樹在中序中最右邊的下標。遞歸打印這棵樹的后序，遞歸出口為start > end。i為root所表示的值在中序中的下標，所以i即是分隔中序中對應root結點的左子樹和右子樹的下標。 先打印左子樹，后打印右子樹，最后輸出當前根結點PRe[root]的值。 輸出的后序應該為：3, 4, 2, 6, 5, 1（左右根）
123456789101112131415161718#include <cstdio>using namespace std;int pre[] = {1, 2, 3, 4, 5, 6};int in[] = {3, 2, 4, 1, 6, 5};void post(int root, int start, int end) { if(start > end) return ; int i = start; while(i < end && in[i] != pre[root]) i++; post(root + 1, start, i - 1); post(root + 1 + i - start, i + 1, end); printf("%d ", pre[root]);}int main() { post(0, 0, 5); return 0;}新聞熱點
疑難解答
