c - 动态创建的树中的根到节点计算

Question

我使用 C 进行编码，使用 GCC 4.8.1 作为编译器。目标是使用节点的键(无值——将其视为“项目”)计算从树根节点开始的每条路径的乘积之和。 Tree 的高度和初始根键由用户(输入)确定，其中 h 是树的高度，x 是根节点的键。

动态创建树，规则如下:

• 树的根节点是x。
• 如果父节点是x，则子节点将为x - 1(左子节点)、1(右子节点) .
• 如果父节点是 x - 1，则子节点将为 x - 1(左子节点)和 1(右子节点)子节点)。
• 如果父节点是1，则子节点将为x(左子节点)和0(右子节点)。

示例输入(以及直观地表示规则的图表):对于 h = 3 和 x = 4。

                                           4
                                         /   \
                                       3      1
                                     /  \    / \
                                    3    1  4   0

路径为4 -> 3 -> 3、4 -> 3 -> 1、4 -> 1 -> 4和 4 -> 1 -> 0。

此外，如果给定路径中的任何节点的键为 0，则在计算中不会使用它(因此 0 乘以任意数字就是 0)。预期总和是:

4x3x3 + 4x3x1 + 4x1x4 = 36 + 12 + 16 = 64(注意，4x1x0 被忽略)

...我的问题是:我不确定如何实现动态树。 这是我的代码:

int n;        //making n(value of root)  global
struct node {
  int data;
  struct node *left,*right;
}
struct node *createnode(int x)
{
  struct node *n = malloc(sizeof(struct node));
  *n=x;
  if(x==n||x==n-1)
  {
      n->left=createnode(x-1);
      n->right=createnode(1);
  }
  else if(x==1)
  {
      n->left=createnode(x);
      n->right=createnode(0);
  }
  return n;
}
void tree(int x,int y)
{
    struct node *root;
    root=creatnode(x);
}

Answer 1

首先，不要担心堆或堆栈或任何其他内存分配细节。相反，了解如何调用 malloc() 和 free():

   // you will need to code struct node ...
   struct node *root = malloc(sizeof(struct node));

   // populate root node

   // recursively call to create children nodes, etc.

   // invoke a routine to free root and other nodes::
   freenodes(root);

你还有很多工作要做。但要实现动态树，只需使用 malloc()。