1020. Tree Traversals (25)

2019-11-11 07:35:13

字体：大中小

来源：转载

供稿：网友

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;}

上一篇：IDEA2016.3配置spring MVC记录

下一篇：（C#）A*算法伪代码及源码