CODEWITHSUNDEEP
pythonlistdata-structurestree
overexchange
overexchange

Reputation: 1

Tree representation using list in python

For this tree,

enter image description here

As a beginner, Below is my list representation,

tree = [
          [
              [
                 [
                   [], 3, []
                 ], 
                 10,
                 [
                   [], 17, []
                 ]
              ],
              25,
              [
                 [
                   [], 30, []
                 ],
                 32,
                 [
                   [], 38, []
                 ]
              ]
          ],
          40,
          [
             [
               [], 50, []
             ], 
             78,
             [
               [], 93, []
             ]
          ]
       ]

Is this representation correct using python list?

Can I avoid empty list [] in this representation?

Upvotes: 2

Views: 9147

Answers (3)

ZSOR
ZSOR

Reputation: 55

It depends on what you mean by 'represent'. You can represent trees by just having the elements in a list e.g. list = [40,25,78,10,32,50,93,3,17,30,38] Then to iterate through it if you want to recreate the tree you can iterate through the list since you know that the life child of list[(i+1)*2-1] and the right child is list[(i+1)*2].

Note: you have to do i+1 since the first element has index 0, And I is the index of the parent node, e.g. the index+1 of the of 25 is 2 therefore the index+1 of 25's left child is 4.

Upvotes: 5

Timothy Murphy
Timothy Murphy

Reputation: 1362

There are many ways to represent a tree using lists.

You can use a single dimensional list. This works well for full trees with a set number of children. Or for missing children pad the array with None where the child of a leaf node should be. if the current node is at index i, its children will be at index i*2 + 1 and (i+1)*2. your parent will be (i-1)/2.

You could also use the a lisp-like tree representation.

[Root, LEFT_SUB_TREE, RIGHT_SUB_TREE]

you example tree would look like:

[40, [25, [10, 3, 17], [32, 30, 38]], [78, 50, 93]]

leaf nodes don't need to be a list they can just be their value.

This method uses less memory for spare trees than the single dimensional list representation.

It is also easy to make this work for any nary tree as well, with varying number of children per node.

[Root, SUB_TREE_1, SUB_TREE_2, ..., SUB_TREE_n]

Upvotes: 0

A.P.
A.P.

Reputation: 1159

You representation makes a lot of sense since it uses just 2 simple rules. A tree is a list that can be:

[]                          #empty tree
[list, number, list]        #non-empty tree

This simplicity makes it easy to write code for and treat things in an uniform way (and without a lot of if statements).

Another equally simple representation is to use tuples instead of lists and/or use None for empty tree.

Another representation would be to put the numbers in leaf nodes directly in the parent node (e.g. to code the subtree under 10 as [3, 10, 17]). This is more compact and gets rid of empty lists but now the logic is more complex, and a tree could be represented 5 different ways:

[]
[list, number, list]
[list, number, number]
[number, number, list]
[number, number, number]

The representation being more complex means you probably need to write more code.

Upvotes: 2

Related Questions