c - BST构建树双指针

Question

我不确定如何设置指向指针的指针来构建树。就像一旦我走到一个叶子并调用插入，我应该如何插入另一个元素调用插入与根节点或根指针的地址？我认为这个函数的问题是名称 root 应该是双指针吧？

#include "bst.h"
#include <stdio.h>
#include <stdlib.h>

//arbitrary list of temp nodes

TreeNode *new_node, *root, *tmp, *parent;
int elemArray[100], i1, i2, i0;


int main( int argc, char *argv[] ) {

    //Throw error is *Argv[] is not an integer
    //assuming it was an integer
    int cnt = atoi( argv[1] );
    printf( "number is %d\n", cnt );
    //
    printf("Enter %i integer values to place in tree:\n", cnt);
    for ( i1 = 0; i1 < cnt; ++i1) {
        scanf( "%d", &elemArray[i1] );
    }

    //first ouput "INput Values"

    printf( " Input Values:\n " );  
     for ( i2 = 0; i2 < cnt; ++i2) {
               printf( "%d\n", elemArray[i2] );
        }
    TreeNode** root = (TreeNode*)malloc(sizeof(TreeNode*));

    buildTree(root, elemArray, cnt );

    printf( "Preorder:\n ");

    //traverse
    //TreeNode* tempN = malloc(sizeof(TreeNode*));
    //tempN->data= 5;

    traverse( root, PREORDER);

    //traverse a single node 
    printf( "Inorder:\n ");

    printf( "Postorder:\n ");


    //Build tree with each element

    return 0;
}

这是.h文件

/// The definition of the tree structure
typedef struct TreeNode {
    int data ;                  // the data stored in the node
    struct TreeNode* left ;     // node's left child
    struct TreeNode* right ;    // node's right child
} TreeNode;

/// The three supported traversals
typedef enum {
    PREORDER,           // parent -> left -> right
    INORDER,            // left -> parent -> right
    POSTORDER           // left -> right -> parent
} TraversalType;

最后是遍历函数，因为它没有通过第一次测试。

void traverse( const TreeNode* root, const TraversalType type ) {

    if ( type == PREORDER) {
             if (root != NULL)
             {
                printf("%d", root->data);
                traverse( root->left, PREORDER);
                traverse( root-> right, PREORDER);
            }
    }
}

void build_tree(TreeNode** root, const int elements[], const int count) {

    TreeNode* node = malloc(sizeof(TreeNode*));
    node->left = node ->right = NULL;

    *root = node;

    for ( int i0 = 0; i0 < count; ++i0 ){
        TreeNode* node = malloc(sizeof(TreeNode*));
        *root = node;
        node->data = elements[cnt];
        insertNode( &(*root), &node );
    }

}

为什么 insertNode 会出现错误(多个)，我不知道哪个是指针，哪个是结构。伙计们有什么提示会有所帮助吗？

bst.c:94:20: error: request for member 'left' in something not a structure or union
         insert(root->left, new_node);


void insertNode(TreeNode** root, TreeNode* new_node) {

   if (new_node-> data < &root-> data) {
      if (&root-> left == NULL) 
         &root-> left == new_node;
      else
        insert(root->left, new_node);
   }

  if (new_node->data > &root->data) {
    if(&root-> right ==NULL)
      &root->right = new_node;
    else
      insert(&root->right, new_node);
  }
}

所以对于编辑 2:我确实有一个头文件，它有一个 build_Tree(**root, elems[], sizeofElem[])，这意味着我需要一个辅助函数插入。是的，通过输入开始*会更容易添加。

编辑 1

#include "bst.h"
#include <stdio.h>
#include <stdlib.h>

//arbitrary list of temp nodes

TreeNode *new_node, *root, *tmp, *parent, *current;
int elemArray[5], i1, i2, i0;

/*
Insert a new node into the tree by referencing the root and using recursion
*/

    TreeNode* getN(int dataElem) {
        TreeNode *newNode = malloc(sizeof(*newNode));
        if (newNode != NULL)
        {
            newNode->data = dataElem;
            newNode->left = NULL;
            newNode->right = NULL;
        }

        return newNode;
    } 

/** This func should just be the root of the tree in the parameter, 
but I like the idea of a pointer becuase it helps to create a tempory 
pointer rather than newNode
**/


TreeNode* addNodeToTree(TreeNode *root, int data) {

    TreeNode *current = *root; //define the current pointer to the root always
    TreeNode *parent = *root
    TreeNode *newNode = getN(data);

    if (*root == NULL)
    {
        printf("First Node");
        *root = newNode;
    }
    else
    {
        while(current != NULL)
        {
            parent = current;
            if (current->data > data)
                current = current->left;
            else if (current->data < data)
                current = current->right;
        }

        if (parent->data > data)
            parent->left = newNode;
        else if (parent->data < data)
            parent->right = newNode;
    }
}



void build_Tree(TreeNode** root, const int elements[], const int count) {

    *root = malloc(sizeof(TreeNode));

    for ( i0 = 0; i0 < count; ++i0 ){
        printf("%d\n", elements[count]);
        addNodeToTree(&root, elements[count]);
    }

}


int main( int argc, char *argv[] ) {

    //Throw error is *Argv[] is not an integer
    //assuming it was an integer
    int cnt = atoi( argv[1] );
    printf( "number is %d\n", cnt );
    //
    printf("Enter %i integer values to place in tree:\n", cnt);
    for ( i1 = 0; i1 < cnt; ++i1) {
        scanf( "%d", &elemArray[i1] );
    }


    //first ouput "INput Values"

    printf( " Input Values:\n " );  

     for ( i2 = 0; i2 < cnt; ++i2) {
               printf( "%d\n", elemArray[i2] );
               printf("building tree0\n");
        }

    printf("building tree\n");
    TreeNode** root = (TreeNode**)malloc(sizeof(TreeNode*));
    TreeNode *root = NULL;
    build_Tree(root, elemArray, cnt );
    printf( "Preorder:\n ");

    //traverse
    //TreeNode* tempN = malloc(sizeof(TreeNode*));
    //tempN->data= 5;

    traverse( *root, PREORDER);             //pass the pointer of root to traverse the tree

    //traverse a single node 
    printf( "Inorder:\n ");

    printf( "Postorder:\n ");


    //Build tree with each element

    return 0;
}

void traverse( const TreeNode* root, const TraversalType type ) {

    if ( type == PREORDER) {
             if (root != NULL)
             {
                printf("%d", root->data);
                traverse( root->left, PREORDER);
                traverse( root-> right, PREORDER);
            }
    }
}




    /**
    void insertNode(TreeNode** root, TreeNode* new_node) {

       if (new_node-> data < *root-> data) {
          if (*root-> left == NULL) 
             *root-> left == new_node;
          else
            insert(*root->left, new_node);
       }

      if (new_node->data > *root->data) {
        if(*root-> right ==NULL)
          *root->right = new_node;
        else
          insert(*root->right, new_node);
      }
    }
    **/


//question1: what is the 

为 main 和 build_tree 编辑 2

void build_Tree(TreeNode** root, const int elements[], const int count) {

    //*root = malloc(sizeof(TreeNode));

    for ( i0 = 0; i0 < count; i0++ ){

        //create the node
        //
        TreeNode *current = *root; //define the current pointer to the root always
        TreeNode *parent = *root;
        //dont create node
        int data = elements[i0];
        TreeNode *newNode = getN(data);

        if (*root == NULL)
        {
            printf("First Node %d\n", elements[i0]); 
            *root = newNode;
        }
        else
        {
            printf("Next Node %d\n", elements[i0]); 
            while(current != NULL)
            {
                parent = current;
                if (current->data > data)
                    current = current->left;
                else if (current->data < data)
                    current = current->right;
            }

            if (parent->data > data)
                parent->left = newNode;
            else if (parent->data < data)
                parent->right = newNode;
        }
        //return root;
    }
}

    TreeNode* getN(int dataElem) {
        TreeNode *newNode = malloc(sizeof(*newNode));
        if (newNode != NULL)
        {
            newNode->data = dataElem;
            newNode->left = NULL;
            newNode->right = NULL;
        }

        return newNode;
    } 

int main( int argc, char *argv[] ) {

    //Throw error is *Argv[] is not an integer
    //assuming it was an integer
    int cnt = atoi( argv[1] );
    printf( "number is %d\n", cnt );
    //
    printf("Enter %i integer values to place in tree:\n", cnt);
    for ( i1 = 0; i1 < cnt; ++i1) {
        scanf( "%d", &elemArray[i1] );
    }


    //first ouput "INput Values"

    printf( " Input Values:\n " );  

     for ( i2 = 0; i2 < cnt; ++i2) {
               printf( "%d\n", elemArray[i2] );
               printf("building tree0\n");
        }

    printf("building tree\n");
    TreeNode* root; //= malloc(sizeof(TreeNode*));
    root = NULL;
    build_Tree(&root, elemArray, cnt );
    printf( "Preorder:\n ");

    //traverse
    //TreeNode* tempN = malloc(sizeof(TreeNode*));
    //tempN->data= 5;

    //traverse( *root, PREORDER);               //pass the pointer of root to traverse the tree

    //traverse a single node 
    printf( "Inorder:\n ");

    printf( "Postorder:\n ");


    //Build tree with each element

    return 0;
}

Answer 1

假设您创建了一个函数 addNodeToTree(TreeNode *root, int data)，将 root 节点和 data 作为参数传递给它.

现在在这个函数中，简单地创建另一个变量说 TreeNode *current = root 这将帮助我们基本上遍历树并将节点放置在其各自的位置，以及 TreeNode *newNode = NULL(这将成为要插入的新节点)。

现在在继续之前，为了实际放置节点，我们将首先检查 root 是否不为 null，即树是否为 EMPTY。为此，我们将测试:

if (root == NULL)
{
    newNode = malloc(sizeof(*newNode)); // else we can make a function for this 
                                        // thingy too. Creating a function too,
                                        // for you to look at.
    root = newNode;
}

如果树不是EMPTY，即它已经包含一个节点，那么我们将遍历树以找到放置新节点的位置。所以 else 部分将是这样的:

else
{
    parent = current = root;
    // This loop will actually help us, find the `parent`, 
    // of the `newNode`(which is to be inserted)
    while (current != NULL)
    {
        parent = current;
        if (current->data > data)
            current = current->left;
        else if (current->data < data)
            current = current->right;
    }
    // Now once, we have found, the node, under which the
    // newNode will be placed, now we have to check, whether
    // newNode will become a `left child/right child` of the 
    // parent.
    newNode = getNewNode(data);
    if (parent->data > data)
        parent->left = newNode;
    else if (parent->data < data)
        parent->right = newNode;


    return root;
}

TreeNode * getNewNode(int data)
{
    TreeNode *newNode = malloc(sizeof(*newNode));
    if (newNode != NULL)
    {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }

    return newNode;
}

现在 newNode 已被插入，您可以简单地以任意顺序遍历以查看树。

编辑 1:

这是一个有效的例子，看看这是否有意义。否则请提出任何可能出现的问题。

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

typedef struct TREENODE
{
    int data;
    struct TREENODE *left;
    struct TREENODE *right;
}TreeNode;

void display(TreeNode *node)
{
    printf("*********************************\n");
    printf("Address of Node: %p\n", node);
    printf("Data: %d\n", node->data);
    printf("Left Child: %p\n", node->left);
    printf("Right Child: %p\n", node->right);
    printf("*********************************\n");
}

TreeNode * getNewNode(int data)
{
    TreeNode *newNode = malloc(sizeof(*newNode));
    if (newNode != NULL)
    {
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
    }

    return newNode;
}

int getIntData(char *message)
{
    int value = 0;
    char buffer[BUFSIZ] = {'\0'};
    fputs(message, stdout);
    fgets(buffer, sizeof(buffer), stdin);
    sscanf(buffer, "%d", &value);

    return value;
}

TreeNode * addNodeToTree(TreeNode *root, int data)
{
    TreeNode *current = root, *parent = root;
    TreeNode *newNode = getNewNode(data);

    if (root == NULL)
    {
        root = newNode;
    }
    else
    {
        while(current != NULL)
        {
            parent = current;
            if (current->data > data)
                current = current->left;
            else if (current->data < data)
                current = current->right;
        }

        if (parent->data > data)
            parent->left = newNode;
        else if (parent->data < data)
            parent->right = newNode;
    }

    return root;
}

void inOrderTraversal(TreeNode *root)
{
    if (root != NULL)
    {
        inOrderTraversal(root->left);
        display(root);
        inOrderTraversal(root->right);
    }
}

int main(void)
{
    TreeNode *root = NULL;
    int data = 0;
    data = getIntData("Enter Data: ");
    root = addNodeToTree(root, data);
    data = getIntData("Enter Data: ");
    root = addNodeToTree(root, data);
    data = getIntData("Enter Data: ");
    root = addNodeToTree(root, data);
    inOrderTraversal(root);

    return EXIT_SUCCESS;
}

编辑 2:

要使 addNodeToTree(...) 实现指向指针的指针，只需将函数更改为:

void addNodeToTree(TreeNode **root, int data)
{
    TreeNode *current = *root;
    TreeNode *parent = *root;
    TreeNode *newNode = getNewNode(data);

    if (*root == NULL)
    {
        *root = newNode;
    }
    else
    {
        // same as before, just don't return anythingy, from the function.
        // As the function uses pointer to a pointer, hence whatever changes
        // are done, here will be reciprocated in the main function automatically
    }

    // no need to return anythingy
}

来自 main 的调用现在看起来像:

int main(void)
{
    TreeNode *root = NULL;
    int data = 0;
    data = getIntData("Enter Data: ");
    addNodeToTree(&root, data);
    // Just see the call to addNodeToTree(...), the rest is same, as before
}

编辑 3:

为了从数组中获取元素而不是直接将它们添加到树中，只需将 main 方法更改为以下形式:

int main(void)
{
    TreeNode *root = NULL;
    int element[5] = {19, 11, 5, 28, 25};
    int size = sizeof(element) / sizeof(element[0]);
    int counter = 0;
    for (counter = 0; counter < size; ++counter)
    {
        addNodeToTree(&root, element[counter]);
    }
    inOrderTraversal(root);

    return EXIT_SUCCESS;
}