Lecture 5/22: Trees


May 22, 2020

📂Associated files

Trees

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

A real binary tree


Slide 2

Announcements


Slide 3

Today's Topics


Slide 4

Pointer Diagram Refresh


Slide 5

Doubly-linked lists


Slide 6

Adding nodes to a doubly linked list


Slide 7

Trees


Slide 8

Trees are inherently recursive

                       (root)
              -----------A--------------
              ↙︎   ↙︎  ↙︎   ↓    ↘︎       ↘︎
             B   C   D   E     F--      G
                    ↙︎   ↙︎ ↘︎   ↙︎ ↘︎ ↘︎      ↘︎
                   H   I   J K   L M       N
                          ↙︎ ↘︎
                         O   P

Slide 9

More Tree Terminology

Most of the same tree as above, but smaller (see below)

                       (root)
                         A--------------
                         ↓    ↘︎        ↘︎
                         E     F         G
                        ↙︎ ↘︎   ↙︎ ↘︎ ↘︎       ↘︎
                       I   J K   L M       N
                          ↙︎ ↘︎
                         O   P

Slide 10

One Parent, No Cycles

An image of a real parent holding a child's hand, and an image of a bicycle with a red 'no' sign through it


Slide 11

Building trees programatically


Slide 12

Traversing a Tree


Slide 13

Pre-order traversal


Slide 14

In-order traversal


Slide 15

Post-order traversal


Slide 16

Level-order traversal