CS 121 Lecture Notes - Lecture 81: Binary Tree
Non-Linear Data Structures:
Trees: a non-linear data structure that consists of a root node & potentially
many levels of additional nodes that form a hierarchy.
oInternal Nodes: all nodes other than the root.
oLeaf Nodes: nodes that have no children.
The tree is drawn “upside down” w/ the root at the top & the
leaves at the bottom.
oIn a general tree, each node could have many child nodes.
The inheritance relationships among classes can be depicted
using a general tree structure.
oIn a binary tree, each node can have no more than 2 child nodes.
Binary trees are useful in various programming situations & usually
easier to implement than general trees.
Technically, binary trees are a subset of general trees.
oThe operations on trees & binary trees vary, but minimally include adding
& removing nodes from the tree or binary tree.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Trees: a non-linear data structure that consists of a root node & potentially many levels of additional nodes that form a hierarchy: internal nodes: all nodes other than the root, leaf nodes: nodes that have no children. The tree is drawn upside down w/ the root at the top & the leaves at the bottom: in a general tree, each node could have many child nodes. The inheritance relationships among classes can be depicted using a general tree structure: in a binary tree, each node can have no more than 2 child nodes. Binary trees are useful in various programming situations & usually easier to implement than general trees. Technically, binary trees are a subset of general trees: the operations on trees & binary trees vary, but minimally include adding. & removing nodes from the tree or binary tree. B/c of their non-linear nature, trees & binary trees are implemented nicely using references as dynamic links.