0

我真的很感激 2-3-4 树的澄清......假设你有这样定义的树： 


class N234{  //node class
    public:
        int firstData, secondData, thirdData;
        N234 *firstChild,*secondChild,*thirdChild,*fourthChild,*parent;
};



class T234{  //tree with root node
    public:
        T234(){
            this->root->parent=NULL;
            this->root->firstChild=NULL;
            this->root->secondChild=NULL;
            this->root->thirdChild=NULL;
            this->root->fourthChild=NULL;
        }
    private:
        N234* root;
};
我的问题实际上是当它的变量（firstData，secondData，thirdData）已经有一些值时，我怎么知道节点是否已满（其中包含所有三个值）？

例如：
根：|4| 根的左孩子：|1,2|
根的右孩子 |7,9|

这里 root 有一个值 (4)。我的问题是我们怎么知道它实际上有一个值，因为他所有的其他变量（secondData，thirdData）都有一些价值（即使它是垃圾）..提前谢谢！

4

2 回答 2

0

如果我们只需要担心内部节点，最简单的方法是查看子指针：

如果thirdChild为 null，则该节点是 2 节点，因此它只有一个有意义的值 ( firstData)，其余 ( secondData, thirdData) 包含垃圾。

如果thirdChild不是空，而是fourthChild空，那么它是一个 3 节点；前两个数据变量包含有意义的值。

如果所有子指针都不为空，那么它是一个 4 节点。

这种方法的唯一问题是它要求一个指针为空，如果它实际上是无效的（例如thirdChild2 节点的），而不仅仅是未使用。但并非所有有效的子指针都将被使用（例如firstChild，作为叶子的 2 节点的 ）。

因此，一种解决方案是创建一个所有无效指针都指向的节点，并且不以任何其他方式使用该节点。从某种意义上说，它充当了第二个 NULL，与普通的 NULL 不同。

请注意，哪种指针（无效或有效但未使用）指向 NULL 以及哪种指针指向假节点并不重要。（另请注意，您可以为“第二个 NULL”使用任何非 NULL 值，它不必是实际节点的地址，但您必须确定它永远不会成为实际的节点，无论如何使用这种方法会让我感到紧张。）

于 2014-06-15T23:48:46.130 回答
0

您需要在节点类中添加“键总数”成员变量

class N234{  //node class
 public:

   N234(int x) : totalItems(1) { keys[0] = x; children[0] = 0; } 

   N234(int x, int y) : totalItems(2) {keys[0] = x; keys[1] = y; children[0] = 0;}

   N234(int x, int y, int z) : totalItems(3) { keys[0] = x; keys[1] = y; 
                      keys[2] = z; children[0] = 0; }

   bool isLeaf() { return child[0] == 0 ? true : false }
   bool isFourNode() { return totalItems == 4 : true : false}
  private:
   totalItems;
   int keys[3];
   N234 *children[4];
};

然后检查它是否是4节点。

于 2014-09-02T17:26:50.480 回答