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
– Pynchia, Commented Oct 25, 2015 at 19:43
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
– Pynchia, Commented Oct 25, 2015 at 19:47
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
– Pynchia, Commented Oct 25, 2015 at 19:58
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
– Julien Palard, Commented Oct 25, 2015 at 22:08

BigFatProgrammer · Accepted Answer · 2015-10-25 22:15:21Z

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.

Collectives™ on Stack Overflow

Python Ordered List Preorder Tree Traversal

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related