This week we covered Trees in lecture; more specifically, binary trees, and honestly I was completely lost during lecture. Hopefully by reading up on Trees more as I write this slog, the class will become more clear to me.
Lets start with basic definitions. This'll be easier with a diagram, so consider the following:
The above tree is a binary tree since every node (represented by the circles) has two child nodes. The top node (here, labelled 'A'), is called the root, and the nodes that do not have any children are leaves. However, since we're in code we don't really have nodes that have nothing branching from them - Nodes can either store either values/objects or Nonetypes. If a node has two Nonetype children then it is a leaf.
Trees are recursive data structures; they're either:
- Empty (represented by None) or
- A node that contains an object and/or two other tree references
So now we have the 'graphical' representation of trees, but what do they look like in actual code? Luckily for me this was shown in-class, so consider the code taken from Monday's lecture:
As you can see from the code, Trees are a lot like the nested lists we examined in Week 4 (as well as Lab #4). Note that if there are no children, the line self.children = [] creates indexes with the Nonetype where in place of a leaf's child nodes.
No comments:
Post a Comment