0

我正在尝试实现一棵二叉树（如果它是通用二叉树或二叉搜索树，则并不重要），并且在创建节点并将其链接到树中的函数上遇到了一些问题。
这是我到目前为止写的代码：

class BinaryTree {
    class Node {
        char data;

        Node* leftChild;
        Node* rightChild;

        Node(char d, Node* lc, Node* rc):
            data(d), leftChild(lc), rightChild(rc) {}
    } *head;
    int treeSize;
public:
    BinaryTree(): head(0), treeSize(0) {}

    // totally wrong code
    void createNode(char dat) {
        if (head->data < dat)
            head->leftChild = new Node(dat, 0, 0);
        if (head->rightChild == 0)
            head->rightChild = new Node(dat, 0, 0);
        if (head == 0) {
            head = new Node(dat, head, head);
        }
    }
};

好吧，我想用链表来实现二叉树，但在这种情况下，问题在于head指针将指向最后添加的节点之一，而不是根。以这种方式使用链表的另一个问题可能是找到要添加新节点的节点的空子节点。
有人可以帮助我，也许可以建议一种更好的方法来实现二叉树？

注意：我计划将这个类设为 a template， char 只是为了即时试用。

4

3 回答 3

3

我认为你移动的方式是正确的，但没有完成它。您的方法可能如下所示：

void addNode( char data ) {
    // when root is uninitialized
    if ( NULL == head ) {
        head = new Node( data, NULL, NULL );
    } else {
        Node *currentNode = head;
        // search for the place to insert the new value
        while ( true ) {
            if ( currentNode->data < data ) {
                // if the current node already has left child
                // so we concern it further
                if ( NULL != currentNode->leftChild ) {
                    currentNode = currentNode->leftChild;
                    continue;
                // if the current node has no left child
                // so we create it with the new value
                } else {
                    currentNode->leftChild = new Node( data, NULL, NULL );
                    return;
                }
            } else {
                // similarly for the value that should be inserted into
                // right subtree
                if ( NULL != currentNode->rightChild ) {
                    currentNode = currentNode->rightChild;
                    continue;
                } else {
                    currentNode->rightChild = new Node( data, NULL, NULL );
                    return;
                }
            }
        }
    }
}
于 2013-05-31T17:46:14.637 回答
1

以下是我注意到的几件事：

  1. 你的 head!=null 应该首先检查，否则你的第一个 createNode() 会崩溃。所有其他分支都应该在“else”中。

  2. 为了代码清晰和/或作为国际维护程序员感谢活动的一部分，您的最后一个（或者我应该首先说）新节点（dat，head，head）应该是新节点（dat，0,0）。

  3. 您可能想要增加 treeSize。

否则，你就在正确的轨道上。继续。

于 2013-05-31T17:31:04.590 回答
1

我假设这是某种家庭作业，所以我认为强调基础知识并让您弄清楚其余部分很重要。由于它是任何遍历树的起点，除非您删除根节点，否则 Head 永远不应更改。任何遍历都应该由另一个 Node 对象完成，该对象可以（并且可能经常会）在每个函数调用结束时超出范围，而不会对程序产生任何副作用。

正如已经指出的，您需要考虑 head = NULL 作为第一个条件的情况，然后处理 head != NULL 的后续遍历。对于插入，您必须考虑如何进行插入，并正确链接到树的其他元素。记住叶子是左右数据成员为 NULL 的任何 Node 对象可能会有所帮助。

祝你的程序好运。

于 2013-06-01T03:23:50.907 回答