solution for tree traversal with python

Question

I am handling with a new problem that relates to tree traverse methods. I have a binary tree with conditional search option. I want to parse an input of type string and traverse tree based on this parsed string. the conditions are a bit complicated so let me explain it using an example:

input :

data = [ 'dummy', ['null', 'd2', 'd1'], ['null', 'b2', 'b1'], 'dummy', ['b2', 'a2', 'a1'], ['b1', 'c1', 'c2'], 'dummy', 'dummy', 'dummy', 'dummy', ['c1', 'a1', 'a2'], ['c2', 'a2', 'a1'] ]

The output should be:

d2,b2,a2 d2,b2,a1 d1,b2,a2 d1,b2,a1 d2,b1,c1,a1 d2,b1,c1,a2 d1,b1,c1,a1 d1,b1,c1,a2 d2,b1,c2,a2 d2,b1,c2,a1 d1,b1,c2,a2 d1,b1,c2,a1

And that's the picture of the tree:

These are my codes that only display the first output line:

solution, solutions = [], [] for d in data: x = d[0] * 2 child = [] for i in data: if i[0] == x: child.append(i[0]) if i[0] == x + 1: child.append(i[0]) d.insert(1, child) root = data[1] solution.append(root[3]) i = 0 pointer = data[root[0] * 2] last = None while i <= len(data): if solution[-1:] != [last]: solution.append(pointer[3]) try: pointer = data[pointer[0] * 2] except: break if len(pointer) > 3: if pointer[2] == 'null' or pointer[2] == solution[-1:]: solution.append(pointer[3]) else: solutions.append(solution) solution = [] pointer = data[int((pointer[0] / 2) + 1)] last = pointer[3] i += 1 print(solutions)

This is the output :

[['d2', 'b2', 'a2']]

More details:

This tree is lexicographic preference tree and i implement it with array. I suppose that each node of tree may have 2 children or less and each edge may have conditional or not.

Now, i want to find the solution of tree. For finding solution, i have to trase the tree

I explain the parameter of tree and array with example:

You are not specifying the rules. The examples are not accompanied with any explanation either, and you are code is not working. Can't you just describe what is dummy, how a single input should be projected to an ouput according to tree ? — grodzi
– grodzi, Commented Jun 27, 2020 at 16:59
It is not clear how you have encoded the tree. For instance, I can't see how you have encoded that B is a child not of D as depicted in the drawing. In the data structure they look more like siblings with a common null-parent. — trincot
– trincot, Commented Jun 27, 2020 at 17:58
@grodzi Thanks for the comment, I have added more details now — Atheris
– Atheris, Commented Jun 27, 2020 at 19:38
@trincot Thanks for the comment, I have added more details now — Atheris
– Atheris, Commented Jun 27, 2020 at 19:38
Please don't put textual explanations in a picture. Put the explanatory text in your question as plain text. — trincot
– trincot, Commented Jun 27, 2020 at 19:47

trincot · Accepted Answer · 2020-06-28 07:39:48Z

I think the following implementation should do it. It produces the output for the example data you have provided. I believe there is some redundancy in that data structure, so I have added some validation in the code as well, and if it violates that validation, an error is raised.

def getpaths(data, i, tracks): paths = [] isleaf = True j = 2*i for k in range(1, 3): if j < len(data) and data[j] != 'dummy': isleaf = False if data[j][0] == 'null': yield from getpaths(data, j, [track + [data[i][m]] for track in tracks for m in range(1,3)]) break elif data[j][0] != data[i][k]: raise ValueError("inconsistent tree") else: yield from getpaths(data, j, [track + [data[i][k]] for track in tracks]) j += 1 if isleaf: for track in tracks: yield track + [data[i][1]] yield track + [data[i][2]] # Example run data = [ 'dummy', ['null', 'd2', 'd1'], ['null', 'b2', 'b1'], 'dummy', ['b2', 'a2', 'a1'], ['b1', 'c1', 'c2'], 'dummy', 'dummy', 'dummy', 'dummy', ['c1', 'a1', 'a2'], ['c2', 'a2', 'a1'] ] for path in getpaths(data, 1, [[]]): print(path)

Collectives™ on Stack Overflow

solution for tree traversal with python

input :

The output should be:

This is the output :

More details:

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

input :

The output should be:

This is the output :

More details:

1 Answer 1

Comments

Related