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

Question

我用C编码，使用GCC4.8.1作为我的编译器。目标是使用节点的键（没有值--将其视为项目）计算从Trees根节点开始的每个路径的乘积总和。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-

此外，如果给定路径中的任何节点的键为0，则在计算中不使用该键（因此0乘以任何数字即为0）。预期金额为：

4x3x3x14x1x4=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

当前代码没有考虑树的h参数，因此不会停止创建过程。你必须考虑到这一点。您为创建树给出的规则也不是真正完整的。您尚未定义数据值为零的节点会发生什么情况。

当开发像树这样的结构时，有代码来释放可用的结构是值得的，还有一个打印结构的函数。我包含的是一个特殊情况版本，只写入标准输出（而不是使用FILE*参数），并且没有标记来标识正在打印的结构。通常，我的树转储函数会有签名dump_tree（FILE*fp，const char*tag，结构节点*Tree）；，但是很容易使用下面显示的代码并将其泛化。

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

/*
** h is the height of the tree and x is the key of the root node.
**
** To dynamically create the tree, the rules are as follows:
**
** - The root node is x.
** - If the parent node is x, then the children will be x - 1 (left), 1 (right).
** - If the parent node is x - 1, then the children will be x - 1 (left) and 1 (right).
** - If the parent node is 1, then the children will be x (left) and 0 (right).
** - If the parent node is 0, then the child pointers will be null.
** - When the nodes are at level h in the tree, the child pointers will be null.
*/

struct node
{
    int          data;
    struct node *left;
    struct node *right;
};

/* Create a tree with value v at with d levels below it with the parameter x */
static struct node *create_node(int x, int d, int v)
{
    struct node *n = malloc(sizeof(*n));
    if (n == 0)
    {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    n->data = v;
    if (d == 0 || v == 0)
    {
        n->left = 0;
        n->right = 0;
    }
    else if (v == x || v == x - 1)
    {
        n->left = create_node(x, d-1, x-1);
        n->right = create_node(x, d-1, 1);
    }
    else if (v == 1)
    {
        n->left = create_node(x, d-1, x);
        n->right = create_node(x, d-1, 0);
    }
    else
        assert(0);
    return n;
}

static void print_node(struct node *tree)
{
    putchar('(');
    if (tree->left)
        print_node(tree->left);
    printf("[%d]", tree->data);
    if (tree->right)
        print_node(tree->right);
    putchar(')');
}

static void print_tree(struct node *tree)
{
    print_node(tree);
    putchar('\n');
}

static int path_products(struct node *tree)
{
    if (tree->left == 0 && tree->right == 0)
    {
        //printf("Leaf node: %d\n", tree->data);
        return tree->data;
    }
    else
    {
        int lhs = path_products(tree->left);
        int rhs = path_products(tree->right);
        int rv  = tree->data * (lhs + rhs);
        //printf("Interior node: lhs = %d, rhs = %d, data = %d, return %d\n", lhs, rhs, tree->data, rv);
        return rv;
    }
}

static void release_tree(struct node *tree)
{
    if (tree == 0)
        return;
    release_tree(tree->left);
    release_tree(tree->right);
    free(tree);
}

int main(int argc, char **argv)
{
    if (argc != 3)
    {
        fprintf(stderr, "Usage: %s height root\n", argv[0]);
        exit(1);
    }
    int h = atoi(argv[1]);
    if (h <= 0)
    {
        fprintf(stderr, "Invalid height %s (should be greater than zero)\n", argv[1]);
        exit(1);
    }
    int x = atoi(argv[2]);
    if (x <= 2)
    {
        fprintf(stderr, "Invalid root value %s (should be greater than two)\n", argv[2]);
        exit(1);
    }
    struct node *tree = create_node(x, h-1, x);

    print_tree(tree);
    printf("Sum of products of paths = %d\n", path_products(tree));
    release_tree(tree);
    return 0;
}

$ tree 1 4
([4])
H = 1, X = 4: Sum of products of paths = 4
$ tree 2 4
(([3])[4]([1]))
H = 2, X = 4: Sum of products of paths = 16
$ tree 3 4
((([3])[3]([1]))[4](([4])[1]([0])))
H = 3, X = 4: Sum of products of paths = 64
$ tree 4 4 
(((([3])[3]([1]))[3](([4])[1]([0])))[4]((([3])[4]([1]))[1]([0])))
H = 4, X = 4: Sum of products of paths = 256
$ tree 5 4
((((([3])[3]([1]))[3](([4])[1]([0])))[3]((([3])[4]([1]))[1]([0])))[4](((([3])[3]([1]))[4](([4])[1]([0])))[1]([0])))
H = 5, X = 4: Sum of products of paths = 1024
$ tree 6 4
(((((([3])[3]([1]))[3](([4])[1]([0])))[3]((([3])[4]([1]))[1]([0])))[3](((([3])[3]([1]))[4](([4])[1]([0])))[1]([0])))[4]((((([3])[3]([1]))[3](([4])[1]([0])))[4]((([3])[4]([1]))[1]([0])))[1]([0])))
H = 6, X = 4: Sum of products of paths = 4096
$

树转储格式是明确的，但对于那些不熟悉它的人来说是难以理解的。编写一个通用的树转储文件，将其打印到多行上，这是一个相当难写的命题。

$ for j in {3..7}; do for i in {1..5}; do ./tree $i $j; done; done | grep -v '^(' | so
H = 1, X = 3: Sum of products of paths = 3
H = 2, X = 3: Sum of products of paths = 9
H = 3, X = 3: Sum of products of paths = 27
H = 4, X = 3: Sum of products of paths = 81
H = 5, X = 3: Sum of products of paths = 243
H = 1, X = 4: Sum of products of paths = 4
H = 2, X = 4: Sum of products of paths = 16
H = 3, X = 4: Sum of products of paths = 64
H = 4, X = 4: Sum of products of paths = 256
H = 5, X = 4: Sum of products of paths = 1024
H = 1, X = 5: Sum of products of paths = 5
H = 2, X = 5: Sum of products of paths = 25
H = 3, X = 5: Sum of products of paths = 125
H = 4, X = 5: Sum of products of paths = 625
H = 5, X = 5: Sum of products of paths = 3125
H = 1, X = 6: Sum of products of paths = 6
H = 2, X = 6: Sum of products of paths = 36
H = 3, X = 6: Sum of products of paths = 216
H = 4, X = 6: Sum of products of paths = 1296
H = 5, X = 6: Sum of products of paths = 7776
H = 1, X = 7: Sum of products of paths = 7
H = 2, X = 7: Sum of products of paths = 49
H = 3, X = 7: Sum of products of paths = 343
H = 4, X = 7: Sum of products of paths = 2401
H = 5, X = 7: Sum of products of paths = 16807
$ 

Answer 2

根据您的评论，以下是您的代码：

struct node {int data; struct node *left,*right; } 

void tree(int x,int y) {
    int i=1;
    while(i<x) {
       struct node *root = malloc(sizeof(struct node));
       i++;
    }
 }

首先，您只需要创建一个根节点，要递归地创建一个左子节点和一个右子节点。因此，现在编写一个名为CreateNode（int-value）的例程：显式分配一个节点，调用自身来创建左、右子节点，返回指向它显式分配的唯一节点的指针，而不是while循环，只需将其称为：

 int  have_built_root_node;  // for this problem I would like using this var
                             // but it could also be passed as a parameter!

 int  max_height = 3;

 void tree(int root_value) {
    struct node *root;

    have_built_root_node = 0;
    root = CreateNode(1, root_value);

    }
 }

所以，CreateNode将成为你的递归例程，它的逻辑很重要！所以，编码的时候要小心！

struct node *createnode(int height, int value)
{  struct node *n = malloc(sizeof(struct node));

  // if root node has NOT been built, then build it!
  // set a switch so that its children are NOT created as root nodes.
  // 
  // store this nodes value in n, as *n.value = 
  // test this value as if (*n.value == 
  // compute value for left and right nodes
  // compute height for children nodes, what should happen when
  // the max_height is reached?

  // write code with lots of white space and aligned, it should look pretty!!
  if (x == n|| x == n-1)   // is this syntactically correct?
  {
      n->left  = createnode(x-1);
      n->right = createnode(1);
  }
  else if (x == 1)
  {
    n->left  = createnode(x);
    n->right = createnode(0);
  }
return n;
}

Answer 3

首先，不要担心堆或堆栈或任何其他内存分配细节。相反，要理解如何调用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（）。