在有序樹的二叉樹表示中計算節點的正確子節點

Question

我需要此問題的幫助。 例樹：

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

我有一個表示有序樹二叉樹，我都數不過來的孩子每個節點的數量和放在相應的節點，這個數字。

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

每個節點只能以物理（二進制）表示形式擁有兩個子節點。如果一個節點有一個左邊的孩子，那麼來自這個節點的每個正確的孩子也被認爲是一個孩子。在我的例子中，一個左邊的孩子是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 
}