-
Notifications
You must be signed in to change notification settings - Fork 3
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Lecture "Organising information: trees", exercise 1 #32
Comments
Edit: I didn't pay attention and came up with a non-recursive solution at first, I moved that to #33 from anytree import Node
def breadth_first_visit(root_node):
visited_nodes = []
discovered_nodes = [root_node]
while discovered_nodes:
visited_nodes.append(recursive_breadth_first_visit(root_node, discovered_nodes))
return visited_nodes
def recursive_breadth_first_visit(root_node, discovered_nodes):
current_node = discovered_nodes.pop(0)
if current_node.children:
for child in current_node.children:
discovered_nodes.append(child)
return current_node
def test_breadth_first_visit(root_node, expected):
result = breadth_first_visit(root_node)
if result == expected:
return True
else:
return False
book = Node("book")
chapter_1 = Node("chapter", book)
chapter_2 = Node("chapter", book)
paragraph_1 = Node("paragraph", chapter_1)
text_1 = Node("Alice was beginning to get very tired of sitting by "
"her sister on the bank, and of having nothing to do: "
"once or twice she had peeped into the book her sister "
"was reading, but it had no pictures or conversations "
"in it, ", paragraph_1)
quotation_1 = Node("quotation", paragraph_1)
text_2 = Node("“and what is the use of a book,”", quotation_1)
text_3 = Node(" thought Alice, ", paragraph_1)
quotation_2 = Node("quotation", paragraph_1)
text_4 = Node("“without pictures or conversations?”", quotation_2)
paragraph_2 = Node("paragraph", chapter_1)
text_5 = Node("So she was considering in her own mind, (as well as "
"she could, for the hot day made her feel very sleepy "
"and stupid,) whether the pleasure of making a "
"daisy-chain would be worth the trouble of getting up "
"and picking the daisies, when suddenly a white rabbit "
"with pink eyes ran close by her.", paragraph_2)
paragraph_3 = Node("paragraph", chapter_1)
text_6 = Node("...", paragraph_3)
text_7 = Node("...", chapter_2)
text_8 = Node("...", book)
print(test_breadth_first_visit(book, [book, chapter_1, chapter_2, text_8, paragraph_1, paragraph_2, paragraph_3, text_7, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4])) # True
print(test_breadth_first_visit(chapter_2, [chapter_2, text_7])) # True
print(test_breadth_first_visit(text_1, [text_1])) # True I am not sure if there needs to be another type of test case, and whether it is necessary to split the function in two... |
from anytree import Node
from collections import deque
def test_breadth_first_visit(root_node, expected):
result = breadth_first_visit(root_node)
if result == expected:
return True
else:
return False
def breadth_first_visit(root):
queue = deque()
queue.append(root)
return recursive_breadth_first(queue, list())
def recursive_breadth_first(queue, lst):
if len(queue) == 0:
return lst
item = queue.popleft()
lst.append(item)
queue.extend(item.children)
return recursive_breadth_first(queue, lst)
book = Node("book")
chapter_1 = Node("chapter", book)
chapter_2 = Node("chapter", book)
paragraph_1 = Node("paragraph", chapter_1)
text_1 = Node("Alice was beginning to get very tired of sitting by "
"her sister on the bank, and of having nothing to do: "
"once or twice she had peeped into the book her sister "
"was reading, but it had no pictures or conversations "
"in it, ", paragraph_1)
quotation_1 = Node("quotation", paragraph_1)
text_2 = Node("“and what is the use of a book,”", quotation_1)
text_3 = Node(" thought Alice, ", paragraph_1)
quotation_2 = Node("quotation", paragraph_1)
text_4 = Node("“without pictures or conversations?”", quotation_2)
paragraph_2 = Node("paragraph", chapter_1)
text_5 = Node("So she was considering in her own mind, (as well as "
"she could, for the hot day made her feel very sleepy "
"and stupid,) whether the pleasure of making a "
"daisy-chain would be worth the trouble of getting up "
"and picking the daisies, when suddenly a white rabbit "
"with pink eyes ran close by her.", paragraph_2)
paragraph_3 = Node("paragraph", chapter_1)
text_6 = Node("...", paragraph_3)
text_7 = Node("...", chapter_2)
text_8 = Node("...", book)
print(test_breadth_first_visit(book, [book, chapter_1, chapter_2, text_8, paragraph_1, paragraph_2, paragraph_3, text_7, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4])) |
I just understood @NoonShin solution and changed the names of the variables with more semantic names. from anytree import Node
from collections import deque
def test_breadth_first_visit(root_node, expected):
result = breadth_first_visit(root_node)
if result == expected:
return True
else:
return False
def breadth_first_visit(root):
node_to_visit = deque()
node_to_visit.append(root)
return breadth_first_visit_recursive(node_to_visit, list())
def breadth_first_visit_recursive(node_to_visit, visited_nodes):
if len(node_to_visit) == 0:
return visited_nodes
item = node_to_visit.popleft()
visited_nodes.append(item)
node_to_visit.extend(item.children)
return breadth_first_visit_recursive(node_to_visit, visited_nodes)
book = Node("book")
chapter_1 = Node("chapter", book)
chapter_2 = Node("chapter", book)
paragraph_1 = Node("paragraph", chapter_1)
text_1 = Node("Alice was beginning to get very tired of sitting by "
"her sister on the bank, and of having nothing to do: "
"once or twice she had peeped into the book her sister "
"was reading, but it had no pictures or conversations "
"in it, ", paragraph_1)
quotation_1 = Node("quotation", paragraph_1)
text_2 = Node("“and what is the use of a book,”", quotation_1)
text_3 = Node(" thought Alice, ", paragraph_1)
quotation_2 = Node("quotation", paragraph_1)
text_4 = Node("“without pictures or conversations?”", quotation_2)
paragraph_2 = Node("paragraph", chapter_1)
text_5 = Node("So she was considering in her own mind, (as well as "
"she could, for the hot day made her feel very sleepy "
"and stupid,) whether the pleasure of making a "
"daisy-chain would be worth the trouble of getting up "
"and picking the daisies, when suddenly a white rabbit "
"with pink eyes ran close by her.", paragraph_2)
paragraph_3 = Node("paragraph", chapter_1)
text_6 = Node("...", paragraph_3)
text_7 = Node("...", chapter_2)
text_8 = Node("...", book)
print(test_breadth_first_visit(book, [book, chapter_1, chapter_2, text_8, paragraph_1, paragraph_2, paragraph_3, text_7, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4]))
# True |
Hi all, please find attached my personal solution – also available online. Contrarily to the approach proposed by @NoonShin et al. (great work, BTW!), my solution move the part related to the queue to a new "fake" root I add at the very beginning of the process, and that I remove at the very end.
|
Write in Python a recursive function
def breadth_first_visit(root_node)
. This function takes the root node of a tree and returns a list containing all the nodes of the tree according to a breadth-first order. The breadth-first order considers all the nodes of the first level, then those ones of the second level, and so forth. For instance, considering the nodes created in Listing 2, the function called on the node book should return the following list:[book, chapter_1, chapter_2, text_8, paragraph_1, paragraph_2, paragraph_3, text_7, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4]
. Accompany the implementation of the function with the appropriate test cases.The text was updated successfully, but these errors were encountered: