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

Question

我正在编码C，使用GCC4.8.1 作为我的编译器。目标是使用节点的键（无值 - 将其视为“项目”）计算从 Trees 根节点开始的每条路径的乘积之和。Tree 的高度和初始根键由用户（输入）确定，其中h是树的高度，x是根节点的键。

动态创建树，规则如下：

树根节点是x。
如果父节点是x，那么子节点将是x - 1（左子节点），1（右子节点）。
如果父节点是x - 1，那么子节点将是x - 1（左子节点）和1（右子节点）。
如果父节点是1，那么子节点将是x（左子节点）和0（右子节点）。

示例输入（以及直观表示规则的图形）： Forh = 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);
}

score 0 · Accepted Answer

per your comment, here is your code:

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++;
    }
 }

First, of all you only want to create one root node, and to do this recursively you want the root node to create a left child and a right child. So, now code a routine called CreateNode(int value) that: explicitly allocates a node, calls itself to create left and right child nodes returns a pointer to the only node that it explicitly allocated, and instead of the while loop, just call it as:

 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);

    }
 }

So, CreateNode is going to be your recursive routine, and its logic is important! So, be careful when you code it!

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;
}

score 0 · Accepted Answer

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

在开发像树这样的结构时，值得拥有释放可用结构的代码，以及打印结构的功能。我包含的版本是一个特殊情况版本，仅写入标准输出（而不是接受FILE *参数），并且没有标记来标识正在打印的结构。通常，我的树转储函数会有签名void dump_tree(FILE *fp, const char *tag, struct node *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
$

score 0 · Accepted Answer

首先，不要担心堆或堆栈或任何其他内存分配细节。相反，了解如何调用malloc()and 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().

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

3 回答 3

代码

样本输出

Related

Reference