将二叉树的节点插入链表（C++）

Question

我有五个文件：source.cpp、继承自 linkedList.h 的 orderedLinkedList.h 和继承自 binaryTree.h 的 binarySearchTree.h。我正在尝试使用名为 createList 的函数将二叉树中的节点插入到链表中，该函数将 orderedLinkedList 对象作为参数并且是 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

问题是当我调用orderedLinkedList的成员函数insertLast时，似乎没有任何反应。我的代码编译并且其他一切都按预期工作。这是继承问题吗？如何使 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)
{
   //...
}

（注意 &），或在方法中创建列表并 return 它，如下所示：

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 生成它并 return 保存它，inorderInsert 通过引用获取它并对其进行修改。

将二叉树的节点插入链表（C++）

Insert nodes of a binary tree into a linked list (C++)

c++

binary-tree

linked-list