Создание бинарного дерева и функции поиска

Question

Я создаю двоичное дерево и хочу просто Поиск , но я хочу знать, сколько узлов посещают, чтобы найти значение. в функции поиска.

Вот файл слушателя

#ifndef INTBINARYTREE_H
#define INTBINARYTREE_H


class IntBinaryTree
{

  private:
    struct TreeNode
    {
      int value;       // The value in node .
      TreeNode *left;  //pointer to left node
      TreeNode *right;  // Pointer to right child node
    };
    TreeNode *root;
  //private member functions

  void insert(TreeNode *&,TreeNode *&);

  void displayInOrder(TreeNode *) const;
  void displayPreOrder(TreeNode *) const;
  void displayPostOrder(TreeNode *) const;



  public:
    IntBinaryTree()
    {
      root = nullptr;
    }


    // Binary search tree
  int searchNode(int);
  void insertNode(int);
  void displayInOrder() const
    {
      displayInOrder(root);
    }


#endif // INTBINARYTREE_H

А вот файл .cpp, который я хочу знать, как использовать функцию поиска, если значение не найдено равным нулю, и если значение найдено, каксколько узлов посещено?

#include "IntBinaryTree.h"

void IntBinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{

    if (nodePtr == nullptr)
        nodePtr=newNode;    // insert the node
    else if (newNode->value < nodePtr->value)  `//search the left branch`
        insert(nodePtr->left, newNode);
    else
        insert(nodePtr->right, newNode); //search the right branch

}

void IntBinaryTree::insertNode(int num)
{
    TreeNode *newNode= nullptr; // pointer to a new node

    //create a new node and store num in it

    newNode = new TreeNode;

    newNode->value= num;
    newNode->left = newNode->right = nullptr;

    //insert the node

    insert(root, newNode);

}
int IntBinaryTree::searchNode(int num)
{
  TreeNode *nodePtr = root;

  while(nodePtr)
  {

    if (nodePtr->value==num)
    {
      cout<<"Node found"<<num<<endl;
    }
    else if (num < nodePtr->value)
      nodePtr = nodePtr->left;  // look to the left side of the branch if less than the value of the node
    else
      nodePtr = nodePtr->right; // look to the right side of the if not less than the value .
  }

return 0;}

Вот главный файл

#include <iostream>
#include "IntBinaryTree.h"


using namespace std;

int main()
{
    IntBinaryTree tree;

    cout << "inserting nodes" << endl;
    tree.insertNode(5);
    tree.insertNode(8);
    tree.insertNode(3);
    tree.insertNode(12);
    tree.insertNode(9);
    cout << "Done.\n";
    tree.searchNode(5);
     return 0;}

Можете ли вы написать его для меня, отредактировать и кратко объяснить, как он работает?

Answer 1

Я предполагаю, что возвращаемое значение - это количество узлов, посещенных searchNode. Объявите локальную переменную, скажем, int visited = 0; перед циклом while {}, и увеличивайте ее при входе в цикл:

int visited = 0;

while (nodePtr)
{
    visited++; // examining another node...

    ... current code ... 
}

return visited;

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

Надеюсь, я правильно понял ваш вопрос.

Answer 2

Ваши включения неверны.

В вашем main.cpp есть #include "IntBinaryTree.cpp". Из-за этого элемент вставки (и многие другие) существуют дважды. Общее правило: никогда не включайте файлы cpp.

Просто удалите строку, и все будет в порядке.