c++ - 有 3 个孩子的树

Question

这是数据结构类型的问题，我想从用户那里获取输入的树有问题，说出它的名字。“DAN”现在我想为它制作一棵树，根节点有三个孩子。我有一棵树，有三个孩子。

我将如何用链表实现它。因为在二叉树链表中有两个孩子。

但这里我有三个。简单是我有一个根节点有三个孩子

                root
                / | \
               /  |  \
             ch1 ch2  ch3

Answer 1

很简单，您创建一个具有三个子指针的结构：

struct TreeNode
{
    int data;
    TreeNode *children[3];
};

或者，您可以将子节点转换为链表，这样任何给定节点都只有一个指向其第一个子节点及其第一个兄弟节点的直接指针：

struct TreeNode
{
    int data;
    TreeNode *firstChild;
    TreeNode *nextSibling;
};

// To iterate through the children of a node:
TreeNode *child = root->firstChild;
while (child != NULL)
{
    // Do stuff with child
    ...
    child = child->nextSibling;
}

这更容易扩展到任意数量的子节点，但在访问数据时会带来更高的性能损失。因此，如果您知道每个节点最多有 3 个子节点，那么最好使用固定的子指针数组来缩短访问时间并提高缓存局部性。