# 從給定的二叉樹構造祖先矩陣 > 原文： [https://www.geeksforgeeks.org/construct-ancestor-matrix-from-a-given-binary-tree/](https://www.geeksforgeeks.org/construct-ancestor-matrix-from-a-given-binary-tree/) 給定一個二叉樹，其中所有值都從 **0** 到 **n-1** 。 構造祖先矩陣 **mat [n] [n]** 。 祖先矩陣定義如下。 ``` mat[i][j] = 1 if i is ancestor of j mat[i][j] = 0, otherwise ``` **示例**： ``` Input: Root of below Binary Tree. 0 / \ 1 2 Output: 0 1 1 0 0 0 0 0 0 Input: Root of below Binary Tree. 5 / \ 1 2 / \ / 0 4 3 Output: 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 ``` **我們強烈建議您最小化瀏覽器，然后自己嘗試。** **方法 1** 這個想法是遍歷這棵樹。 遍歷時，請跟蹤數組中的祖先。 當我們訪問一個節點時，將其添加到祖先數組中，并考慮鄰接矩陣中的相應行。 我們將其行中的所有祖先標記為 1。一旦處理完一個節點及其所有子節點，便從祖先數組中刪除該節點。 以下是上述想法的實現。 ## C++ ```cpp // C++ program to construct ancestor matrix for // given tree. #include<bits/stdc++.h> using namespace std; #define MAX 100 /* A binary tree node */ struct Node { ????int data; ????Node *left, *right; }; // Creating a global boolean matrix for simplicity bool mat[MAX][MAX]; // anc[] stores all ancestors of current node.? This // function fills ancestors for all nodes. // It also returns size of tree.? Size of tree is // used to print ancestor matrix. int ancestorMatrixRec(Node *root, vector<int> &anc) { ????/* base case */ ????if (root == NULL) return 0;; ????// Update all ancestors of current node ????int data = root->data; ????for (int i=0; i<anc.size(); i++) ???????mat[anc[i]][data] = true; ????// Push data to list of ancestors ????anc.push_back(data); ????// Traverse left and right subtrees ????int l = ancestorMatrixRec(root->left, anc); ????int r = ancestorMatrixRec(root->right, anc); ????// Remove data from list the list of ancestors ????// as all descendants of it are processed now. ????anc.pop_back(); ????return l+r+1; } // This function mainly calls ancestorMatrixRec() void ancestorMatrix(Node *root) { ????// Create an empty ancestor array ????vector<int> anc; ????// Fill ancestor matrix and find size of ????// tree. ????int n = ancestorMatrixRec(root, anc); ????// Print the filled values ????for (int i=0; i<n; i++) ????{ ????????for (int j=0; j<n; j++) ????????????cout << mat[i][j] << " "; ????????cout << endl; ????} } /* 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); } /* Driver program to test above functions*/ int main() { ????/* Construct the following binary tree ????????????????5 ??????????????/?? \ ????????????1????? 2 ??????????/? \??? / ?????????0??? 4? 3??? */ ????Node *root??????? = newnode(5); ????root->left??????? = newnode(1); ????root->right?????? = newnode(2); ????root->left->left? = newnode(0); ????root->left->right = newnode(4); ????root->right->left = newnode(3); ????ancestorMatrix(root); ????return 0; } ```