[Tutor] tree or link-list questions.

[mhysnm1964 at gmail.com]

All,

 

Windows 10, python 3.6.

 

I am trying to create a data structure. I might be using the wrong term here, but I am calling it a hierarchical tree. The properties of the tree I am trying to create is:

*	A single root node
*	A node can only have a single parent.
*	A parent can have multiple children.
*	Each node is unique.

This is also my first attempt in doing Object coding ever. Thus the terminology I am not going to use correct. 😊

 

Data structure:

records = [‘the brown fox',

    ‘the brown cow’,

    ‘the brown car’,

    ‘the yellow car’,

    ‘the green house’,

    ‘yellow flowers’,

    ‘the quick brown fox’]

    

What I am trying to do:

I want to create a tree structure that stores the first word under the root, the 2nd word under the first word as a child, ETC. the word ‘the’ for example can only occur once as a node. Below is an example of the tree structure I am trying to achieve:

 

Root

Root / the

Root / the / brown

Root / the / brown / fox

Root / the / brown / cow

Root / the / brown / car 

Root / the / yellow

Root / the / yellow / car

Root / the / green 

Root / the / green / house

Root / the / quick 

Root / the / quick / brown 

Root / the / quick / brown / fox

Root / yellow

Root / yellow / flowers

 

The code I have used to break up the words and build a dictionary to identify the unique words plus the hit count:

 

nar_dict = {}

for text  in records:

    words = text.split()

    l = len(words)

    for i in range(1, l+1):

        # only method I have found to correctly join the words.

        tmp_list = words[:i]

        key = ' '.join(tmp_list)

        nar_dict[key] = 0

 

# perform the searches using dictionary key and count the number of hits.

for key, item  in nar_dict.items():

    print (key, item)

    for line  in records:

        if  line.startswith(key):

            nar_dict[key] += 1

 

The result  is (note, the output below is using a different data set):

 

{'the': 5, 'the brown': 3, 'the brown cow': 2, 'the brown car': 1, 'the yellow': 1, 'the yellow car': 1, 'yellow': 2, 'yellow house': 1, 'the quick': 1, 'the quick fox': 1, 'yellow flowers': 1}

 

The code below works fine if I want to have a single parent and a single child. The init definition I have used an empty array to store the children. I am not sure how I can reference the new node back to the parent node. I have looked at some packages like anytree and I got completely lost with the code. I have looked for examples on the net and did not find anything I could understand. Here is my code thus far with the children as a list.

# Value = hit counter 

# Name = node name 

 

class Node:

    def __init__(self, name, value):

        self.parent = None

        self.child = []

        self.name = name

        self.value = value

    def add_child(self, name, value):

        # Compare the new value with the parent node

        if self.name:

            if name != self.name:

                if  self.child is None:

                    self.parent = self.child

                    self.child = Node(name, value)

                else:

                    self.child.add_child(name, value)

        else:

            self.name  = name

            self.value = value

    # Print the tree

    def PrintTree(self):

        if self.child:

            self.child.PrintTree()

        print( self.name, self.value),

I want to be able to do the following syntax:

 

Node.children[-1]value

Child = Node.children[0].children[0]

Parent = child.parent.name 

 

 

I know I will have to write a search and walk functionality. 

 

Any comments and tips on how to fix the parent issue. I would be grateful. Hopefully this is not to open ended. Done my best to be very specific. 😊

 

Sean – Open ended question master 😊