c - 搜索子树以找到许多特征

Question

我在一个文件中保存了许多子树，我想搜索它们以找到每个子树的许多信息，例如:节点数、叶子数和子树组成的级别数...

更准确地说，是我工作中节点和叶子的区别；节点是子树中的任何顶点，可以是父节点或子节点，而叶子只是子节点，即每个叶子都是一个节点，反之则不然。

我在这项工作中面临很多问题，第一个:包含子树的文件没有显示根节点，并且没有区分父节点和子节点。

第二个问题:我读到，为了搜索树，程序员通常使用递归方法，所以我尝试通过互联网搜索引用资料、算法或伪代码，但我发现的只是处理二叉树，这不是我的案例(我正在处理子树的所有配置)!!!

那么任何人都可以通过提供引用、算法或示例来帮助我搜索树以找到此类子树的先前特征吗？

另一个问题:是否可以使用 R 来完成这项工作？

我会使用任何程序来编写代码，但主要对 C 感兴趣。

再说一遍，我的子树不是二叉树

更新:每个子树在我的文件中都表示为一组边，您可以在下面看到大小为 4 的子树的示例:

      44180 0 
      44180 18238
      44180 13362
      69677 44180

更新:对于新的更新感到抱歉，但是即使有大量子树，例如 100000 个子树，每个子树有 20 个边 (100000*20)，我可以在我的情况下使用 R 吗？？

Answer 1

一个Tree定义明确。

我假设每个文件恰好描述一棵树。假设 44180 0 行表示从节点 44180 到节点 0 的边似乎也是合理的。您应该仔细检查这些假设。

有了这些假设，您可以将文件解析为以下数据结构:

Node
    int id (id of self)
    Node* parent (pointer to parent Node)
    Node** children (list of children Nodes)

或者更简单:

Node
    int id
    int parent (id of the parent node)
    int* children (ids of all children)

将整个文件解析为节点列表/数组后，选择任何节点，并递归遍历父节点，直到找到没有父节点的节点。那么最终的节点一定是树的根。

现在您已经有了指向根节点的指针，您应该能够应用其他算法。