inorder in non binary tree python-CodePudding

I want to built a function in python which get some non-binary tree and put the values in the tree on a list in-order from left to right. like for example in this tree -

                                      C1
                                  /    \
                                C2       C3
                             /   |   \
                            C4   C5   C6

I will get: [ C4 , C5 , C2 , C6 , C1, C3] I saw how this function works on binary tree and I try to write it similar :

    def iters(self, by_order):
        children = get_children(self)  # get_children is a function which give me a list with all the children of a value in the tree
        if (len(children) % 2) == 0:
            mid = int(len(children) / 2)
        else:
            mid = int(len(children) / 2)   1
        first_half = children[:mid]
        second_half = children[mid:]
        if len(first_half) != 0:
            first_half[0].iters(by_order)
        by_order.append(self)
        if len(second_half) != 0:
            second_half[0].iters(by_order)
        return by_order

But I dont get all the variables on my list any idea how to make it better ? or perhaps another way to solve it ? I found information just on binary tree on the web thanks a lot !

CodePudding user response：

Your code isn't including all the child nodes because you're specifically picking out just one node from your first_half and second_half lists to recurse on and ignoring everything else. Probably you want to loop over each of those lists instead:

    mid = int(len(children) / 2)   1
    first_half = children[:mid]
    second_half = children[mid:]
    for child in first_half:
        child.iters(by_order)
    by_order.append(self)
    for child in second_half
        child.iters(by_order)

It's worth noting that this order seems a bit awkward. You're choosing to stick the parent node in the exact middle of its children (or as close as possible, for odd-numbers of children), but that is a bit arbitrary. While the child nodes have a definitive order, there's not necessarily a clear reason to order the parent in any particular relation to them. Indeed, for some kinds of non-binary trees (like B-trees), there are multiple values stored in each node of the tree, and a proper in-order traversal would interleave them in between the child nodes' values.