Нахождение предков узла в двоичном дереве только со значением узла

Question

Я пытаюсь завершить sh метод, который принимает значение, я должен РЕКУРСИВНО найти предков узла с совпадающим значением в двоичном дереве, так что пока у меня возникают небольшие проблемы с рекурсивная часть, вот класс, с которым я работаю:

#ifndef TREETYPE_H
#define TREETYPE_H
#include <string>
#include <fstream>
#include "QueType.h"
using namespace std;

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template<class ItemType>
struct TreeNode;

template <class ItemType>
class TreeType
{
public:
  TreeType();                     // constructor
 ~TreeType();                    // destructor
  TreeType(const TreeType<ItemType>& originalTree);
  void operator=(const TreeType<ItemType>& originalTree);
  // copy constructor
  void MakeEmpty();
  bool IsEmpty() const;
  bool IsFull() const;
  int GetLength() const; 
  ItemType GetItem(ItemType item, bool& found);
  void PutItem(ItemType item);
  void DeleteItem(ItemType item);
  void ResetTree(OrderType order); 
  ItemType GetNextItem(OrderType order, bool& finished);
  void Print(ofstream& outFile) const;
  string Ancestors(ItemType item) const;
  string AncestorsNext(TreeNode<ItemType>* node, ItemType item) const;
private:
  TreeNode<ItemType>* root;
  QueType<ItemType> preQue;
  QueType<ItemType> inQue;
  QueType<ItemType> postQue;
};

template <class ItemType>
struct TreeNode
{
  ItemType info;
  TreeNode* left;
  TreeNode* right;
};

И вот что у меня есть с моим методом предков:

// This recursive function will return the ancestors of item in reverse order.
template <class ItemType>
string TreeType<ItemType>::Ancestors(ItemType item) const{
    string out="";
    TreeNode<ItemType>* temp=root;
    if(root==nullptr || root->info==item){
        return "Value has no ancestors";
    }
    else{

        if(temp->info>item){
            out+=temp->info;
            temp=temp->left;
            TreeType<ItemType>::Ancestors(temp->info);
        }
        if(temp->info<item){
            out+=temp->info;
            temp=temp->right;
            TreeType<ItemType>::Ancestors(temp->info);
        }
    }

    return out;

}

Я застрял на том, как я могу использовать рекурсию для проверяйте следующее значение в дереве с помощью моей переменной temp, если оно всегда устанавливается на root каждый раз. Если есть другой способ, я все уши!

Answer 1

Если есть другой способ, которым я все уши!

Рассмотрим:

a) передать «вектор TreeNodes» в качестве второго параметра в ваш метод Ancestors () ,

b) Во время рекурсивного поиска (сначала я использовал глубину), используйте push_back в векторе, чтобы ЗАХВАТИТЬ посещаемых предков (узел *) во время поиска,

c) и когда значение будет найдено, верните интересующего предка.

d) Если не найден (в текущей ветви), используйте pop_back во время «удаления проклятия», чтобы удалить нежелательный узел (узлы) предка.

---

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

Пример вывода: (поиск узлов, сумма которых равна -5)

   BTree_t::dfVisitSum(-5)   
     @ level 3:    -2   -3 
     @ level 2:     0   -2   -3 

В дереве: (т.е. тестовый ввод)

BTree_t::showTallView():  (balance: 0  sz: 19)

                -3 
           -2 
                -1 
       0 
                 1 
            2 
                      3 
                 4 
  5 
                 6 
            7 
                      8 
                 9 
      10 
                11 
           12 
                     13 
                14 
                     42 

---

// target-sum-search
int Node_t::sumSearch(const int targetSum, NVec_t& nodeLog)
{
   int reportCount = 0;
   // diag only  std::cout << "  Node_t::sumSearch() " << m_payLoad << std::endl;

   // CAPTURE visit to log
   nodeLog.push_back(this); // trace node route (depth-first-search style)

   if(m_left)
   {
      reportCount += m_left->sumSearch(targetSum, nodeLog);  // RECURSE
   }

   {
      size_t   startLvl = nodeLog[0]->m_lvl; // used in report

      int accumulateSum = 0;
      for (size_t i = 0; i < nodeLog.size(); ++i)
         accumulateSum += nodeLog[i]->m_payLoad;

      if (targetSum == accumulateSum)
      {
         std::stringstream reportLabelSS;
         reportLabelSS << "\n     @ level " << startLvl << ":";
         std::cout << showNVec(nodeLog, reportLabelSS.str());
         reportCount += 1;
      }
   }

   if(m_right)
   {
      reportCount += m_right->sumSearch(targetSum, nodeLog);  // RECURSE
   }


   // REMOVE this node visit from log
   nodeLog.pop_back(); // removes last nodeLog element  // DE-CURSE

   return(reportCount); // report count
}

Answer 2

Я застрял на том, как я могу использовать рекурсию для проверки следующего значения в дереве с моей временной переменной, если оно просто устанавливается на root каждый раз.

---

Это распространенная ошибка с простое решение. (Но, возможно, нет, если вы не можете добавить метод)

По сути, вы пытаетесь сделать слишком много вещей в одной функции.

Простое решение состоит в том, чтобы разделить текущую функцию на 2 функции,

а) одна, которая обрабатывает инициализацию того, где начать поиск, которая не является рекурсивной,

b) и другая, которая выполняет рекурсию.

Я надеюсь ниже приводится достаточно подсказок для вас (поскольку я не практиковался с шаблонами)

template <class ItemType>
string TreeType<ItemType>::Ancestors(ItemType item) const
{
    string out = AncestorsR(item, root)  // invoke recursive funct
    return out;
}

template <class ItemType>
string TreeType<ItemType>::AncestorsR(ItemType item,
                           TreeNode<ItemType>* temp) const
{
    string out="";

    if(temp==nullptr || temp->info==item)
    {
        return "Value has no ancestors";
    }
    else
    {
        if(temp->info>item)
        {
            out+=temp->info;
            temp=temp->left;
            TreeType<ItemType>::Ancestors(temp->info);
        }
        if(temp->info<item)
        {
            out+=temp->info;
            temp=temp->right;
            TreeType<ItemType>::Ancestors(temp->info);
        }
    }
    return out;
}

Answer 3

Вместо того, чтобы делать рекурсию, вы можете просто инициализировать temp = root, как вы это сделали, а затем использовать некоторое время l oop:

while ( temp->left && temp->right && temp->info != item )
{
    if ( temp->info > item )
    {
        // your ancestor stuff
        temp = temp->left;
    }
    else if ( temp->info < item )
    {
        // your ancestor stuff
        temp = temp->right;
    }
}