2 3 1 5 7 6 4 1 2 3 4 5 6 7 得到root為4 左樹： 2 3 1 1 2 3 右樹： 5 7 6 5 6 7 遞歸
#include<iostream>#define MAX_Node 32#include<deque>using namespace std;int post[MAX_Node];//保存后序int in[MAX_Node];//保存中序int N;typedef struct Node{ int data; struct Node *lchild; struct Node *rchild;}Node,*Tree;int findN(int x,int a)//尋找root在中序某范圍內的位置{ for (int t = 0;t < N;t++) if (x == in[t+a]) return t; return 0;}Tree findchild(int m,int n,int x,int y){ if (m > n) {return NULL; } Node *root=(Node *)malloc(sizeof(Node)); root->data = post[n]; int mid = findN(root->data,x); root->lchild=findchild(m, m+mid-1,x,x+mid-1); root->rchild=findchild(m+mid, n-1, x+mid+1,y); return root;}void bfstraverse(Node *p){ deque<Node *> que; cout << p->data; if (p->lchild != NULL) que.push_back(p->lchild); if (p->rchild != NULL) que.push_back(p->rchild); while (!que.empty()) { if (que.front()->lchild != NULL) que.push_back(que.front()->lchild); if (que.front()->rchild != NULL) que.push_back(que.front()->rchild); cout << " "<<que.front()->data; que.pop_front(); }}int main(){ Node *p; cin >> N; for (int t = 0;t < N;t++) cin >> post[t]; for (int t = 0;t < N;t++) cin >> in[t]; p=findchild(0, N - 1,0,N-1);//構建樹木 bfstraverse(p);//層序遍歷樹 cout << endl;}新聞熱點
疑難解答
