Вставить узлы двоичного дерева в связанный список (C ++)

Question

У меня есть пять файлов: source.cpp, ordersLinkedList.h, который наследуется от connectedList.h, и binarySearchTree.h, который наследуется от binaryTree.h. Я пытаюсь вставить узел из бинарного дерева в связанный список, используя функцию с именем createList, которая принимает в качестве аргумента объект orderLinkedList и является членом bSearchTreeType.

//These two functions are in binarySearchTree.h
template <class elemType>
void bSearchTreeType<elemType>::createList(orderedLinkedList<elemType> list)
{
    inorderInsert(root, list);
}

template <class elemType>
void bSearchTreeType<elemType>::inorderInsert
(bNodeType<elemType> *p, orderedLinkedList<elemType> list)
{
    if (p != nullptr)
    {
        inorderInsert(p->lLink, list);
        list.insertLast(p->info);
        inorderInsert(p->rLink, list);
    }
}
________________________________________________________
//Insert functions from orderedLinkedList.h
template <class Type>
void orderedLinkedList<Type>::insert(const Type& newItem)
{

    nodeType<Type> *current; //pointer to traverse the list
    nodeType<Type> *trailCurrent = NULL; //pointer just before current
    nodeType<Type> *newNode; //pointer to create a node
    bool found;
    newNode = new nodeType<Type>; //create the node
    newNode->info = newItem; //store newItem in the node
    newNode->link = nullptr; //set the link field of the node
    //to nullptr
    if (first == nullptr) //Case 1
    {
        first = newNode;
        last = newNode;
        count++;
    }
    else
    {
        current = first;
        found = false;
        while (current != nullptr && !found) //search the list
            if (current->info >= newItem)
                found = true;
            else
            {
                trailCurrent = current;
                current = current->link;
            }
        if (current == first) //Case 2
        {
            newNode->link = first;
            first = newNode;
            count++;
        }
        else //Case 3
        {
            trailCurrent->link = newNode;
            newNode->link = current;
            if (current == nullptr)
                last = newNode;
            count++;
        }
    }//end else
}//end insert
template <class Type>
void orderedLinkedList<Type>::insertLast(const Type& newItem)
{
    insert(newItem);
}//end insertLast

Проблема в том, что, когда я вызываю insertLast, который является функцией-член orderLinkedList, кажется, что ничего не происходит. Мой код компилируется, а все остальное работает как задумано. Это проблема наследования? Как сделать так, чтобы insertLast работал при использовании в файле binarySearchTree?

Answer 1

Как уже указывалось, ваши методы createList и inorderInsert принимают список по значению, поэтому они копируют его, изменяют копию и ничего не делают с копией. Так что он разрушается и вся работа теряется. Ваше замечание о том, что оно также не работает в createList напрямую, является спорным, поскольку createList также принимает список по значению, поэтому он будет вставлен в локальный список (и вы можете проверить это с некоторыми выходными данными непосредственно в этом методе)но это не повлияет на список, с которым вы вызываете этот метод.

Вы должны либо передать список по ссылке, как показано здесь:

template <class elemType>
void bSearchTreeType<elemType>::createList(orderedLinkedList<elemType> &list)
{
    inorderInsert(root, list);
}

template <class elemType>
void bSearchTreeType<elemType>::inorderInsert
(bNodeType<elemType> *p, orderedLinkedList<elemType> &list)
{
   //...
}

(обратите внимание на &), либо создать список в методе и вернуть его, как показано здесь:

template <class elemType>
orderedLinkedList<elemType> bSearchTreeType<elemType>::createList()
{
    return inorderInsert(root);
}

template <class elemType>
orderedLinkedList<elemType> bSearchTreeType<elemType>::inorderInsert
(bNodeType<elemType> *p, orderedLinkedList<elemType> list, orderedLinkedList<elemType> list = {}) // Default parameter, so we don't have to do it in createList
{
    orderedLinkedList<elemType> list
    if (p != nullptr)
    {
        list = inorderInsert(p->lLink, list);
        list.insertLast(p->info);
        list = inorderInsert(p->rLink, list);
    }
    return list;
}

Лично я бы предпочел гибридное решение, где createList генерирует его и возвращает, а inorderInsert берет его по ссылке и модифицирует.