Data Structures Lecture 8: Trees

What is a Tree?

• A tree is a collection of nodes with specific properties
• A tree can be empty or consist of a root node and zero or more non-empty subtrees connected by directed edges
• The root node is the parent of each subtree root, and each subtree root is a child of the root node
• A tree with N nodes has N-1 edges

Preliminaries

• A node can have multiple children, and a child node has only one parent
• Leaf nodes have no children
• Sibling nodes have the same parent node
• A path is a sequence of nodes where each node is the parent of the next node
• The length of a path is the number of edges in the path
• The depth of a node is the length of the path from the root to the node
• The height of a node is the length of the longest path from the node to a leaf node

Implementation of Trees

• A tree can be implemented using a struct with pointers to the first child and next sibling nodes
• Each node has an element and pointers to its first child and next sibling nodes

Binary Trees

• A binary tree is a tree where each node has at most two children
• The depth of a node can be as large as N-1 in the worst case
• A binary tree consists of a root node and two subtrees, which can be empty

Tree Traversals

Postorder Traversal

• A node is visited after its descendants
• Application: compute space used by files in a directory and its subdirectories

Inorder Traversal

• Left node is visited, then the Root node, and finally the right node (for binary trees)
• Application: fast sorting on binary search trees

Binary Tree Traversals

• There are three types of traversals: preorder, inorder, and postorder

The BinaryNode Class

• A template class for binary nodes with an element, left child, and right child

Preorder, Inorder, and Postorder Traversal Functions

• Each function has a specific order of visiting nodes in a tree

Learn about trees in data structures, including their properties and characteristics, and how they are structured with nodes and sub-trees.