pythonooprecursiontreenon-recursive

convert object structure of n child tree to nested list in python


I made two classes as follow:

  1. Node class
class Node:
    def __init__(self,title):
        self.title = time
        self.child = []

And implement methods like getTitle, getChild, addChild, isEmpty: if child = [] and more

  1. Tree class
class Tree:
    def __init__(self, title):
        self.root = Node('*')
        self.wordset = set()

I want to implement one method in Tree class , so I can make equivalent list structure of Tree object (as below)

suppose i have tree structure like this

      a - p
     / 
* - t - o - y
         \ 
          p

obj formate: obj(title, [child])

suppose i have obj structure as below...

obj(*, [
        obj(t, [
                obj(o, [
                        obj(p, []),
                        obj(y, [])
                       ]),

                obj(a,[
                       obj(p, [])
                       ])
               ])
       ])

i want this kind of resultant obj structure in list

[t, [
       [o, [
             [p, []],
             [y, []]
           ]
       ],
       [a, [
             [p, []]
           ]
       ]
   ]
]

details...

i took reference from this question and modify the code but output is not as i write above

import Tree as tr

def getTree(obj):
    inputList = obj.getChild()[:]
    curResultList = []
    stack = []
    preResultList = []

    while inputList or stack:
        if inputList:
            poppedObj = inputList.pop(0)
            
            if poppedObj.isEmpty():
                curResultList.append(poppedObj.getTitle())
            else:
                    curResultList.append(poppedObj.getTitle())
                    stack.append((inputList, curResultList))
                    inputList = poppedObj.getChild()
                    curResultList = []

        else:
            inputList, preResultList = stack.pop()
            preResultList.append(curResultList)
            curResultList = preResultList
            
    
    return curResultList


t = tr.Tree()
t.addWord('top')
t.addWord('toy')
t.addWord('tap')
print(t.getWordset())
print(getTree(t.root))

my output is : ['t', ['o', ['p', 'y'], 'a', ['p']]]

is their any change suggested in above function or any other solution (recursive or non recursive) for me?


Solution

  • I think you can simplify this a lot using recursion:

    def getTree(obj):
        return [
            obj.getTitle(),
            list(map(getTree, obj.getChild()))
        ]