C：二叉树，内存分配

Question

所以我正在尝试使用结构和所有爵士乐在 C 中构建一个二叉树。到目前为止，我得到了以下信息：

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <signal.h>

typedef struct treeNode {
    int value;
    struct treeNode *left;
    struct treeNode *right;
} node;

node *top = NULL;

static node *addNode(int e, node *n);
static void printTree(node *n);

static node *addNode(int e, node *n) {
    if(top == NULL) {
        top = malloc(sizeof(node));
        top->value = e;
        top->left = NULL;
        top->right = NULL;
        return top;
    } else if (n != NULL) {
        if(e <= n->value) {
            if(n->left == NULL) {
                n->left = addNode(e, n->left);
            } else {
                (void) addNode(e, n->left); 
            }
        } else {
            if(n->right == NULL) {
                n->right = addNode(e, n->right);
            } else {
                (void) addNode(e, n->right);
            }
        }
    } else if(n == NULL) {
        n = malloc(sizeof(node));
        n->value = e;
        n->left = NULL;
        n->right = NULL;
        return n;
    }
    return n;
}

static void printTree(node *n) {
    if(n != NULL) {
        fprintf(stdout, "%d, ", n->value);
        if(n->left != NULL) {
            printTree(n->left);
        }
        if(n->right != NULL) {
            printTree(n->right);
        }
    }
}

int main(int argc, char **argv) {
        addNode(1, top);
        addNode(2, top);
        addNode(0, top);
        addNode(3, top);
        printTree(top);
return 0;
}

它缺少除了添加节点和打印树之外的所有东西，但这正是我已经有问题的地方。我得到的是 addNode 函数中的一些奇怪行为：最初，我将第一个 if 子句设置为

if(n == NULL) {
    n = malloc(sizeof(node));
    n->value = e;
    n->left = NULL;
    n->right = NULL;
    return n;
}

根本没有解决 - 因此没有创建新节点。现在的样子，它正在按照它必须的方式工作——我真的不明白为什么它会这样。当我第一次调用 addNode 函数时，无论如何我都会给它顶部指针作为参数，所以它应该检查它是否为 null（此时它应该是）并且应该只为它分配一些内存。但是，它不会发生。我不明白为什么。

Answer 1

您需要将第一个节点分配给top。

int main(int argc, char **argv) {
    top = addNode(1, top);
    addNode(2, top);
    addNode(0, top);
    addNode(3, top);
    printTree(top);
    return 0;
}

使用您原来的 if 子句，top 没有得到更新。您刚刚返回 n。

Answer 2

这里有几点。首先让我们从细节开始：你的 printTree() 太复杂了。当您在输入函数时检查 NULL 值时，您不必再次检查 left/right:

void printTree(node *n) {
  if (n == NULL) { return; }  // just leave
  printTree(n->left);
  printf("%d\n", n->value);
  printTree(n->right);
}

注意打印值的顺序，左右会改变输出。在此示例中，它将从低值到高值打印。

现在，对于您的 addNode()，您不需要全局 top 值。您将 top 赋给您的函数并获得具有返回值的新函数 (top = addNode(val, top);。拥有此全局值只会在混合使用 n 和 top 访问时导致错误代码. 而且功能可以更简单：

node *addNode(int val, node *n) {
  if (n == NULL) {  // just allocate a new one
    n = malloc(sizeof(node));  // add check for failure here, of course
    n->left = n->right = NULL; // it is a leaf, no child
    n->value = val;
    return(n);  // return the node for caller
  }
  // ok, we are on a node, check on which side we need to insert
  if (val < n->value) {
    // to the left: it may be replaced (if created)
    n->left = addNode(val, n->left);
  } else {
    // same, for right
    n->right = addNode(val, n->right);
  }
  // return the node so that top=addNode(val,top) always works
  return(n);
}

您可以使用指向节点的指针来阻止传递+获取节点，但是您必须很好地理解解引用指针。可能是：

void addNode(int val, node **n) {
  if (*n == NULL) {  // just allocate a new one
    *n = malloc(sizeof(node));  // add check for failure here, of course
    (*n)->left = (*n)->right = NULL; // it is a leaf, no child
    (*n)->value = val;
    return;  // return, the node 'n' is still modified
  }
  // ok, we are on a node, check on which side we need to insert
  if (val < (*n)->value) {
    // to the left: it may be replaced (if created)
    (*n)->left = addNode(val, (*n)->left);
  } else {
    // same, for right
    (*n)->right = addNode(val, (*n)->right);
  }
  // leave function (return not needed), node unchanged
  return;
}

那么你将这样调用这个函数：

int main(void) {
  node *top = NULL;  // must be initialized

  addNode(3, &top);
  addNode(1, &top);
  addNode(5, &top);
  printNode(top);
  (…)

C：二叉树，内存分配

C: binary trees, memory allocation

c

struct

memory-management

binary-search-tree