C ++ функция для заполнения правой части дерева

Question

Проблема Мы предоставили вам класс TreeNode. Методы объявлены в TreeNode.h, а большинство из них реализованы в TreeNode.cpp.

Ваша работа: реализовать функцию TreeNode * makeFullRight (int n), которая создает полное дерево с n узлами. То, как вы построите дерево, заключается в том, что левый потомок каждого узла с двумя дочерними элементами будет листом. Узлы должны быть пронумерованы (путем заполнения его поля data_) от 1 до n, согласно следующему правилу: если бы у узла был номер i, то у любого левого потомка был бы номер i + 1, а у любого правого потомка был бы номер i + 2.

Поместите ваш код в TreeNode.cpp.

Например, makeFullRight (7) создаст дерево

    1
   / \
  2   3
     / \
    4   5
       / \
      6   7

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

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

Sample Run Ваш main.cpp будет упражнять вашкод.

Я устал делать это с помощью рекурсии, но я не смог получить ответ, и теперь я заблудился о том, как использовать функцию makeFullRight

TreeNode.cpp- File

#include "TreeNode.h"

// Your function here

TreeNode *makeFullRight(int n)
{

}

// Methods and functions we provide following.
// You should not need to edit this code.

TreeNode::TreeNode(int data, TreeNode *left, TreeNode *right) :
    data_(data), left_(left), right_(right) {}

TreeNode::~TreeNode() {
    if (left_ != NULL)
        delete left_;
    if (right_ != NULL)
        delete right_;
}

bool equal(TreeNode *n1, TreeNode *n2) {
    if (n1 == NULL)
        return n2 == NULL;

    if (n2==NULL)
        return false;

    return (n1->getData() == n2->getData() &&
            equal(n1->getLeft(),n2->getLeft()) &&
            equal(n1->getRight(),n2->getRight()));
}

int TreeNode::getData() const {
    return data_;
}

TreeNode *TreeNode::getLeft() const {
    return left_;
}

TreeNode *TreeNode::getRight() const {
    return right_;
}

TreeNode.h --- Новый файл

#ifndef _TREENODE_H
#define _TREENODE_H

#include <cstddef>

class TreeNode {

    public:
        int data_;
        TreeNode *left_;
        TreeNode *right_;

        TreeNode(int data=0, TreeNode *left=NULL, TreeNode *right=NULL);
        ~TreeNode();
        int findMax() const;

        int getData() const;
        TreeNode *getLeft() const;
        TreeNode *getRight() const;

};

// Here is the signature of the code you will write

TreeNode *makeFullRight(int n);

bool equal(TreeNode *n1, TreeNode *n2);

#endif

main.cpp --- Новый файл

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

using namespace std;

const string RED_TEXT = "\033[1;31m";
const string GREEN_TEXT = "\033[1;32m";
const string RESET_TEXT = "\033[0m";

void print_pass(string message) {
  cout<<GREEN_TEXT<<"TEST PASSED"<<RESET_TEXT<<": "<<message<<endl;
}

void print_fail(string message) {
  cout<<RED_TEXT<<"TEST FAILED"<<RESET_TEXT<<": "<<message<<endl;
  exit(1);
}

int main() {

    TreeNode *example =
        new TreeNode(1,
                new TreeNode(2),
                new TreeNode(3,
                    new TreeNode(4),
                    new TreeNode(5,
                        new TreeNode(6),
                        new TreeNode(7))));


    // Try complete

    TreeNode *x = makeFullRight(7);

    cout << "Result of makeFullRight: " << endl;

    if (equal(x,example))
        print_pass("");
    else
        print_fail("");

    // Clean up

    delete x;
    delete example;
}

Makefile --- Новый файл

    EXENAME = main
    OBJS = main.o TreeNode.o

    CXX = clang++
    CXXFLAGS = -std=c++0x -c -g -O0 -Wall -Wextra
    LD = clang++
    LDFLAGS = -std=c++0x

    all: $(EXENAME)

    $(EXENAME): $(OBJS)
        $(LD) $^ $(LDFLAGS) -o $@

    main.o: main.cpp
        $(CXX) $< $(CXXFLAGS)

    TreeNode.o: TreeNode.cpp TreeNode.h
        $(CXX) $< $(CXXFLAGS)

    clean:
        -rm -f *.o $(EXENAME)

Answer 1

Если вы изучите дерево, вы увидите, что у каждого поддерева есть k в корне, лист с k+1 в левом узле и полное дерево справа с k+2 в корне справаузел.

Предположим, что у вас есть предложенная вспомогательная функция - давайте назовем ее «fullHelper», которая отслеживает «текущее значение» и создает дерево с корнем в нем:

// Produce a right-full tree with 'current' at the root, up until 'n'.
TreeNode* fullHelper(int n, int current);

Затем вы можете написать

TreeNode* makeFullRight(int n)
{
    return fullHelper(n, 1);
}

Теперь «все», что вам нужно, это написать вспомогательную функцию.
Вам нужен базовый случай и рекурсивный случай:

• Еслиn == current, создайте один узел с n,
• В противном случае создайте дерево с current в корне, current+1 в левом листе и полное дерево справа с корнем в current+2 как правое поддерево.

Переведено на C ++:

TreeNode* fullHelper(int n, int current)
{
    return n == current
         ? new TreeNode(current)
         : new TreeNode(current, 
                        new TreeNode(current+1), 
                        fullHelper(n, current+2));
}