C++ 二叉树插入/高度

Question

我似乎无法弄清楚这段代码哪里出错了。这是为了类作业，我必须在高度最低的地方插入二叉树。

我在高度函数中遇到明显的段错误。

class Node {
    public:
        Node();
        Node( int );

    private:
        friend class bT;
        int data;
        Node* left;
        Node* right;
};

class bT {
    public:
        bT();
        virtual void insert( int );
        int height() const;
        unsigned size() const;

    protected:
        Node* root;

    private:
        void insert( Node*&, int );
        int height( Node* ) const;
};

还有我的主文件:

int bT::height() const {
    //Returns -1 when root does not exist
    if ( root == NULL )
        return -1;

    //Calls private recursive method. Uses taller height
    int lheight = height( root->left );
    int rheight = height( root->right );

    if ( lheight > rheight )
        return lheight;
    else
        return rheight;
}


void bT::insert( int x ) {
    //Inserts new node at root if root does not exist
    if ( root == NULL ){
        Node node( x );
        root = &node;
    }

    //Calls private recursive method to insert.
    else {
        int lheight = height( root->left );
        int rheight = height( root->right );

        if ( lheight <= rheight )
            insert( root->left, x );
        else
            insert( root->right, x );
    }
}

int bT::height( Node* r ) const {
    //Base Case: Returns 0 when node does not exist
    if ( r == NULL )
        return 0;

    //Calls private recursive method. Uses taller height
    int lheight = height( r->left );
    int rheight = height( r->right );

    if ( lheight > rheight )
        return 1 + lheight;
    else
        return 1 + rheight;
}

void bT::insert(Node*& r, int x){
    //Base Case: Sets r = new node when node does not exist
    if ( r == NULL ) {
        Node node( x );
        r = &node;
    }

    //Recursive Call: Calls insert function for node with lower height
    else {
        int lheight = height( r->left );
        int rheight = height( r->right );

        if ( lheight <= rheight )
            insert( r->left, x );
        else
            insert( r->right, x );
    }
}

Answer 1

insert 方法中的这段代码会导致悬空指针

---

if ( root == NULL ){
   Node node( x );
   root = &node;
}
//root point to invalid address now

---

一个简单的解决方法是更改​​为动态分配。

---

if ( root == NULL ){
   Node* node = new Node( x );
   root = node;
}

---

因为你不能改变类的声明(而且里面没有析构函数)，我想你还没有学过这个，但是你需要小心内存泄漏。