c++ - 如何打印 bst 中祖父母是五的倍数的节点？

Question

很抱歉，这是我第一次在 stackoverflow 中提问。我刚刚阅读了常见问题解答，就知道我违反了规则。我不只是应对和粘贴问题。我使用顺序遍历方法进行递归并检查节点是否为五的倍数，我不知道下一步该做什么。我应该使用标志来检查一些东西吗？

void findNodes(BSTNode<Key,E> *root) const
{
    if(root==NULL) return;
    else
    {
        if(root->key()%5==0)//I know it's wrong, but I don't know what to do
        {
            findNodes(root->left());
            cout<<root->key()<<" ";
            findNodes(root->right());
        }
        else
        {
            findNodes(root->left());
            findNodes(root->right());
        }

    }
}

Answer 1

打印祖父母是 5 的倍数的节点很复杂，因为您必须“向上”查找树。如果您将问题视为找到所有 5 的倍数的节点并打印它们的孙子节点，则会更容易，因为您只需沿着树向下走。

void printGrandChildren(BSTNode<Key,E> *root,int level) const{
    if(!root) return;
    if(level == 2){
         cout<<root->key()<<" ";
         return;


    }else{
        printGrandChildren(root->left(),level+1);
        printGrandChildren(root->right(),level+1);

     }

}

然后将您的 findNodes 修改为

void findNodes(BSTNode<Key,E> *root) const
{
    if(root==NULL) return;
    else
    {
        if(root->key()%5==0)
        {
            printGrandChildren(root,0);
        }
        else
        {
            findNodes(root->left());
            findNodes(root->right());
        }

    }
}

Answer 2

尝试这个：

int arr[height_of_the_tree]; //arr[10000000] if needed;

void findNodes(BSTNode<Key,E> *root,int level) const {
  if(root==NULL) return;
  arr[level] = root -> key();
  findNodes(root -> left(), level + 1);
  if(2 <= level && arr[level - 2] % 5 == 0) cout << root->key() << " ";
  findNodes(root -> right(), level + 1);
}

int main() {
  ...
  findNodes(Binary_search_tree -> root,0);
  ...
}

Answer 3

如果你只是想打印我们所有的子节点，它们的祖先的键是 5 的倍数，那么一种方法是将 a 传递bool给你的 findNodes 函数来存储这个事实。

类似于以下内容：

void findNodes(BSTNode<Key,E>* node, bool ancesterIsMultOf5) const
{
    if (node)
    {
        if (ancesterIsMultOf5)
            std::cout << node->key() << std::endl;

        ancesterIsMultOf5 |= (node->key() % 5 == 0); 

        findNodes(node->left(), ancesterIsMultOf5);            
        findNodes(node->right(), ancesterIsMultOf5);            
    }
} 

或者，如果您尝试绘制树，之前已经回答过：C How to "draw" a Binary Tree to the console

Answer 4

替换以下

    cout<<root->key()<<" ";

和

    if(root->left)
    {
        if(root->left->left)
            cout<<root->left->left->key()<< " ";
        if(root->left->right)
            cout<<root->left->right->key()<< " ";
    }
    if(root->right)
    {
        if(root->right->left)
            cout<<root->right->left->key()<< " ";
        if(root->right->right)
            cout<<root->right->right->key()<< " ";

    }