搜索二叉树并打印有价值的子项

Question

因此，过去两周我度过了许多不眠之夜，试图编写一个我认为简单的程序：我试图从特定文件中的整数列表创建一个二叉树。这些数字被插入到二叉树中。然后，我提示用户输入一个值来搜索以查看是否是一个节点。如果是，那么我打印搜索值的左右子项。不幸的是，我一生都无法让我的代码正常工作。非常感谢任何帮助！

#define kFileName   "../../Data.txt"

struct Node {
    int           number;
    struct Node   *left, *right;
};

extern struct Node *gRootNodePtr;
void    BuildTree( void );
int     GetNumberFromFile( int *numPtr, FILE *fp );
void    InsertInTree( int num );
void    AddNode( struct Node *newNodePtr, struct Node **curNodePtrPtr );
void    SearchTree( int num, struct Node *nodePtr );
void    PrintChild( struct Node *nodePtr );

void InsertInTree(int num) {
    struct Node *nodePtr;

    nodePtr = malloc(sizeof(struct Node));

    if (nodePtr == NULL)
        DoError("Could not allocate memory!\n");

    nodePtr->number = num;
    nodePtr->left = NULL;
    nodePtr->right = NULL;

    AddNode(nodePtr, &gRootNodePtr);
}

void AddNode(struct Node *newNodePtr, struct Node **curNodePtrPtr) {
    if (*curNodePtrPtr == NULL)
        *curNodePtrPtr = newNodePtr;
    else if (newNodePtr->number < (*curNodePtrPtr)->number)
        AddNode(newNodePtr, &((*curNodePtrPtr)->left));
    else
        AddNode(newNodePtr, &((*curNodePtrPtr)->right));
    }

void SearchTree(int num, struct Node *nodePtr) {
    if (nodePtr == NULL)
        return;

    printf("Enter number to be searched: ");
    scanf("%d", &num);
    SearchTree(num, nodePtr);
    PrintChild(nodePtr->left);
    printChild(nodePtr->right);
}

void PrintChild( struct Node *nodePtr) {
    printf("%d ", nodePtr->number);
}

void BuildTree(void) {
    int     num;
    FILE    *fp;

    if ((fp = fopen( kFileName, "r")) == NULL)
        printf("Could not read numbers file!\n");

    printf("Numbers:   ");

    while (GetNumberFromFile( &num, fp )) {
        printf("%d, ", num);
        InsertInTree(num);
    }

    printf("\n-------\n");

    fclose(fp);
}

int GetNumberFromFile(int *numPtr, FILE *fp)
{
    if (fscanf(fp, "%d\n", numPtr) == EOF)
        return false;
    else
        return true;
}

int main(int argc, char* argv[]) {
    gRootNodePtr = NULL;
    int num=NULL;
    BuildTree();
    NodePtr SearchTree(num, gRootNodePtr);

return;
}

Answer 1

这是一个足够不同的东西，它不仅直接给你答案，而且足够相似，它可能会提供一些帮助和/或灵感。只是为了一笑，这演示了递归和迭代树遍历。

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

typedef struct node {
    struct node *left;
    struct node *right;
    char *string;
} node;

node *root; /* automatically initialized to NULL */

node *make_node(char const *string) {
    node *ret = malloc(sizeof(node));
    if (ret == NULL)
        return NULL;
    ret->string = malloc(strlen(string) + 1);
    if (ret->string == NULL) {
        free(ret);
        return NULL;
    }
    strcpy(ret->string, string);
    ret->left = NULL;
    ret->right = NULL;
    return ret;
}

void del_node(node *node) {
    free(node->string);
    free(node);
}

int insert(const char *string, node **root) {
    if (*root == NULL)
        *root = make_node(string);
    else {
        node *iter = *root;
        for(;;) {
            int cmp = strcmp(string, iter->string);
            if ( 0 == cmp)
                /* duplicate string - ignore it. */
                return 0;
            else if (1 == cmp) {
                if (NULL == iter->right ) {
                    iter->right = make_node(string);
                    break;
                }
                else iter=iter->right;
            }
            else if ( NULL == iter->left ) {
                iter->left = make_node(string);
                break;
            }
            else
                iter = iter->left;
        }
    }
    return 1;
}

void print(node *root) {
    if (root->left != NULL )
        print(root->left);
    fputs(root->string, stdout);
    if ( root->right != NULL )
        print(root->right);
}

int main() {
    char line[100];

    while (fgets(line, 100, stdin))
        insert(line, &root);
    print(root);
    return 0;
}

Answer 2

循序渐进。

创建一个新函数 PrintLeaves。进行所需的更改后，将 main 修改为

int main() {
    InsertInTree(42);
    PrintLeaves();
    return 0;
}

并进行调整，直到打印出 42。
然后添加一些随机的 InsertInTree ...并调整...

Answer 3

SearchTree 错误可能源于它在 main() 中的使用。 NodePtr 在那里做什么？ SearchTree 被宣布无效。另外，指针中的整数可能是由于您使用了 NULL，它可以是 (void*)0。使用

int num = 0;

Answer 4

您没有确切说明它如何不起作用，但很明显您不应该提示您从递归 SearchTree 例程中搜索要搜索的值。

除此之外，看起来你们已经很接近了。尝试这样的事情：

    void    SearchTree( int num, struct Node *nodePtr ) {
        if ( nodePtr == NULL )
            return;

        if (NodePtr->Number == num)
        {
           PrintChild( nodePtr->left );
           PrintChild( nodePtr->right );
        }
        else
        {
          SearchTree(num, nodePtr->left );
          SearchTree(num, nodePtr->right );
        }
    }

Answer 5

无需深入研究代码，以下是人们通常如何递归地搜索 BST 的方法：（

伪代码）

visit(node,value):
   if node is null: // empty tree
       return
   if node->key==value: // found one
       // do whatever it is you want to do with it
   if node->key<=value: // less than or equal keys are to the left 
      visit(node->left,value)
   else: // greater keys are to the right
      visit(node->right,value)  

Answer 6

我编译了你的代码。它甚至做了一些事情。我试着不去碰它太多。只是为了让它有所作为，因为您的代码中没有二叉树，并且不清楚它的用途。请参阅下面的代码。但在此之前：
1. 您不是在构建二叉树，而是在构建链表。也许，您需要排序数字的双链表？如果是，我在此处发布的代码不会对其属性进行排序，仅供参考。
2.也许，您专门在这里发布了堆栈溢出有害代码，但您应该关心用户输入、指针和其他所有内容（其他用户对此有很好的答案）。
3. 最后，你到底想做什么？

代码

#include <stdio.h>
#include <malloc/malloc.h>
#define kFileName   "Data.txt"

struct Node {
    int         number;
    struct Node     *left, *right;
};

struct Node *gRootNodePtr;

void    BuildTree( void );
int     GetNumberFromFile( int *numPtr, FILE *fp );
void    InsertInTree( int num );
void    AddNode( struct Node *newNodePtr, struct Node **curNodePtrPtr );
void    SearchTree( int num, struct Node *nodePtr );
void    PrintChild( struct Node *nodePtr );

void    InsertInTree( int num ) {
    struct Node *nodePtr;

    nodePtr = (struct Node *) malloc( sizeof( struct Node ) );

    if ( nodePtr == NULL ) {
        printf("Could not allocate memory!\n" );
                return;
        }

    nodePtr->number = num;
    nodePtr->left = NULL;
    nodePtr->right = NULL;

    AddNode( nodePtr, &gRootNodePtr );
}

void    AddNode( struct Node *newNodePtr, struct Node **curNodePtrPtr ) {
if ( *curNodePtrPtr == NULL )
        *curNodePtrPtr = newNodePtr;
    else if ( newNodePtr->number < (*curNodePtrPtr)->number )
        AddNode( newNodePtr, &( (*curNodePtrPtr)->left ) );
    else
        AddNode( newNodePtr, &( (*curNodePtrPtr)->right ) );
}

void search(struct Node * nodePtr) {
        int num;
    printf("Enter number to be searched: ");
    scanf("%d", &num);
        SearchTree(num, nodePtr);
}

void  SearchTree(int num, struct Node *nodePtr ) {
    if ( nodePtr == NULL )
        return;

        if(num == nodePtr->number) {
            if(nodePtr->left != NULL) PrintChild(nodePtr->left);
            PrintChild(nodePtr);
            if(nodePtr->right != NULL) PrintChild(nodePtr->right);
            printf("\n");
            return;
        } else if(num > nodePtr->number) {
            SearchTree(num, nodePtr->right);
        } else {
            SearchTree(num, nodePtr->left);
        }
}

void    PrintChild( struct Node *nodePtr ) {
    printf( "%d ", nodePtr->number );
}

void    BuildTree( void )
{
    int     num;
    FILE    *fp;

    if ( ( fp = fopen( "Data.txt", "r" ) ) == NULL )
        printf( "Could not read numbers file!\n" );

    printf( "Numbers:   " );

    while ( GetNumberFromFile( &num, fp ) )
    {
        printf( "%d, ", num );
        InsertInTree( num );
    }

    printf( "\n-------\n" );

    fclose( fp );
}

int GetNumberFromFile( int *numPtr, FILE *fp )
{
    if ( fscanf( fp, "%d\n", numPtr ) == EOF )
        return false;
    else
        return true;
}

int main(int argc, char* argv[])
{
    gRootNodePtr = NULL;
    BuildTree();
        search(gRootNodePtr);
        return;
}

Answer 7

这是我的二叉树代码及其在 php 中的所有操作：

<?php

class Node
{
公共$数据；
公共$leftChild;
公共$rightChild;

公共函数 __construct($data)
{
$this->data=$data;
$this->leftChild=null;
$this->rightChild=null;
}
公共函数 disp_data()
{
回显 $this->data;
}

}//结束类Node
二叉树类
{
公共$根；
//公共$s;
公共函数 __construct()
{
$this->root=null;
//$this->s=file_get_contents('store');

}
//显示树的函数
公共函数显示()
{
$this->display_tree($this->root);

}
公共函数display_tree($local_root)
{

if($local_root==null)
返回;
$this->display_tree($local_root->leftChild);
echo $local_root->data."
";
$this->display_tree($local_root->rightChild);

}
// 插入新节点的函数
公共函数插入($key)
{
$newnode=新节点($key);
if($this->root==null)
{
$this->root=$newnode;
返回;
}
别的
{
$parent=$this->root;
$current=$this->root;
而（真）
{
$父=$当前；
//$this->find_order($key,$current->data);
if($key==($this->find_order($key,$current->data)))
{
$current=$current->leftChild;
如果（$当前==空）
{
$parent->leftChild=$newnode;
返回;
}//结束if2
}//结束if1
别的
{
$current=$current->rightChild;
如果（$当前==空）
{
$parent->rightChild=$newnode;
返回；
} //结束 if1
} //其他结束
}//结束while循环
}//end else

} //结束插入函数

//搜索特定节点的函数
公共函数查找（$key）
{
$current=$this->root;
while($当前->数据!=$key)
{
if($key==$this->find_order($key,$current->data))
{
$current=$current->leftChild;
}
别的
{
$current=$current->rightChild;
}
如果（$当前==空）
返回（空）；

      }
     return($current->data); 

}//结束搜索函数
公共函数delete1($key)
{
$current=$this->root;
$parent=$this->root;

$isLeftChild=true;
 while($current->data!=$key)
      {
       $parent=$current;
       if($key==($this->find_order($key,$current->data)))
         {
          $current=$current->leftChild;
          $isLeftChild=true;
         }   
       else
         {
          $current=$current->rightChild;
          $isLeftChild=false;   
         } 
        if($current==null)
          return(null);
      }//end while loop 

  echo "<br/><br/>Node to delete:".$current->data;
 //to delete a leaf node 
 if($current->leftChild==null&&$current->rightChild==null)
   {
       if($current==$this->root)
          $this->root=null;  
      else if($isLeftChild==true)
       {
        $parent->leftChild=null;
       }  
     else
       {
        $parent->rightChild=null;
       }
     return($current);       
   }//end if1
 //to delete a node having a leftChild 

else if($current->rightChild==null)
{
if($current==$this->root)
$this->root=$current->leftChild;
否则如果($isLeftChild==true)
{
$parent->leftChild=$current->leftChild;
}
别的
{
$parent->rightChild=$current->leftChild;
}
返回（$当前）；
}//结束 else if1
//删除具有rightChild的节点
else if($current->leftChild==null)
{
if($current==$this->root)
$this->root=$current->rightChild;
否则如果($isLeftChild==true)
{
$parent->leftChild=$current->rightChild;
}
别的
{
$parent->rightChild=$current->rightChild;
}
返回（$当前）；
}
//删除有两个孩子的节点
别的
{
$successor=$this->get_successor($current);
if($current==$this->root)
{
$this->root=$successor;

      }
    else if($isLeftChild==true)
      {
       $parent->leftChild=$successor;
      }
    else
      {
       $parent->rightChild=$successor;
      }     
     $successor->leftChild=$current->leftChild;
    return($current);
   }   

}//结束删除节点的函数
//查找后继节点的函数
公共函数 get_successor($delNode)
{
$succParent=$delNode;
$后继者=$delNode；
$temp=$delNode->rightChild;
while($temp!=null)
{
$succParent=$继任者；
$后继者=$temp；
$temp=$temp->leftChild;
}
if($successor!=$delNode->rightChild)
{
$succParent->leftChild=$successor->rightChild;
$successor->rightChild=$delNode->rightChild;
}
返回（$后继者）；
}
//查找两个字符串的顺序的函数
公共函数 find_order($str1,$str2)
{
$str1=strtolower($str1);
$str2=strtolower($str2);
$i=0;
$j=0;

 $p1=$str1[i];
 $p2=$str2[j]; 

而（真）
{
如果（或（$p1）

       return($str1);
     }
  else
     {
       if(ord($p1)==ord($p2))
         {
          $p1=$str1[++$i];
          $p2=$str2[++$j];
          continue;
         }
      return($str2); 
     }

}//end while

} //结束函数查找字符串顺序

public function is_empty()
{
if($this->root==null)
返回（真）；
别的
返回（假）；
}
}//结束二叉树类
？>