C程序：二叉树

Question

我需要一些帮助来创建二叉树程序。基本上，我有不同的方法来创建和使用二叉树表（插入，查找等）。这些方法从其他类中调用。现在我不认为我的插入功能正常工作，因为当我打印表格时，它只显示树的最后一个节点。

#include <stdio.h> 
#include <stdlib.h> 
#include <ctype.h> 
#define __USE_BSD 
#include <string.h> 

#include "speller.h" 
#include "dict.h" 

typedef struct node *tree_ptr; 
struct node { 
    Key_Type element; // only data is the key itself 
    tree_ptr left, right; 
    // add anything else that you need 
}; 

struct table { 
    tree_ptr head; // points to the head of the tree 
    // add anything else that you need 
}; 

Table initialize_table(/*ignore parameter*/) { 
    Table newTable = malloc(sizeof(Table)); 
    newTable->head = NULL; 
    return newTable; 
} 

void insert_again(Key_Type key, tree_ptr node) { 
    Key_Type currentKey = node->element; 
    //printf("%s\n%s", currentKey, key); 
    int keyCompare = strcmp(key, currentKey); 
    // Move to the left node. 
    if (keyCompare < 0) { 
     //printf("%s\n%s", currentKey, key); 
     // If left node is empty, create a new node. 
     if (node->left == NULL) { 
      tree_ptr newPtr = malloc(sizeof(tree_ptr)); 
      newPtr->element = key; 
      newPtr->left = NULL; 
      newPtr->right = NULL; 
      node->left = newPtr; 
     } else { 
      insert_again(key, node->left); 
     } 
    } 
    // Move to the right node. 
    else if (keyCompare > 0) { 
     //printf("%s\n%s", currentKey, key); 
     // If right node is empty, create a new node. 
     if (node->right == NULL) { 
      tree_ptr newPtr = malloc(sizeof(tree_ptr)); 
      newPtr->element = key; 
      newPtr->left = NULL; 
      newPtr->right = NULL; 
      node->right = newPtr; 
     } else { 
      insert_again(key, node->right); 
     } 
    } 
} 

Table insert(Key_Type key, Table table) { 
    // if it's a new tree. 
    if (table->head == NULL) { 
     tree_ptr headPtr = malloc(sizeof(tree_ptr)); 
     headPtr->element = key; 
     headPtr->left = NULL; 
     headPtr->right = NULL; 
     table->head = headPtr; 
     //printf("%s", table->head->element); 
    } 
    // if the tree already exists 
    else { 
     //printf("%s", table->head->element); 
     insert_again(key, table->head); 
    } 
    //printf("%s", table->head->element); 
    return table; 
} 

Boolean find_key(Key_Type key, tree_ptr node) { 
    Key_Type currentKey = node->element; 
    int keyCompare = strcmp(key, currentKey); 
    if (node != NULL) { 
     if (keyCompare == 0) { 
      return TRUE; 
     } else 
     if (keyCompare == -1) { 
      return find_key(key, node->left); 
     } else { 
      return find_key(key, node->right); 
     } 
    } else { 
     return FALSE; 
    } 
} 

Boolean find(Key_Type key, Table table) { 
    return find_key(key, table->head); 
} 

void print_tree(tree_ptr node) { 
    if (node == NULL) { 
     return; 
    } 
    print_tree(node->left); 
    printf("%s\n", node->element); 
    print_tree(node->right); 
} 

void print_table(Table table) { 
    print_tree(table->head); 
} 

void print_stats(Table table) { 
} 

Answer 1

您必须搜索空子节点才能将新节点插入树中。使用指向指针的指针来注意空的子节点。除此之外，您必须为sizeof(struct node)分配内存，而不是像sizof(struct node*)那样分配内存。关于我可以看到的代码，该类型的Key_Type是char*。因此，您必须使用strcmp来比较密钥，并且必须分配内存并将密钥复制到节点中。

Boolean insert(Key_Type key, Table table) 
{ 
    tree_ptr *ppNode = &(table->head); // pointer to pointer to node (struct node **) 
    while (ppNode != NULL) 
    { 
     int keyCompare = strcmp(key, (*ppNode)->element); 
     if (keyCompare == 0) 
      return FALSE; // element with key is already member of tree 

     if (keyCompare < 0) 
      ppNode = &((*ppNode)->left); // go to left child 
     else 
      ppNode = &((*ppNode)->right); // go to right child 
    } 

    // now ppNode is either a pointer to an empty child pointer, 
    // or to table->head if the tree is empty 

    *ppNode = malloc(sizeof(struct node)); // allocate new node right to target 
    (*ppNode)->left = NULL; 
    (*ppNode)->right = NULL; 
    (*ppNode)->element = malloc(strlen(key) + 1); 
    strcpy((*ppNode)->element, key); 

    return TRUE; // new node added successfully 
} 

寻找具有key节点类似于找到一个空指针cjhild：

Boolean find_key(Key_Type key, Table table) 
{ 
    tree_ptr pNode = table->head; 
    while (ppNode != NULL) 
    { 
     int keyCompare = strcmp(key, pNode->element); 
     if (keyCompare == 0) 
      return TRUE; // element with key was found 

     if (keyCompare < 0) 
      pNode = pNode->left; // go to left child 
     else 
      pNode = pNode->right; // go to right child 
    } 
    return FALSE; // key is not member of tree 
}