1

我是一个爱好者，对 c++ 很陌生，我正在努力通过最好的方式来实现这棵树。

我有很多问题，但主要是我试图找出在构建树期间存储指向父节点的指针的最佳方法；但是当我尝试在成员函数中访问该值时出现总线错误。我可以愉快地访问地址，这个输出没有错误。root->parent->datapreOrderroot->parent

任何人都可以建议我在这里做的根本错误吗？我认为这可能是一个范围问题，但可能有更好的方法来构建树？

class FibTree {

    class Node {
    public:
        int data;
        Node const* left;
        Node const* right;
        Node const* parent;
        Node (void);
    };
    Node const* root; // 'root' pointer to constant Node

public:
    FibTree (int);
    Node const* getRoot(void);
    void preOrder(Node const* root);

};

// Tree constructor
FibTree::FibTree(int n) {
    this->root = buildTree( n );
};

FibTree::Node const* FibTree::getRoot(void) {
    return this->root;
}

private:
    static Node* buildTree( int n, Node* parent = NULL );
};

void FibTree::preOrder(Node const* root) {
    if (root == NULL)
        return;
    // *** This prints the address of the parent node correctly
    cout << root->data << "[" << root->parent << "]" << ",";
    // *** This produces a 'Bus Error'
    cout << root->data << "[" << root->parent->data << "]" << ",";
    preOrder(root->left);
    preOrder(root->right);
}

FibTree::Node* FibTree::buildTree( int n, Node* parent ) {
    // *** Is there a scope issue with 'thisNode' here?
    Node* thisNode = new Node();
    thisNode->parent = parent;
    if (n < 2) {
        thisNode->left = NULL;
        thisNode->right = NULL;
        thisNode->data = n;
        return thisNode;
    } else {
        thisNode->left = buildTree( n - 1 , thisNode );
        thisNode->right = buildTree( n - 2, thisNode );
        thisNode->data = thisNode->left->data + thisNode->right->data;
        return thisNode;
    }
}

// Node constructor
FibTree::Node::Node(void) {
    this->data;
    this->left;
    this->right;
    this->parent;
};

int main () {
    FibTree f(n);
    f.preOrder(f.getRoot());
    return 0;
}

此外，是否有一种标准方法可以避免将root节点传递给遍历函数，并让成员函数遍历创建的root节点。因为我不觉f.preOrder(f.getRoot())得很优雅。

非常感谢，亚历克斯

4

2 回答 2

2

据我所知，问题是以下组合：

buildTree您的函数中的这一行，

thisNode->parent = parent;

这个功能，

// Tree constructor
FibTree::FibTree(int n) {
    this->root = buildTree( n );
};

和你的preOrder功能。

父指针没有被传入树构造函数中的 buildTree，因此默认为 NULL 指针。所以 root->parent 将是 NULL （有道理，因为它是根）。

然后调用preOrder从根开始的函数。Root 有一个parentNULL，但你从不检查这个（你确实检查了 root 本身是否为 NULL）。

您应该改为执行以下操作：

void FibTree::preOrder(Node const* root) {
    if (root == NULL)
        return;

    if(root->parent == NULL) {
      cout << root->data << " [I am the root] " << endl;
    }
    else {
      cout << root->data << "[" << root->parent->data << "]" << ",";
    }
    preOrder(root->left);
    preOrder(root->right);
}
于 2013-03-31T08:23:23.393 回答
1

我无法重现该问题，但看起来最可疑的部分是：

// Node constructor
FibTree::Node::Node(void) {
    this->data;
    this->left;
    this->right;
    this->parent;
};

语句 ( this->data) 完全没有任何作用。也许您想要（并且应该尝试）：

FibTree::Node::Node()
  : data( 0 ),
    left( NULL ),
    right( NULL ),
    parent( NULL )
{
}

解释一下：您的代码没有初始化数据和指针，因此它们未初始化。如果您打印指针，这通常可以工作，但取消引用它可能会导致您看到的错误。

当你这样做时，你可能会看到它parent变成NULL了并且你需要检查它：

if( root->parent != NULL ) {
    cout << root->data << "[" << root->parent->data << "]" << ",";
}
于 2013-03-31T08:16:49.647 回答