Нужна помощь в поиске бинарного дерева - PullRequest
Новая
       6

Нужна помощь в поиске бинарного дерева

0 голосов
/ 21 апреля 2020 
trav.h

#include <map>
#include <iostream>

class Tree
{
    Tree *left;
    Tree *right;
    int node;

    static std::map<int, Tree *> allNodes;

public:
    Tree(int n, Tree *l = 0, Tree *r = 0) : left(l), right(r), node(n)
    {
        allNodes[n] = this;
    }

    int GetNode() { return node; }

    void Insert(Tree *newnode)
    {

        if (newnode->node == this->node)
        {
        }
        // skip dup
        else if (newnode->node < this->node)
        {
            left = newnode;
            cout << "left" << left->node << endl;
        }
        else if (newnode->node > this->node)
        {
            right = newnode;
            cout << "right" << right->node << endl;
        }
    }

    int Find(int node)
    {
        if (node == this->node){}
        // skip dup
        else if (node < this->node)
        {
            return left->node;
        }
        else if (node > this->node)
        {
            return right->node;
        }
    }

    // print does an inorder search
    void Print(Tree *root)
    {
        if (root == nullptr)
        {
            return;
        }

        Print(root->left);
        cout << root->node << endl;
        Print(root->right);
    }
};

trav.cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#include "trav.h"

std::map<int, Tree *> Tree::allNodes;

// trav print
// trav find X

int main(int argc, char *argv[])
{
    if (argc < 2)
        return 0;

    string cmd(argv[1]);

    // READ IN THE INTEGERS
    vector<int> ids;
    int input;
    while (cin >> input)
    {
        ids.push_back(input);
    }

    // MAKE NODES FROM THE INTEGERS
    vector<Tree *> nodes;
    for (int id : ids)
    {
        nodes.push_back(new Tree(id));
    }

    if (ids.size() == 0)
        return -1;

    // PUT NODES INTO A TREE USING Insert
    Tree *theTree = nodes[0];

    if (theTree == nullptr)
        return -1;

    for (auto n : nodes)
    {
        theTree->Insert(n);
    }

    // PRINT TREE
    if (cmd == "print")
        theTree->Print(theTree);

    else if (cmd == "find")
    {
        string cmd2 = argv[2];
        int num = stoi(cmd2);
        int result = theTree-> Find(num);
        if(result!=0)
            cout<<num<<endl;
        else
            cout<<"-1"<<endl;
    }

    return 0;
}

Возникли проблемы при создании Find ()

  1. , выполните обход дерева по порядку и распечатайте обход
  2. , найдите значение в дереве и распечатайте его, если найдено

Первое действие запускается, когда argv [1] == "print". Если это так, выполните обход по порядку и напечатайте каждый узел дерева, по одному узлу на строку вывода. Обход по порядку означает прохождение через левое поддерево (если оно существует), затем распечатывает текущий узел, затем пересекает правое поддерево (если оно существует).

Второе действие запускается, когда argv [1] == "найти". Если это так, найдите в дереве argv [2] (строку, которую вам нужно будет преобразовать в int). Если найдено, выведите int. Если не найдено, выведите -1. Формат вывода должен быть одной строкой:

Ответы [ 2 ]

0 голосов
/ 21 апреля 2020

Я внес несколько изменений в методы Insert и Find: 

void Insert(Tree *newnode)
{
  // skip dup
  if (newnode->node == this->node)
  {
  }
  else if (newnode->node < this->node)
  {
    if(left != nullptr)
    {
      left -> Insert(newnode);
    }
    else 
    {
      left = newnode;
    }
  }
  else if (newnode->node > this->node)
  {
    if(right != nullptr)
    {
      right -> Insert(newnode);
    }
    else
    {
      right = newnode;
    }
  }
}

// 1 if found,
// 0 if not found
int Find(int node)
{
  if (node == this->node)
  {
    return 1;
  }
  else if (node < this->node)
  {
    if(left == nullptr)
    {
      return 0;
    }
    return left->Find(node);
  }
  else
  {
    if(right == nullptr)
    {
      return 0;
    }
    return right->Find(node);
  }

}

Insert проверьте, есть ли у текущего узла уже left или right, если он имеет, вставьте влево или вправо, в противном случае установите влево или вправо. Аналогичная проверка выполняется для Find. Надеюсь, это поможет.

0 голосов
/ 21 апреля 2020

Есть некоторые ошибки.

Ваш метод Insert () добавляет только новый узел на left или right. Если эти указатели все еще равны NULL, это нормально. В противном случае вы должны зацикливаться на них. Нет рекурсивного вызова Insert().

. И у метода Find() также есть проблема, которая уже обнаружена при включении предупреждений (g++ -Wall ....): если значение node соответствует запросу ничего не делает. Нет возвращаемого значения, поэтому он будет возвращать неопределенное значение. Отсутствует return 0; здесь.

...