c - 如何在二叉树中搜索与给定值 x 的匹配项？

Question

这是我的代码，这里我需要搜索一个值为整数类型的x的二叉树，并需要返回匹配节点的BTREE类型的指针窗口。

这里程序遇到了case2，但仍然没有搜索节点。我找不到我的错误。

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

    typedef struct tree
    {
        int data;
        struct tree *left;
        struct tree *right;
    }tree;

    int AddToArray(tree *node, int arr[], int i);
    tree *CreateNode(int data);
    tree *Insert(tree *node, int data);
    void PrintPreorder(tree *node);
    int count(tree *node);
    int compare(const void * a, const void * b);

    //-------------------------------------------------------------------------------------------------
    int main()
    {
        int i;
        int choice;
        int num;
        int count;
        int size;
        int *arr=NULL;
        tree *root=NULL;


         while (1)
        {
         printf("enter your choice \n 1.Insert into tree \n");
         printf("enter your choice \n 2.search element \n");
         scanf("%d",&choice);


        switch (choice)
         {
         case 1:

        printf("Enter the input : \n");
        scanf("%d",&num);

        root = Insert(root, 4);
        root = Insert(root, 3);
        root = Insert(root, 5);
        root = Insert(root, 10);
        root = Insert (root, 8);
        root = Insert (root, 7);
        root = Insert(root,num);

        break;

        case 2:
        printf("\n enter the element to be searched");
        scanf("%d",&num);
        for(i=0;i<100;i++)
         {
           if(arr[i]==num)   {
             printf("\n element found");
            break;
            } 
          }
          if(i==count)
             printf("\n element not found");

            break;



          }
        printf("\n***BINARY TREE (PREORDER)***\n");
        PrintPreorder(root);
        }


    }



        /*intf("\n\n***ARRAY***\n");
        arr = calloc(size, sizeof(int));
        AddToArray(root, arr, 0);
        qsort(arr,size,sizeof(int),compare);

        for (i=0; i<size; i++)
        {
            printf("arr[%d]: %d\n", i, arr[i]);
        }*/


    //-------------------------------------------------------------------------------------------------

    int compare(const void * a, const void * b)
    {
       return ( *(int*)a - *(int*)b );
    }

    int AddToArray(tree *node, int arr[], int i)
    {
         if(node == NULL)
              return i;


         arr[i] = node->data;
         i++;
         if(node->left != NULL)
              AddToArray(node->left, arr, i);
         if(node->right != NULL)
              AddToArray(node->right, arr, i);


         arr[i] = node->data;
         i++;

    }

    tree *CreateNode(int data)
    {
                    tree *node = (tree *)malloc(sizeof(tree));
                    node -> data = data;
                    node -> left = node -> right = NULL;
                    return node;
    }

    tree *Insert(tree *node, int data)
    {
            if(node==NULL)
            {
                    tree *temp;
                    temp = CreateNode(data);
                    return temp;
            }

            if(data >(node->data))
            {
                    node->right = Insert(node->right,data);
            }

            else if(data < (node->data))
            {
                    node->left = Insert(node->left,data);
            }

            /* Else there is nothing to do as the data is already in the tree. */
            return node;
    }

    void PrintPreorder(tree *node)
    {
            if(node==NULL)
            {
                    return;
            }
            printf("%d ",node->data);
            PrintPreorder(node->left);
            PrintPreorder(node->right);

    }

Answer 1

首先为arr分配内存您要求使用二叉树，但您的代码显示您正在使用它，就好像它是BST。[至于添加函数]。

回答

如果是没有排序的二叉树，则必须使用标准树遍历或 BFS 或 DFS 等搜索所有节点。

If it is `BST` then it will be easier. 
1. Check the value x=root.val return root
2. else if( root.val> x) return search(x,root.left);
3. else return search(x,root.right);

在 SO 中阅读有关 MCV 示例的一件事。 :)

注1:要分配数组，您可以使用arr=malloc(sizeof(int)*n);

注释 2:如果您使用数组，那么您将以这种方式存储它们

[ root root.left root.right root.left.left root.left.right root.right.left ... ]

     1
   /  \
  2    3
 / \  / \
4   5 6  7 

注释 3: 为什么在这种情况下使用数组..root 可以访问任何其他节点..如果您不想动态分配，则仅将它们存储在数组中否则，您只需在需要时动态插入必要的节点。

在 BST(二叉搜索树)中搜索的代码:

bool search(node * root, int x)
{
        if(root->val==x)
           return true;
        else
        {
            if(x<root->val) //value is smaller go to the left subtree
                return search(root->left,x);
            else
                return search(root->right,x);
         }
}

插入算法BST

struct node* insert(struct node* node, int val)
{

    if (node == NULL) 
    {
         struct node *temp = malloc(sizeof(struct node));
                 temp->val = val;
                 temp->left = temp->right = NULL;
                 return temp;
    }

    if (val < node->val)
        node->left  = insert(node->left, val);
    else if (val > node->val)
        node->right = insert(node->right,val);   

    /* return the (unchanged) node pointer */
    return node;
}

如果您使用二叉树

那么您还可以使用一些数组[就像我们在堆中所做的那样]或使用类似图形的结构(邻接表..)。这实际上取决于您的实现。

检查此链接以获得想法 - Binary tree implementation .

在二叉树中搜索

简单的把遍历代码改成这样就可以了..

int levelOrder_Search(struct node* root)
{
    struct Queue* queue = createQueue(SIZE);

    Enqueue(root, queue);

    while (!isEmpty(queue))
    {
        struct node* temp = Dequeue(queue);

        if(temp->data==x)
           return 1;   // found :-)

        if (temp->left)
            Enqueue(temp->left, queue);

        if (temp->right)
            Enqueue(temp->right, queue);
    }
    return 0;//not found
}