Imagine a folder containing files and smaller folders. You can start at the main folder and follow the branches to reach every item. A tree captures that shape: it is a connected graph with no cycles, so following its edges cannot lead you around a loop. section 7.2 section 7.4
In a rooted tree, the relationships have simple names:
- The root is the starting node and has no parent. section 7.1
- A node can have children, but each node has at most one parent. section 7.1
- A leaf is a node with no children. section 7.1
How would you print every file name in a folder, including files in its subfolders? Breadth-first search can traverse the tree. Put the starting folder in a queue. Take a folder from the queue, print the files inside it, and add its subfolders to the queue. Continue until the queue is empty. Unlike a general graph search, this traversal needs no record of visited nodes when the structure really is a tree: there are no cycles, and each node has only one parent. section 7.2
from os import listdir
from os.path import isfile, join
from collections import deque
def printnames(start_dir):
search_queue = deque() #1
search_queue.append(start_dir)
while search_queue: #2
dir = search_queue.popleft()
for file in sorted(listdir(dir)): #3
fullpath = join(dir, file)
if isfile(fullpath):
print(file) #4
else:
search_queue.append(fullpath) #5
printnames("pics")
The Python example uses a queue of folders still to visit. It prints file names and queues subfolders for later. section 7.2
Choosing a branch
A binary search tree gives each node up to two children and puts smaller values on the left and larger values on the right. To find 7, start at 10: go left to 5, then right to 7. To look for 8, follow the same choices; if the next position is empty, 8 is not in the tree. Each comparison lets you skip a whole branch. section 8.2
Trees also support jobs beyond finding files or numbers. Huffman coding uses binary trees for text compression, while balanced trees such as B-trees are used for database storage. These are specialized trees built on the same node-and-edge idea. section 7.0 section 7.1
