广东工业大学数据结构AnyView作业系统：判断子孙关系与构建父节点数组算法

在广东工业大学的数据结构anyview作业系统第六章中，主要讨论了两种与二叉树存储结构相关的算法。首先，第6.33小题要求设计一个名为`StatusDencendant`的函数，用于判断结点u是否为结点v的子孙。这个函数使用两个一维数组L和R来存储二叉树的结构，其中L[i]表示结点i的左孩子，R[i]表示结点i的右孩子，0表示该节点为空。函数采用递归策略，通过遍历子树来确定关系，如果u是v的左孩子或右孩子，或者u是v的左孩子的左孩子、右孩子的左孩子等间接关系，函数返回`TRUE`，否则返回`FALSE`。 具体实现如下： ```c typedef int Array1D[MAXSIZE]; StatusDencendant(Array1DL L, Array1DR R, int n, int u, int v) { int flagL = 0, flagR = 0; // 判断u是否直接为v的左孩子或右孩子 if (L[v] == u || R[v] == u) return TRUE; // 递归查找左孩子的情况 if (L[v] != 0 && Dencendant(L, R, n, u, L[v])) flagL = 1; // 递归查找右孩子的情况 if (R[v] != 0 && Dencendant(L, R, n, u, R[v])) flagR = 1; // 如果u是v的任何子节点的子孙（包括直接和间接），则返回TRUE if (flagL + flagR > 0) return TRUE; // 否则，返回FALSE return FALSE; } ``` 接下来，第6.34小题则进一步扩展了这个功能，需要构建一个新的数组T，用于存储每个结点的父节点。T[i]将指示结点i的双亲。为此，首先需要遍历L和R数组，根据节点间的链接关系填充T数组。然后，使用已有的`StatusDencendant`函数来判断结点u是否为结点v的子孙，但这次是在已知父节点关系的情况下进行判断。 为了完成这个任务，可以编写一个辅助函数来构建T数组，接着调用`StatusDencendant`函数。构建T数组的步骤大致如下： ```c void BuildParentArray(Array1D L, Array1D R, Array1D T, int n) { for (int i = 1; i <= n; i++) { if (L[i] == 0 && R[i] == 0) // 叶子节点，其父节点为NULL T[i] = -1; else if (L[i] != 0) // 非叶子节点，其父节点为L[i] T[i] = L[i]; else if (R[i] != 0) // 非叶子节点，其父节点为R[i] T[i] = R[i]; } } StatusIsDescendant(Array1D L, Array1D R, Array1D T, int n, int u, int v) { BuildParentArray(L, R, T, n); return StatusDencendant(T, NULL, n, u, v); // 使用已构建的T数组调用原函数 } ``` 这两个题目涉及了二叉树的层次结构表示和深度优先搜索（DFS）的应用，重点在于递归算法的设计和在一维数组上实现二叉树的查找操作。理解这些概念和算法对于深入学习数据结构和树形数据的处理至关重要。