遍歷2-3-4樹

Question

我一直在思考，並提出了兩個選項來尋找2-3-4樹的遍歷遍歷。其中之一是遞歸方法，在節點類型上使用switch case，另一種方法更多的是迭代方法。爲了背景，這個遍歷的目標是從上面的樹中產生下面一組元素。

         [S] 
           /   \ 
          [J O]   [U] 
         / | \  /\ 
         [EH] [MN] [PQR] [T] [VWX] 

     { {E} {H} {J} {M} {N} {O} {P} {Q} {R} {S} {T} {U} {V} {W} {Z} } 

由於只能有一個節點上2米3或4的兒童我的想法，以下任一方法將工作（僞代碼）。

第一種方式是從左側的根，中左，中，右，右，這取決於節點的當前大小必要時改乘：

list = new list 
234InOrder(Node cur): 

    switch(cur.numElems) 
     case 1: // 2-node 
     234InOrder(cur.child[0]) 
     list.add(cur.child[0]) 
     234InOrder(cur.child[1]) 
     break; 
     case 2: // 3-node 
     234InOrder(cur.child[0]) 
     list.add(cur.child[0]) 
     234InOrder(cur.child[1]) 
     list.add(cur.child[1]) 
     234InOrder(cur.child[2]) 
     break; 
     case 3: // 4-node 
     234InOrder(cur.child[0]) 
     list.add(cur.child[0]) 
     234InOrder(cur.child[1]) 
     list.add(cur.child[1]) 
     234InOrder(cur.child[2]) 
     list.add(cur.child[2]) 
     234InOrder(cur.child[3]) 
     break; 

或者反覆走最左邊節點，從該節點「獲取」每個元素，返回到父節點，繼續下一個子節點，重複該過程。一旦所有的孩子都被看到了，進入父母/ root並重新開始從根的後繼者（對不起沒有僞代碼）開始。

哪種方法更適合在樹中獲取所需的元素集？

Answer 1

我會建議遞歸解決方案，因爲它更容易實現和閱讀。 也可以使用循環擺脫3種情況。

假設你的節點數據結構是這樣的：

class 234Node: 
    keys: list of KeyType 
    childs: list of Nodes 
    # with 1 <= len(items) == len(childs) - 1 <= 3 

這將是（在Python的符號）：

def inorder_traversal(node, inorder): 
    if not node: 
     return 

    inorder_traversal(node.childs[0]) 
    for i in range(len(node.keys)): 
     inorder.append(node.keys[i]) 
     inorder_traversal(node.childs[i+1]) 

# and use 
t = someTree 
inorder = [] 
inorder_traversal(t.root, inorder)