c - 将节点添加到树并按后序排序不起作用

Question

因此，对于我的一项作业，我们必须创建一棵树，向其中添加字符串，然后对其进行排序，以便它们按降序打印。代码看起来都正确并且编译得很好，但是当我运行我的程序 ./addnodetest 时，当它应该按降序打印排序的节点时，它不会打印任何内容。有什么原因吗？

这是函数treesort.c，它根据节点的值对添加到树中的节点进行排序:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "treesort.h"

/** Adds a new node to the tree. If the pointer to the passed in node is NULL, allocates a new node, puts 
 * the value into it, and returns a pointer to the new node. If the pointer is not NULL, compares the new 
 * value to the value in the node pointed to, then invokes the function       recursively on the left or right 
 * child as appropriate.
 * @param *current_tnode Pointer to an existing node
 * @param value A new value to be add to the tree
 * @return The new node
 */
Tnode *add_tnode(Tnode *current_tnode, char* value) {
  if (current_tnode == NULL) {
    Tnode *node = (Tnode*) malloc(sizeof(Tnode));
    node->leftchild = NULL;
    node->string = value;
    node->rightchild = NULL;
    current_tnode = node;
  }

  if (strcmp(current_tnode->string, value) > 0) {
    add_tnode(*(current_tnode->leftchild), value);
  }

  if (strcmp(current_tnode->string, value) < 0) {
    add_tnode(*(current_tnode->rightchild), value);
  }

  while (strcmp(current_tnode->string, value) == 0) {
    return current_tnode;
  }

  return current_tnode;
}

这是 traversetree.c 函数，我在其中调用树上的 postorder，以便它按降序打印树:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "treesort.h"

/** Traverses the tree, then prints out the values in the appropriate order.
 * @param node Tree to be sorted.
 */
void postorder(Tnode *node) {
  if (node != NULL) {
    postorder(*(node->leftchild));
    postorder(*(node->rightchild));
    printf("%s\n", node->string);
  }
}

这是主程序addnodetest.c，我在其中将根节点初始化为NULL(必须为分配执行此操作，我认为可能是问题)，然后为数组中的每个字符调用add_tnode(将它们添加到树)并使用后序打印它们:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "treesort.h"

int main() {
  Tnode *root = NULL;
  int i; // Loop counter
  char* array[] = {"m","j","p","h","f","t","c","w","z","a"};

  for(i = 0; i < 10; i++) {
    add_tnode(root, array[i]);
  }

  postorder(root);
  return 0; // Success!
}

这是头文件treesort.h，我在其中定义了结构节点和我创建的两个函数:

#ifndef TREESORT_H
#define TREESORT_H

/** Struct to define a node
 */
struct node {
  char* string; // Pointer to the C-style string that the node holds
  void** leftchild; // Pointer to the left child of the node
  void** rightchild; // "Pointer to the right child of the node
};

typedef struct node Tnode;

// Function prototypes

Tnode *add_tnode(Tnode *current_tnode, char* value);
void postorder(Tnode *node);

#endif

如果您想编译它，这是我的 makefile 中您需要的部分:

all: treesort addnodetest traversetree

treesort: treesort.o addnodetest.o traversetree.o
    gcc -g treesort.o addnodetest.o traversetree.o -o treesort

treesort.o: treesort.c treesort.h
    gcc -g -Wall -c treesort.c

addnodetest: addnodetest.o treesort.o traversetree.o
    gcc -g addnodetest.o treesort.o traversetree.o -o addnodetest

addnodetest.o: addnodetest.c treesort.h
    gcc -g -Wall -c addnodetest.c

traversetree: traversetree.o addnodetest.o treesort.o
    gcc -g traversetree.o addnodetest.o treesort.o -o traversetree

traversetree.o: traversetree.c treesort.h
    gcc -g -Wall -c traversetree.c

clean:
    rm -f *.o
    rm -f treesort
    rm -f addnodetest
    rm -f traversetree

Answer 1

add_tnode 目前永远不会向传入的树添加任何内容，因为它永远无法修改按值传递给它的指针 current_tnode。

您需要像这样使用add_tnode的返回值:

root = add_tnode(root, array[i]);

或者您需要更改函数以获取指向指针的指针，如下所示:

add_tnode(&root, array[i]);

您还应该意识到您错误地使用了 leftchild 和 rightchild。它们应该是 struct node * 类型，并且在使用它们的地方都应该进行相应的调整。现在，如果您设法添加一个节点，则对 add_tnode 的下一次调用将取消引用 NULL。