c++ - 在有序树的二叉树表示中计算节点的右子节点

Question

我需要帮助解决这个问题。示例树：

                         A
                        /
                       B-C-D
                           /
                           E-F-G

我有一个表示有序树的二叉树，我必须计算每个节点的子节点数并将该数字放在相应的节点中。

A有三个孩子（B，C，D），D有三个（E，F，G）。B，C，E，F，G有零个孩子。

每个节点只能有两个物理（二进制）表示的子节点。如果一个节点有一个左孩子，那么从这个节点开始的每个右孩子也被认为是一个孩子。在我的示例中，A 左孩子是 B。B 有一个右孩子 C。C 有一个右孩子 D。所以 B、C 和 D 是此任务中 A 的孩子。

在程序结束时，节点中的数据应为 A(3),B(0),C(0),D(3),E(0),F(0),G(0)。

Answer 1

你所描述的似乎是一个以左子右兄弟模式表示的任意树。每个节点都拥有一个指向其最左侧子节点以及其右侧兄弟节点的指针。

找出给定节点有多少孩子应该不会太难。只取最左边的孩子，然后计算你可以迭代到它的右边兄弟姐妹的次数。在伪代码中，它看起来像这样：

def Node {
    Node* left_child
    Node* right_sibling
}

numChildren(Node n) {
    num = 0
    next = n.left_child
    while (next exists)
        num = num + 1
        next = next.right_sibling
    return num
}