典型的二进制树表示

通常,我们将一个 anary 树(每个节点可能无限的子节点)表示为二叉树(每个节点只有两个子节点)。 下一个孩子被视为兄弟姐妹。请注意,如果树是二进制,则此表示将创建额外的节点。

然后我们对兄弟姐妹进行迭代并对孩子们进行递归。由于大多数树木相对较浅 - 很多孩子只有几层次的层次结构,这就产生了有效的代码。注意人类家谱是一个例外(许多级别的祖先,每个级别只有几个孩子)。

如果需要,可以保留后退指针以允许树上升。这些更难维护。

请注意,通常有一个函数可以调用根,一个递归函数有额外的参数,在本例中是树深度。

  struct node
  {
     struct node *next;
     struct node *child;
     std::string data;
  }

  void printtree_r(struct node *node, int depth)
  {
     int i;

     while(node)
     {
         if(node->child)
         {
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
            printtree_r(node->child, depth +1);
            for(i=0;i<depth*3;i++)
                printf(" ");
            printf("{\n"):
    
            for(i=0;i<depth*3;i++)
               printf(" ");
             printf("%s\n", node->data.c_str());

             node = node->next;
          }
      }
  }

  void printtree(node *root)
  {
     printree_r(root, 0);
  }