2021秋季《数据结构》_EOJ 1063.树的双亲存储法（parent+child / parent）

题目

前面介绍了树的链式存储结构，那么如何用顺序存储来存储一棵树呢？在顺序存储时，我们除了存储每个结点值外，还要存储树中结点与结点之间的逻辑关系（即双亲与孩子结点之间的关系）。下面介绍树的双亲存储法。

编号，从根结点（它的编号为 0）开始，按从上到下的层次顺序，每一层按从左到右的顺序，递增地依次给每一个结点一个编号，图1上标出了各个结点的编号。
存储，如果用一维数组 tree[n] 来存储图1中的这棵树，则树中每个结点存储在 tree[n] 中的下标等于它的编号值，而且在数组 tree[n] 中， 每个元素是一个结构体，它包含两个成员，data 和 parent：其中 tree[i].data 存储一个结点的值， tree[i].parent 存储该结点的双亲结点在该数组中的下标。根结点 tree[O].parent=-1, 图2为图1中树的存储数组。

思路

方法一

存储每个结点的双亲和儿子

方法二

• 遵守题目要求，仅存储双亲结点
• 由于顺序输入，可得一个结点若有多个孩子结点，则这些孩子结点的下标必定升序顺序排列
• 对数组按照parent下标升序排序，可使用二分查找
• 需要注意的是，由于一个结点可能有多个孩子结点，所以我们需要找下标最小的孩子节点，即根节点的第一棵子树。然后再找第一棵子树的第一棵子树、第二棵子树balabala，这里的重复劳动可以用递归。找到叶子结点时输出key值，再返回叶子的parent，即重新回到上一个for循环。
  • 为了找到下标最小的叶子结点，需要对二分查找进行一些改进，使它夹出最靠左的下标。

代码

方法一

#include<bits/stdc++.h>using namespace std;struct Leaf
{
    int parent;vector<int> sons;
};vector<Leaf> Tree;void postOrderTraverse(vector<Leaf>& Tree, int root)
{
    for (int i = 0; i < Tree[root].sons.size(); i++){
    postOrderTraverse(Tree, Tree[root].sons[i]);}cout << root << ' ';
}int main()
{
    int n; cin >> n;int root;  // 存根节点的下标for (int i = 0; i < n; i++){
    Leaf tmp;Tree.push_back(tmp);}for (int i = 0; i < n; i++){
    cin >> Tree[i].parent;if (Tree[i].parent == -1){
    root = i;}else{
    Tree[Tree[i].parent].sons.push_back(i);}}postOrderTraverse(Tree, root);cout << endl;return 0;
}

方法二

#include<bits/stdc++.h>
using namespace std;struct mtNODE
{
    int key;int parent;
};bool cmp(mtNODE a, mtNODE b)
{
    if (a.parent != b.parent)return a.parent < b.parent;else{
    return a.key < b.key;}
}int binarySearch(int key, mtNODE tree[], int n)
{
    int left = 0, right = n - 1;int mid;int idx = -1;while (left <= right){
    // 采用靠左的策略mid = (left + right) / 2;if (tree[mid].parent < key){
    left = mid + 1;}// 为了夹出最小的idx需作出改进else if (tree[mid].parent >= key){
    right = mid - 1;idx = mid;}}return idx;
}void postOrder(int key, mtNODE tree[], int n)
{
    // cout << '*'<<key << endl;// 找到key的第一个孩子结点int idx = binarySearch(key, tree, n);// cout << '&' << idx << endl;if (idx != -1)  // 即key有孩子结点{
    for (int i = idx; i < n && tree[i].parent == key; i++){
    // 找tree[i].key的第一个孩子结点postOrder(tree[i].key, tree, n);}}cout << key << ' ';
}int main()
{
    int n; cin >> n;mtNODE* tree = new mtNODE[n];for (int i = 0; i < n; i++){
    cin >> tree[i].parent;tree[i].key = i;}// 对tree按parent升序排序sort(tree, tree + n, cmp);postOrder(tree[0].key, tree, n);return 0;
}