Python Ordered List Preorder Tree Traversal

Question

I'm new to python and am trying to return the preorder list of an ordered tree (NOTE: Not Binary Tree). I'm having some trouble following the recursion after it reaches a leaf of the tree. How do I get it to go back up to the previous node? Here's my code thus far:

def OrdPreOrder(T):
    if Is_OrdLeaf(T):
        return []
    else:
        for t in Subtrees(T):
            return [OrdRoot(t)] + OrdPreOrder(t)

Thanks in advance,

interesting problem, but your question lacks a fundamental element: an example input/output. Please read this and update the info provided. — Pynchia
a brief note on how do I get it to go back up to the previous node?: recursion does that for you. I assume you know how pre-order visits the tree (i.e. the current node, then the children) — Pynchia
from what I can see, your code does nothing with leaf nodes. Normally, you'd check if the tree (i.e. T) is empty (e.g. None) and return if it is. If it is not, do something with the node contents then visit the children/subtrees. — Pynchia
You should read the PEP8, and use pylint to check your code, here, typically, T should not be capitalized, and is too short (we don't how what it is, that's not telling us). Won't fix your problems though. like @Pynchia said, we'd like an exemple input and output :) — Julien Palard

BigFatProgrammer BigFatProgrammer · Accepted Answer · 2015-10-25T22:15:21

The question is not very clear to me, but hopefully this will help. You want to do a pre-order traversal of an ordered tree. Pre-Order traversal means 1. Firstly print the value stored in node 2. Then print the value stored in children (according to some principle) First off,

How do I get it to go back up to the previous node?

According to the definition of pre-order traversal i have written above, I don't see why you need to go back and revisit the parent node.

class Node:
    def __init__(self, data):
        self.__data = data
        self.__children = []

    def identifier(self):
        return self.__data

    def children(self):
        return self.__children

    def add_child(self, data):
        self.__children.append(data)

class Tree:
    def __init__(self):
        self.__nodes = {}

    def nodes(self):
        return self.__nodes

    def add_node(self, data, parent=None):
        node = Node(data)
        self[data] = node

        if parent is not None:
            self[parent].add_child(data)

        return node

    def traversal(tree):
        if tree == None:
            return
        print (tree.identifier())
        for child in tree.children():
            traversal(child)

I am also not that well versed with data structures in Python (there might be mistakes in the code). But hopefully it might point you in the right direction.

Python Ordered List Preorder Tree Traversal

1 Answers