Traversing 2-3-4 Tree

Question

В последнее время я думал и предложил два варианта поиска обхода порядка 2-3-4. Один из них - это рекурсивный подход с ключом переключения на тип узла, а другой - итеративный подход. Для фона цель этого обхода состоит в том, чтобы создать следующий набор элементов из дерева выше этого.

         [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; 

Или итеративно идти в крайнее левое положение узел, «получить» каждый элемент из этого узла, вернуться к родительскому, перейти к следующему ребенку, повторить процесс. После того, как все дети будут замечены, перейдите к parent/root и повторите процесс, начиная с преемника корневого каталога root (извините не псевдокод).

Какой из этих методов был бы лучше для получения желаемого набора элементов внутри дерева?

Answer 1

Я бы предложил решение recursive, потому что его намного проще реализовать и прочитать. Также вы можете использовать петлю , чтобы избавиться от 3-х корпусов.

Предположим, что ваш узел структура данных что-то вроде этого:

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

, что будет (в питоновских обозначениях):

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)