題目：樹的遍歷

前言

如果不是完全二叉樹，使用數組模擬樹，會很浪費空間。

題目來源

本題來自 PTA 天梯賽。
題目鏈接: 樹的遍歷

題目描述
給定一棵二叉樹的后序遍歷和中序遍歷序列，輸出其層序遍歷的序列。假設樹中節點的鍵值均為互不相同的正整數。

輸入格式

• 第一行：一個正整數 N（≤30），表示二叉樹的節點個數。
• 第二行：后序遍歷序列，數字間以空格分隔。
• 第三行：中序遍歷序列，數字間以空格分隔。

輸出格式

• 輸出層序遍歷序列，數字間以 1 個空格分隔，行首尾不得有多余空格。

輸入樣例

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

輸出樣例

4 1 6 3 5 7 2

---

樹的數組存儲

基本思想

通過數組的索引關系表示樹的父子結構，無需顯式存儲指針。

存儲規則

1. 根節點存儲在索引 1（注意不是 0）。
2. 對于任意節點 i：
   • 左子節點索引：2 * i
   • 右子節點索引：2 * i + 1
   • 父節點索引：i / 2（整數除法）

示例

假設有一棵二叉樹：

我們可以通過一個數組去存儲

樹的索引對應數組的索引，樹節點的值存在數組里。

建樹算法

關鍵思路

• 后序遍歷：最后一個元素是根節點
• 中序遍歷：根節點左邊是左子樹，右邊是右子樹
• 遞歸構建：分別處理左右子樹

后序遍歷：
結構： 左子樹 — 右子樹 — 根

中序遍歷：
結構： 左子樹，根，右子樹

我們通過中序遍歷找到根，就能知道左子樹的個數，那么我們就能找到后序遍歷左子樹的范圍，從而得知左子樹的根。右子樹同理。

算法過程：

1.確定根節點：

• 從后序遍歷序列中取出最后一個元素，這就是當前子樹的根節點
• 將這個根節點存入我們構建的樹結構中

2.在中序序列中定位根節點：

• 在中序遍歷序列中查找這個根節點的位置
• 這個位置將中序序列分為左子樹和右子樹兩部分

3.遞歸構建左右子樹

代碼

參數說明

• root 后序序列中當前子樹的根節點索引
• start 中序序列中當前子樹的起始索引
• ed 中序序列中當前子樹的結束索引
• idx 當前節點在tree數組中的存儲位置

變量說明

• post 為后序遍歷數組
• in 為中序遍歷數組
• tree為存儲樹的數組

//根據中序遍歷和后續遍歷構造樹
void build(int root,int start,int ed,int idx)
{if(start>ed) return;//后序知道樹根，直接構造數組樹tree[idx] = post[root];//在中序遍歷中找根位置，用來區分后序遍歷左右子樹位置int i = start;while(i<ed && in[i] != post[root]) i++;//構造左子樹build(root - ed+i-1,start,i-1,idx*2);//構造右子樹build(root - 1,i+1,ed,idx*2+1);
}

總代碼

#include <iostream>
using namespace std;
#include <vector>const int N = 1e5+10;
int n;
int post[N],in[N];
vector<int> tree(N,-1);//根據中序遍歷和后續遍歷構造樹
void build(int root,int start,int ed,int idx)
{if(start>ed) return;//后序知道樹根，直接構造數組樹tree[idx] = post[root];//在中序遍歷中找根位置，用來區分后序遍歷左右子樹位置int i = start;while(i<ed && in[i] != post[root]) i++;//構造左子樹build(root - ed+i-1,start,i-1,idx*2);//構造右子樹build(root - 1,i+1,ed,idx*2+1);
}int main()
{cin  >> n;for(int i = 1;i<=n;i++)cin >>  post[i];for(int i = 1;i<=n;i++)cin >> in[i];build(n,1,n,1);vector<int> ans;for(int i = 1;i<tree.size();i++)if(tree[i] !=-1) ans.push_back(tree[i]);for(int i = 0;i<ans.size();i++)if(i != ans.size()-1)cout << ans[i]  <<  ' ';else cout << ans[i];return 0;
}

鏈表法

思路是差不多的

#include <iostream>
#include <queue>using namespace std;
const int N  =50;
int n;
int post[N],in[N];struct node
{int val;node* left;node* right;
};node* build(int root,int start,int ed)
{if(start>ed) return nullptr;//創建結點node * p = (node *) malloc(sizeof(node));p->val = post[root];//在中序遍歷中找根位置，用來區分后序遍歷左右子樹位置int i = start;while(i<ed && in[i] != post[root]) i++;p->left = build(root - ed+i-1,start,i-1);p->right = build(root - 1,i+1,ed);return p;
}void dfs(node *p)
{queue<node> q;q.push(*p);while(q.size()){node temp = q.front();q.pop();if(temp.val != p->val)cout << " ";cout << temp.val;if(temp.left != nullptr)  q.push(*temp.left);if(temp.right != nullptr) q.push(*temp.right);} 
}int main()
{cin >> n;for(int i = 1;i<=n;i++)cin >>  post[i];for(int i = 1;i<=n;i++)cin >> in[i];node* head = build(n,1,n);dfs(head);return 0;
}