解決一個重要的問題：如果給定一棵二叉樹的先序遍歷序列和中序遍歷序列，重建這棵
二叉樹，
假設已知先序序列為pre1、pre2、…、pren，中序序列為in1、in2、…、inn，如圖下圖所
示，
那么由先序序列的性質可知，先序序列的第一個元素pre1是當前二叉樹的根結點，再由中序序列的性質可知，當前二叉樹的根結點將中序序列劃分為左子樹和右子樹，因此，要做的就是在中序序列中找到某個結點ink，使得ink = pre1，這樣就在中序序列中找到了根結點，易知左子樹的結點個數numLef = k - 1，于是，左子樹的先序序列區間就是[2，k]，左子樹的中序序列區間是[1，k - 1],右子樹的先序序列區間是[k + 1，n]，右子樹的中序序列區間是[k + 1，n]，接看只需要往左子樹和右子樹進行遞回構建二叉樹即可，
先序序列和中序序列或者后序序列和中序序列構建二叉樹（兩種構建的方法相似，都是一層回圈找到根節點之后，左右子樹進行遞回后回傳指標），之后再利用層序遍歷（或者先序，后序）輸出：
當前先序序列區間為[preL，preR]，中序序列區間為[inL,inR]，后序序列為[postL,postR]，
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn = 50; int n,pre[maxn], in[maxn], post[maxn];//n代表節點個數 struct node { int data; node* lchild; node* rchild; }; node* preincreate(int preL, int preR, int inL, int inR) { if (preL > preR) { return NULL; //因為為左閉右閉區間所以preL > preR代表區間長度為0，為空樹； } node* root = new node;//創建一個新的節點來存放二叉樹的根節點； root->data = https://www.cnblogs.com/migang/p/pre[preL];//新節點的資料域的值為根節點的值， int k=0; for (k = inL; k <= inR; k++) { if (in[k]==pre[preL]) {//在中序序列中找到in[k]==pre[preL]的節點，此為根節點 break; } } int numleft = k - inL;//左子樹的節點個數， //思考: //左子樹的先序區間[preL+1,preL+numleft],左子樹的中序區間為[inL,k-1]; root->lchild = preincreate(preL + 1, preL + numleft, inL, k - 1); //右子樹的先序區間[preL+numleft+1,preR],右子樹的中序區間[k+1,inR]; root->rchild = preincreate(preL + numleft + 1, preR, k + 1, inR); return root; } node* postincreate(int postL, int postR, int inL, int inR) { if (postL > postR) { return NULL; } node* root = new node;//創建一個新的節點來存放二叉樹的根節點； root->data = https://www.cnblogs.com/migang/p/post[postR];//新節點的資料域的值為根節點的值 int k=0; for ( k = inL; k <=inR; k++) { if (in[k] == post[postR]) { break; } } int numleft = k - inL; root->lchild = postincreate(postL, postL + numleft - 1, inL, k - 1); root->rchild = postincreate(postL+numleft , postR - 1, k + 1, inR); return root;//回傳根節點的地址 } void BFS(node* root) { queue<node*> q;//佇列中存放地址 q.push(root); while (!q.empty()) { node* top = q.front(); q.pop(); printf("%d ", top->data); if (top->lchild != NULL) q.push(top->lchild);//左子樹非空 if (top->rchild != NULL) q.push(top->rchild);//右子樹非空 } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &post[i]); } for (int i = 0; i < n; i++) { scanf("%d", &in[i]); } node* root = postincreate(0,n-1,0,n-1);//通過后序和中序創建樹， BFS(root);//層序遍歷輸出 delete(root); return 0; }
由層序遍歷和中序遍歷重建二叉樹 ,因為層序序列是按照層級進行排列的，每一層的節點都是下一層的根節點，因此通過遍歷層序序列和中序序列找到層級優先級高的節點(層次低的，層序序列排在前面的)，再通過中序序列將其分為左右子樹進行更深一層的遞回遍歷查找，直到達到遞回基，
node* layerincreate(int ll, int lr, int inl, int inr) { if (inl > inr) return NULL; node* root = new node;//創建一個新的節點來存放二叉樹的根節點， int i, j; if (inl > inr) { return NULL;//遞回邊界，中序序列的長度為零，子樹為空樹， } for (i = ll; i <= lr; i++) {//從層數低的節點（優先級高的節點）開始查找， bool f = false;//標記未找到 for (j = inl; j <= inr; j++) { if (layer[i] == in[j]) { root->data = https://www.cnblogs.com/migang/p/in[j];//將當前序列的根節點資料域賦值； f = true; break;//找到了并標記，立刻退出內層回圈 } } if (f) break;//找到當前中序序列中優先級最高的節點，后退出回圈 } if (j >=inl) root->lchild = layerincreate(0, n - 1, inl, j - 1);//通過遞回對當前根節點的指向左子樹根節點的指標進行賦值， if (j <=inr) root->rchild = layerincreate(0, n - 1, j + 1, inr);//通過遞回對當前根節點的指向左子樹根節點的指標進行賦值， return root;//回傳當前序列的根節點， } void preOrder(node* root) { if (root == NULL) return; printf("%d ", root->data); preOrder(root->lchild); preOrder(root->rchild); } void inOrder(node* root) { if (root == NULL) return; inOrder(root->lchild); printf("%d ", root->data); inOrder(root->rchild); } void postOrder(node* root) { if (root == NULL) return; postOrder(root->lchild); postOrder(root->rchild); printf("%d ", root->data); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &layer[i]);//輸入層序序列 for (int i = 0; i < n; i++) scanf("%d", &in[i]);//輸入中序序列 node* root = layerincreate(0, n - 1, 0, n - 1); preOrder(root); printf("\n"); postOrder(root); return 0; }
與上面類似的還可以，由層序遍歷和中序遍歷我們先遞回求出先序序列，再由先序和中序重建二叉樹，
#include<cstdio> using namespace std; const int maxn = 50; int layer[maxn], in[maxn], pre[maxn]; int n,idx=0; struct node { int data; node* lchild; node* rchild; }; void makepre(int ll, int lr, int inl, int inr) { int i=0, j=0; //找出層序遍歷中的根節點在中序序列中的位置 for (i = ll; i <= lr; i++) { bool f = false; for (j = inl; j <= inr; j++) { if (layer[i] == in[j]) { pre[idx++] = in[j];//構造先序序列 f = true;//找到了先序排列的一個節點后退出回圈， break; } } if (f) break; } //將剛加入先序序列的節點的左子樹遞回 if (j > inl) makepre(ll, lr, inl, j - 1); //將剛加入先序序列的節點的右子樹遞回 if (j < inr) makepre(ll, lr, j + 1, inr); } //由先序和中序遞回構造二叉樹 node* preincreate(int preL, int preR, int inL, int inR) { if (preL > preR) { return NULL; //因為為左閉右閉區間所以preL > preR代表區間長度為0，為空樹； } node* root = new node;//創建一個新的節點來存放二叉樹的根節點； root->data = https://www.cnblogs.com/migang/p/pre[preL];//新節點的資料域的值為根節點的值， int k = 0; for (k = inL; k <= inR; k++) { if (in[k] == pre[preL]) {//在中序序列中找到in[k]==pre[preL]的節點，此為根節點 break; } } int numleft = k - inL;//左子樹的節點個數， //思考: //左子樹的先序區間[preL+1,preL+numleft],左子樹的中序區間為[inL,k-1]; root->lchild = preincreate(preL + 1, preL + numleft, inL, k - 1); //右子樹的先序區間[preL+numleft+1,preR],右子樹的中序區間[k+1,inR]; root->rchild = preincreate(preL + numleft + 1, preR, k + 1, inR); return root; } //先序遍歷 void preOrder(node* root) { if (root == NULL) return; printf("%d ", root->data); preOrder(root->lchild); preOrder(root->rchild); } //中序遍歷 void inOrder(node* root) { if (root == NULL) return; inOrder(root->lchild); printf("%d ", root->data); inOrder(root->rchild); } //后序遍歷 void postOrder(node* root) { if (root == NULL) return; postOrder(root->lchild); postOrder(root->rchild); printf("%d ", root->data); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &layer[i]); for (int i = 0; i < n; i++) scanf("%d", &in[i]); makepre(0, n - 1, 0, n - 1); node* root = preincreate(0, n - 1, 0, n - 1); preOrder(root); printf("\n"); postOrder(root); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279203.html
標籤：其他
上一篇：理解Nginx負載均衡
下一篇：擴展CRT（擴展中國剩余定理）