在只有节点值的二叉树中查找节点的祖先

Question

我正在尝试完成一个接受值的方法，我必须递归地在二叉树中找到具有匹配值的节点的祖先，到目前为止我运行递归部分有点麻烦，这是 class 我正在使用的：

#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 变量，如果它每次都设置为根。如果有其他方法我洗耳恭听！

Answer 1

不用递归，你可以简单地初始化 temp=root，然后使用 while 循环：

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;
    }
}

Answer 2

If there's another way im all ears!

考虑：

a) 将 "vector of TreeNodes" 作为第二个参数传递给 Ancestors() 方法。

b) 在递归搜索期间（我首先使用深度），在向量中使用 push_back 以在搜索期间捕获访问的祖先（节点*），

c) 并且当找到值时，return 感兴趣的祖先。

d) 如果未找到（在当前分支中），请在 'de-cursion' 期间使用 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 3

我一直在思考如何使用递归来检查树中的下一个值，如果它每次都被设置为根的话。

这是一个简单的解决方案的常见错误。（但如果您不能添加方法，则可能不会）

本质上，您试图在一个函数中做太多事情。

简单的解决方案是将当前函数拆分为 2 个函数，

a) 处理从哪里开始搜索的初始化，它不是递归的，

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;
}

在只有节点值的二叉树中查找节点的祖先

Finding the ancestors of a node in a binary tree with only the value of a node

c++

binary-tree

ancestor

data-structures