The aim of this code, written in Python3.6, was to write a function that will non-recursively walk over a N-branching tree structure.
It works by using a list of indices that keep track of visited nodes and by retracing prior steps when a tree branch ends. The function
non_recurs visits nodes top down left to right (as far as I can tell).
non-recurs allows the caller to provide a function to the
func argument which will be applied to to each node. The
end_only argument will determine if the supplied function will be applied to all nodes (
end_only=False) or only nodes at the end of branches (
1st I would like to know if this attempt is actually capable of walking over N-branching trees and 2nd I would like to know what you think about my implementation.
NOTE: There are two sections to my code below. The first is to generate N-branching trees and is not the focus of this code review. But is required to generate my demonstrated output
- I added IndexError to the except of the try block
tree generation code
from itertools import product # CODE to create test tree's for walking def assign(tree, idx, value): new_idx = idx[:] assignment_idx = new_idx.pop() ref = tree for i in new_idx: ref = ref[i] ref[assignment_idx] = value return tree def n_branch_tree(height, branches): idx = ([i] for i in range(branches)) tree = list(range(branches)) count = 0 node = 0 while count < height: for i in idx: # mutates tree assign(tree, list(i), list(range(node, node+branches))) node += branches count += 1 idx = product(range(branches), repeat=count) return tree
tree walk code
# Code to walk over tree def walk(tree, idx): """Return tree node at provided index args: tree: tree to index idx: index of desired node returns: node """ for i in idx: tree = tree[i] return tree def non_recurs(tree, func=print, branches=2, end_only=True, ): """Non-recursively walk n-branching tree args: tree: n-branching tree func: function that takes tree node as first argument branches: The number of branches each node has end_only: Default is True. When True will only apply func to end nodes. When False will apply func to all Nodes """ branches = branches - 1 # Because index's start at 0 idx =  node = None while True: # print(idx) try: node = walk(tree, idx) except (TypeError, IndexError): # Could not find node at index try: # Walk back up tree until a node has not # been fully explored while idx[-1] == branches: idx.pop() except IndexError: # Means all nodes in index have been fully explored break # Increase index if current index is under node branch limit if idx[-1] < branches: idx[-1] += 1 # Apply func to end node if end_only and node: func(node) node = None else: idx.append(0) # Apply func to all nodes if not end_only: func(node) if __name__ == '__main__': tree = n_branch_tree(height=3, branches=3) print(tree) value_store =  non_recurs(tree, func=value_store.append, branches=3, end_only=True) print(value_store)
[[[18, 19, 20], [21, 22, 23], [24, 25, 26]], [[27, 28, 29], [30, 31, 32], [33, 34, 35]], [[36, 37, 38], [39, 40, 41], [42, 43, 44]]] [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44]