DFS：

list nodes_to_visit = {root};

while( nodes_to_visit isn't empty ) {

  currentnode = nodes_to_visit.take_first();

  nodes_to_visit.prepend( currentnode.children );

  //do something

}

BFS：

list nodes_to_visit = {root};

while( nodes_to_visit isn't empty ) {

  currentnode = nodes_to_visit.take_first();

  nodes_to_visit.append( currentnode.children );

  //do something

}

兩者的對(duì)稱性很酷。

更新：如前所述，take_first()刪除并返回列表中的第一個(gè)元素。

您將使用一個(gè)堆棧來保存尚未訪問的節(jié)點(diǎn)：

stack.push(root)

while !stack.isEmpty() do

    node = stack.pop()

    for each node.childNodes do

        stack.push(stack)

    endfor

    // …

endwhile

如果您有指向父節(jié)點(diǎn)的指針，則無需額外的內(nèi)存即可完成操作。

def dfs(root):

    node = root

    while True:

        visit(node)

        if node.first_child:

            node = node.first_child      # walk down

        else:

            while not node.next_sibling:

                if node is root:

                    return

                node = node.parent       # walk up ...

            node = node.next_sibling     # ... and right

請(qǐng)注意，如果子節(jié)點(diǎn)存儲(chǔ)為數(shù)組而不是通過同級(jí)指針存儲(chǔ)，則下一個(gè)同級(jí)可以找到：

def next_sibling(node):

    try:

        i =    node.parent.child_nodes.index(node)

        return node.parent.child_nodes[i+1]

    except (IndexError, AttributeError):

        return None

分享編輯

如果您有指向父節(jié)點(diǎn)的指針，則無需額外的內(nèi)存即可完成操作。

def dfs(root):

    node = root

    while True:

        visit(node)

        if node.first_child:

            node = node.first_child      # walk down

        else:

            while not node.next_sibling:

                if node is root:

                    return

                node = node.parent       # walk up ...

            node = node.next_sibling     # ... and right

請(qǐng)注意，如果子節(jié)點(diǎn)存儲(chǔ)為數(shù)組而不是通過同級(jí)指針存儲(chǔ)，則下一個(gè)同級(jí)可以找到：

def next_sibling(node):

    try:

        i =    node.parent.child_nodes.index(node)

        return node.parent.child_nodes[i+1]

    except (IndexError, AttributeError):

        return None

分享編輯