轉自：http://www.liuchuo.net/archives/2090
已知后序與中序輸出前序（先序）
已知后序與中序輸出前序（先序）： 后序：3, 4, 2, 6, 5, 1（左右根） 中序：3, 2, 4, 1, 6, 5（左根右） 分析：因為后序的最后一個總是根結點，令i在中序中找到該根結點，則i把中序分為兩部分，左邊是左子樹，右邊是右子樹。因為是輸出先序（根左右），所以先打印出當前根結點，然后打印左子樹，再打印右子樹。左子樹在后序中的根結點為root – (end – i + 1)，即為當前根結點-右子樹的個數。左子樹在中序中的起始點start為start，末尾end點為i – 1.右子樹的根結點為當前根結點的前一個結點root – 1，右子樹的起始點start為i+1，末尾end點為end。 輸出的前序應該為：1, 2, 3, 4, 5, 6（根左右）
#include <cstdio>using namespace std;int post[] = {3, 4, 2, 6, 5, 1};int in[] = {3, 2, 4, 1, 6, 5};void PRe(int root, int start, int end) { if(start > end) return ; int i = start; while(i < end && in[i] != post[root]) i++; printf("%d ", post[root]); pre(root - end + i - 1, start, i - 1); pre(root - 1, i + 1, end);}int main() { pre(5, 0, 5); return 0;}新聞熱點
疑難解答
