從祖先矩陣構造樹 · GeeksForGeeks 中文系列教程

# 從祖先矩陣構造樹 > 原文： [https://www.geeksforgeeks.org/construct-tree-from-ancestor-matrix/](https://www.geeksforgeeks.org/construct-tree-from-ancestor-matrix/) 給定祖先矩陣 mat [n] [n]，其中祖先矩陣定義如下。 ``` mat[i][j] = 1 if i is ancestor of j mat[i][j] = 0, otherwise ``` 從給定的祖先矩陣構造一個二叉樹，其所有節點值都從 0 到 n-1。 1. 可以假定，如果程序有效，則輸入內容可以從中構造出樹。 2. 一個輸入可以構建許多二叉樹。該程序將構造其中任何一個。例子： ``` Input: 0 1 1 0 0 0 0 0 0 Output: Root of one of the below trees. 0 0 / \ OR / \ 1 2 2 1 Input: 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 Output: Root of one of the below trees. 5 5 5 / \ / \ / \ 1 2 OR 2 1 OR 1 2 OR .... / \ / / / \ / \ / 0 4 3 3 0 4 4 0 3 There are different possible outputs because ancestor matrix doesn't store that which child is left and which is right. ``` 該問題主要是以下問題的逆向。 [從給定的二叉樹](https://www.geeksforgeeks.org/construct-ancestor-matrix-from-a-given-binary-tree/)構造祖先矩陣 **我們強烈建議您最小化瀏覽器，然后自己嘗試。** 解決方案中使用的觀察結果： 1. 對應于葉子的行全為 0 2. 根目錄對應的行最大數量為 1。 3. 第 i 行中的數字 1 表示節點 i 的后代數量。這個想法是以**自底向上**的方式構造樹。 1）創建一個節點指針數組 node []。 2）存儲與給定計數相對應的行號。為此，我們使用了[多圖](http://geeksquiz.com/multimap-associative-containers-the-c-standard-template-library-stl/)。 3）處理多圖的所有條目，從最小計數到最大（注意，可以按排序順序遍歷圖和多圖中的條目）。請為每個條目執行以下操作。 …….a）為當前行號創建一個新節點。 …….b）如果此節點不是葉節點，請考慮未設置其父節點的所有后代，將當前節點作為其父節點。 4）最后處理的節點（具有最大和的節點）是樹的根。下面是上述想法的 C++ 實現。以下是步驟。 ``` // Given an ancestor matrix for binary tree, construct // the tree. #include <bits/stdc++.h> using namespace std; # define N 6 /* A binary tree node */ struct Node { ????int data; ????Node *left, *right; }; /* Helper function to create a new node */ Node* newNode(int data) { ????Node* node = new Node; ????node->data = data; ????node->left = node->right = NULL; ????return (node); } // Constructs tree from ancestor matrix Node* ancestorTree(int mat[][N]) { ????// Binary array to determine whether ????// parent is set for node i or not ????int parent[N] = {0}; ????// Root will store the root of the constructed tree ????Node* root = NULL; ????// Create a multimap, sum is used as key and row ????// numbers are used as values ????multimap<int, int> mm; ????for (int i = 0; i < N; i++) ????{ ????????int sum = 0; // Initialize sum of this row ????????for (int j = 0; j < N; j++) ????????????sum += mat[i][j]; ????????// insert(sum, i) pairs into the multimap ????????mm.insert(pair<int, int>(sum, i)); ????} ????// node[i] will store node for i in constructed tree ????Node* node[N]; ????// Traverse all entries of multimap.? Note that values ????// are accessed in increasing order of sum ????for (auto it = mm.begin(); it != mm.end(); ++it) ????{ ??????// create a new node for every value ??????node[it->second] = newNode(it->second); ??????// To store last processed node. This node will be ??????// root after loop terminates ??????root = node[it->second]; ??????// if non-leaf node ??????if (it->first != 0) ??????{ ????????// traverse row 'it->second' in the matrix ????????for (int i = 0; i < N; i++) ????????{ ???????????// if parent is not set and ancestor exits ???????????if (!parent[i] && mat[it->second][i]) ???????????{ ?????????????// check for unoccupied left/right node ?????????????// and set parent of node i ?????????????if (!node[it->second]->left) ???????????????node[it->second]->left = node[i]; ?????????????else ???????????????node[it->second]->right = node[i]; ?????????????parent[i] = 1; ???????????} ????????} ??????} ????} ????return root; } /* Given a binary tree, print its nodes in inorder */ void printInorder(Node* node) { ????if (node == NULL) ????????return; ????printInorder(node->left); ????printf("%d ", node->data); ????printInorder(node->right); } // Driver program int main() { ????int mat[N][N] = {{ 0, 0, 0, 0, 0, 0 }, ????????{ 1, 0, 0, 0, 1, 0 }, ????????{ 0, 0, 0, 1, 0, 0 }, ????????{ 0, 0, 0, 0, 0, 0 }, ????????{ 0, 0, 0, 0, 0, 0 }, ????????{ 1, 1, 1, 1, 1, 0 } ????}; ????Node* root = ancestorTree(mat); ????cout << "Inorder traversal of tree is \n"; ????printInorder(root); ????return 0; } ``` 輸出： ``` Inorder traversal of tree is 0 1 4 5 3 2 ``` 請注意，我們也可以使用向量數組代替多圖。為了簡單起見，我們使用了 multimap。向量數組將提高性能，因為插入和訪問元素將花費`O(1)`時間。