c++ - 递归地将元素插入二叉树

Question

所以我完成了列表练习并继续学习二叉树。到目前为止我的代码:

树.h

#include "Node.h"

class Tree
{
private:
    int mCount;
    Node *root;

public:
    Tree();
    ~Tree();

    void insert(int, Node *);
};

树.cpp

void Tree::insert(int data, Node *node)
{
    if( root == 0 )
    {
        Node *temp = new Node;
        temp->setData(100);
        temp->setRight(0);
        temp->setLeft(0);
        root = temp;
    }
    else
    {
        if( data > root->getData() )
            return insert( data, root->getRight() );
        else
            return insert( data, root->getLeft() );
    }
}

主要.cpp

int main(int argc, char** argv)
{
    Tree *tree = new Tree;
    tree->insert( 100, 0 );

    std::cin.get();
    return 0;
}

我希望这是足够的代码。 Node 和 Tree 是两个独立的类。我很难理解递归。

我在我的 Tree 类中定义了 Node *root，以便在树的顶部有一个根节点。然而，在我看来，当我在 main 中调用 tree->insert insert 时，我不必指定任何节点。 Tree 类的根将完成所有查找工作。但是，当我在代码中需要recur的时候，这时我突然一个参数short了，如上图。

我的解决方案是将参数 Node *node 放在 insert() 的参数列表中，然后用 0 调用它从主要。我还需要调用 tree->display(0); 作为 Node *node 的参数。

这看起来很老套。我错过了一些明显的东西吗？

Answer 1

几点:

首先，不要使用 Node**。那个错误“丑化”了你的代码。如果确实需要，请改用 Node*&(参见答案 here)。

其次，您不需要递归调用(除非您想使用一个)。

非递归插入法:

void Tree::insert(int data)
{
    if(!root)
    {
         root = new Node(data);  // Node constructor should receive
                                 // the data value and init internal value from it
                                 // it should also set left and right pointers to 0
         return;
    }

    Node* insertIterator = root;
    Node* parent = 0;

    while(insertIterator)
    {
         parent = insertIterator;
         insertIterator = data < insertIterator->getData() 
             ? insertIterator->getLeft()
             : insertIterator->getRight();
    }

    if(data < parent->getData())
         parent->setLeft( new Node(data) );
    else
         parent->setRight( new Node(data) );
}

如果您确实使用递归方法，请使用查找插入点的递归方法，而不是执行插入的递归方法。基本上，将上面代码中的 while 循环替换为单独的方法(下面代码中的 FindInsertionPoint):

Node* Tree::FindInsertionPoint(int data, Node * parent) // this should be private
{
    Node* insertPoint = data < parent.getData()
        ? parent->getLeft() 
        : parent->getRight();

    return insertPoint
        ? FindInsertionPoint(data, insertPoint)
        : parent;
}

void Tree::Insert(int data)  // this should be public
{
    if(!root)
    {
        root = new Node(data);
        return;
    }

    Node* parent = FindInsertionPoint(data, root);
    if(data < parent.getData())
        parent->setLeft(new Node(data)); // see comment on Node constructor above
    else
        parent->setRight(new Node(data)); // see comment on Node constructor above
}

编辑:

I'm having difficulties wrapping my head around the recursion.

这样看:要找到插入点，您知道您需要作为左子节点或右子节点的子节点插入。要向左插入，您需要作为当前节点的左子节点的左子节点或右子节点的子节点插入。即如果向左插入，调用左 child 的查找插入点部分；否则，为正确的子节点调用查找插入点。

定义递归算法需要做什么:

• 确定应用于部分数据的算法(在这种情况下，您需要作为左侧或右侧子节点的子节点插入)。

• 确定停止条件(算法何时停止？)。如果不这样做，您将得到无限递归和 stackoverflow 错误 :)。

• 确定算法的可变部分(这应该告诉您递归函数将具有哪些参数)。