My best advice would be that there is no standard tree data structure because there are so many ways you could implement it that it would be impossible to cover all bases with one solution. The more specific a solution, the less likely it is applicable to any given problem. I even get annoyed with LinkedList - what if I want a circular linked list?
The basic structure you'll need to implement will be a collection of nodes, and here are some options to get you started. Let's assume that the class Node is the base class of the entire solution.
If you need to only navigate down the tree, then a Node class needs a List of children.
If you need to navigate up the tree, then the Node class needs a link to its parent node.
Build an AddChild method that takes care of all the minutia of these two points and any other business logic that must be implemented (child limits, sorting the children, etc.)
re.match
is anchored at the beginning of the string. That has nothing to do with newlines, so it is not the same as using ^
in the pattern.
As the re.match documentation says:
If zero or more characters at the
beginning of string match the regular expression pattern, return a
corresponding MatchObject
instance.
Return None
if the string does not
match the pattern; note that this is
different from a zero-length match.
Note: If you want to locate a match
anywhere in string, use search()
instead.
re.search
searches the entire string, as the documentation says:
Scan through string looking for a
location where the regular expression
pattern produces a match, and return a
corresponding MatchObject
instance.
Return None
if no position in the
string matches the pattern; note that
this is different from finding a
zero-length match at some point in the
string.
So if you need to match at the beginning of the string, or to match the entire string use match
. It is faster. Otherwise use search
.
The documentation has a specific section for match
vs. search
that also covers multiline strings:
Python offers two different primitive
operations based on regular
expressions: match
checks for a match
only at the beginning of the string,
while search
checks for a match
anywhere in the string (this is what
Perl does by default).
Note that match
may differ from search
even when using a regular expression
beginning with '^'
: '^'
matches only
at the start of the string, or in
MULTILINE
mode also immediately
following a newline. The “match
”
operation succeeds only if the pattern
matches at the start of the string
regardless of mode, or at the starting
position given by the optional pos
argument regardless of whether a
newline precedes it.
Now, enough talk. Time to see some example code:
# example code:
string_with_newlines = """something
someotherthing"""
import re
print re.match('some', string_with_newlines) # matches
print re.match('someother',
string_with_newlines) # won't match
print re.match('^someother', string_with_newlines,
re.MULTILINE) # also won't match
print re.search('someother',
string_with_newlines) # finds something
print re.search('^someother', string_with_newlines,
re.MULTILINE) # also finds something
m = re.compile('thing$', re.MULTILINE)
print m.match(string_with_newlines) # no match
print m.match(string_with_newlines, pos=4) # matches
print m.search(string_with_newlines,
re.MULTILINE) # also matches
Best Answer
A Tree is just a restricted form of a Graph.
Trees have direction (parent / child relationships) and don't contain cycles. They fit with in the category of Directed Acyclic Graphs (or a DAG). So Trees are DAGs with the restriction that a child can only have one parent.
One thing that is important to point out, Trees aren't a recursive data structure. They can not be implemented as a recursive data structure because of the above restrictions. But any DAG implementation, which are generally not recursive, can also be used. My preferred Tree implementation is a centralized map representation and is non recursive.
Graphs are generally searched breadth first or depth first. The same applies to Tree.