递归地将元素插入二叉树

Question

所以我完成了List练习并继续使用Binary Trees.我的代码到目前为止:

tree.h中

#include "Node.h"

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

public:
    Tree();
    ~Tree();

    void insert(int, Node *);
};

Tree.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() );
    }
}

main.cpp中

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

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

我希望这是足够的代码.Node并且Tree是两个单独的类.我在绕递归时遇到困难.

我Node *root在Tree类中定义了在树顶部有一个根节点.但是,我看到它的方式,当我tree->insert在main中调用insert时,我不必指定任何节点.Tree类的根将完成所有工作.但是,当我在代码中并且需要重复时,我突然变成一个参数,如上所示.

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

这看起来很骇人听闻.我错过了一些明显的东西吗

Answer 1

几点:

首先,不要使用Node**.那错误"丑化"了你的代码.如果你真的需要,请Node*&改用(见这里的答案).

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

非递归插入方法:

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
}

编辑:

我在绕递归时遇到困难.

看看它是这样的:要找到插入点,您知道需要插入左侧或右侧子节点的子节点.要插入左侧,您需要插入当前节点的左子节点的左子节点或子子节点的子节点.也就是说,如果你向左边插入,则调用找到左边孩子的插入点部分; 否则,调用查找右子节点的插入点.

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

• 识别适用于部分数据的算法(在这种情况下,您需要插入左侧或右侧子节点的子节点).

• 识别停止条件(算法何时停止？).如果你不这样做,你会得到无限递归和stackoverflow错误:).

• 识别算法的可变部分(这应该告诉你递归函数将具有哪些参数).