Поиск пути к двоичному дереву C ++ - PullRequest
Новая
       11

Поиск пути к двоичному дереву C ++

0 голосов
/ 09 марта 2019

У меня есть вопрос относительно нахождения суммы пути двоичного дерева int.Это для колледжа, поэтому требования следующие: возьмите код из Lab Sheet 3B (Binary Tree) для двоичного дерева целых чисел и закодируйте метод с именем hasPathSum (), который дает двоичное дерево и сумму, возвращает true, еслиУ дерева есть путь от корня к листу, так что сложение всех значений вдоль пути равно заданной сумме.Вернуть false, если такой путь не найден.Прототип функции: 

int hasPathSum(struct node* node, int sum)

Примечание: «путь от корня к листу» - это последовательность узлов в дереве, начинающаяся с корневого узла и продолжающаяся вниз до листа (узла без дочерних элементов),Пустое дерево не содержит путей от корня к листу.Так, например, следующее дерево имеет ровно четыре пути от корня к листу: 

5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1

Для этой задачи нас будет интересовать сумма значений такого пути - например,сумма значений на пути 5-4-11-7 составляет 5 + 4 + 11 + 7 = 27.

У меня проблемы с этим.У меня есть двоичное дерево, но функция hasPathSum () требует пропуск узла, а не дерева.Я не могу понять, как это сделать.Я также не знаю, как найти сумму пути от корня до листа (тело hasPathSum также).Это должно быть сделано рекурсивно.

Любая помощь очень ценится.

Вот мой класс узла: 

#include <stdio.h>
#pragma once
struct TreeNode
{
public:
    friend class BinaryTree;
    TreeNode(int theData) : data(theData) {}
    bool isLeaf();
private:
    int data;
    TreeNode *leftlink;
    TreeNode *rightLink;
};

Вот файл заголовка BinaryTree: 

#include "TreeNode.h"
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;

#pragma once
class BinaryTree
{
public:
    BinaryTree();
    void add(int toadd);
    int height();
    void inorderShow() const;
    int hasPathSum(TreeNode * tree, int sum);
private:
    void add(TreeNode *toAdd, TreeNode *& addHere);
    int height(TreeNode *& root);
    TreeNode *root;
    void inorderShow(TreeNode *subTree) const;
};

И мой cpp-файл BinaryTree: 

#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
}

void BinaryTree::add(int toAdd)
{
    TreeNode *node = new TreeNode(toAdd);
    add(node, root);
}

int BinaryTree::height()
{
    return height(root);
}

void BinaryTree::add(TreeNode * toAdd, TreeNode *& addHere)
{
    if (addHere == NULL)
        addHere = toAdd;
    else if (toAdd->data < addHere->data)
        add(toAdd, addHere->leftlink);
    else //toAdd->data >= addHere->data
        add(toAdd, addHere->rightLink);
}

int BinaryTree::height(TreeNode *& n)
{
    if (n == NULL)
        return -1;
    else
        return 1 + max(height(n->leftlink), height(n->rightLink));
}

void BinaryTree::inorderShow(TreeNode * subTree) const
{
    if (subTree != NULL)
    {
        inorderShow(subTree->leftlink);
        cout << subTree->data << " ";
        inorderShow(subTree->rightLink);
    }
}

void BinaryTree::inorderShow() const
{
    inorderShow(root);
}

int BinaryTree::hasPathSum(TreeNode * tree, int sum)
{

}

В main.cpp у меня есть дерево следующим образом: 

#include <iostream>
#include "BinaryTree.h"
#include "TreeNode.h"
using namespace std;

int main()
{
    BinaryTree tree;
    tree.add(5);
    tree.add(6);
    tree.add(3);
    tree.add(4);
    tree.add(9);
    tree.add(11);
    cout << "Height of the tree is: ";
    cout << tree.height() << " ";

    cout << "\nIn Order Show:" << endl;
    tree.inorderShow();

    cout << "Root to leaft path: " << endl;

    cout << endl;
    system("pause");
    return 0;
}

Кто-то может объяснить, как я могувыполнить эту задачу и удовлетворить требования (иначе не меняйте параметры функции hasPathSum ()). Я был бы очень признателен.

1 Ответ

0 голосов
/ 09 марта 2019

Мне кажется, что требование неверно (или, возможно, запутано)

и закодируйте метод hasPathSum (), который дает двоичное дерево и сумму

учитывая, что это метод класса двоичного дерева, дерево передается неявно, поэтому единственным явным параметром является сумма.Таким образом, метод должен быть объявлен как 

class BinaryTree
{
    ...
    bool hasPathSum(int sum);
    ...
};

Однако данная подпись -

int hasPathSum (struct node * node, int sum)

с неправильным типом возврата (int, а не bool) и необъяснимым параметром node.

Вот как я бы организовал решение, поскольку оно включает два метода, возможно, объясняет путаницу. 

class BinaryTree
{
    ...
public:
    bool hasPathSum(int sum) { return hasPathSumHelper(root, sum); }
    ...
private:
    static bool hasPathSumHelper(TreeNode* node, int sum);
};

Публичный метод hasPathSum имеет подпись, подразумеваемую описанием проблемы (единственная подпись, которая имеет смысл).Он просто вызывает закрытый метод hasPathSumHelper, передавая корневой узел и сумму, это решает проблему передачи частного корневого узла.

Метод hasPathSumHelper является рекурсивной подпрограммой, где реальная работасделано (оставлено для реализации).Публичный hasPathSum просто запускает вычисления, вызывая этот метод.

Когда вы думаете о том, как реализовать hasPathSumHelper, вам может быть полезно добавить дополнительные параметры (параметр sum_so_far, который, каквы спускаетесь по дереву, это сумма всех узлов над вами имеет смысл для меня).Это нормально, потому что это приватный метод, вы можете добавить то, что вам нравится.

...