CS310 Lecture 09: Tree Data Structures

Introduction to Tree Data Structures

Data structures previously covered in the course include arrays, singly-linked lists, doubly-linked lists, stacks, queues, and double-ended queues. These are categorized as linear data structures because their elements can be displayed in a straight line. In contrast, trees are fundamental nonlinear data structures that store elements hierarchically. A tree consists of nodes connected by edges without containing any cycles. Every node in a tree, with the exception of the root node, has exactly one parent and may have zero or more child nodes. Furthermore, every node in the tree is considered the root of its own subtree, except for leaf nodes.

Identifying Tree Structures

To be classified as a tree, a structure must follow specific rules. A single linear list is technically a tree. However, certain configurations disqualify a structure from being a tree. For example, a cycle where a node points to itself ($A \rightarrow A$) or a larger cycle (e.g., $B \rightarrow C \rightarrow E \rightarrow D \rightarrow B$) prevents the structure from being a tree. Additionally, a structure with non-connected parts, such as one group of nodes ($A \rightarrow B$) and a separate group ($C \rightarrow D \rightarrow E$), is not considered a single tree.

Fundamental Tree Terminology

There are numerous terms used to describe the specific aspects and components of tree structures. The Root is the unique node at the top of the tree; there is only one root node per tree. A Leaf, also known as an external node, is a node that has no children. A Parent is any node (excluding leaves) that has at least one edge leading out to another node. A Child is any node (excluding the root) that has an edge leading in from a parent. A Subtree consists of a specific node along with all its children and their descendants. Visiting refers to the moment program control accesses a node, while Traversing is the process of visiting all nodes in the tree in a specific order exactly once.

Additional structural terms include the Path, which describes the route taken when walking from node to node along edges. An Edge is the physical connection between nodes. The Depth of a node is defined as the number of edges from that specific node to the root. The Size of a tree is the total count of nodes; for instance, a tree with $9$ nodes has a size of $9$. Levels refer to the number of generations a node is from the root. Keys or Values represent the data field within a node. The Height of the Tree is the maximum depth among all leaves of the tree. Siblings are nodes that share the same parent. An Internal Node is any node that possesses at least one child.

Exercise: Analyzing Tree Properties

In a sample tree with nodes labeled $A$ through $I$, various properties can be identified. The levels start at $0$ for the root $A$. Level $1$ contains nodes $B$ and $C$, level $2$ contains $D, E, F, G,$ and $H$, and level $3$ contains $I$. In this scenario, node $B$ is the parent of $D$ and $E$. Node $G$ is the child of $C$. Nodes $F, G,$ and $H$ are siblings. The internal nodes of this tree are $A, B, C,$ and $H$. The leaf nodes are $D, E, F, G,$ and $I$. The size of this tree is $9$. The depth of node $H$ is $2$, and the total height of the tree is $3$.

Binary Tree Definitions and Types

A Binary Tree is a specific type of tree that is either empty or consists of a root node and two binary trees referred to as the Left Subtree and the Right Subtree. In a binary tree, every node has at most two children. A Proper or Full Binary Tree is a subset where every node has either zero or exactly two children; in these trees, every internal node must have exactly two children.

Binary Tree Abstract Data Type (ADT)

The Binary Tree ADT is designed to store arbitrary objects. The main tree operations include various Traversal methods, a boolean Search(object) function, Insert(object), and Delete(object). There are also auxiliary operations such as boolean isInternal(p), boolean isExternal(p), and boolean isRoot(p). Boundary cases must be handled carefully; for example, attempting to traverse an empty tree or deleting a non-existent object will return null.

Binary Tree Implementation and Node Structure

The implementation of a Binary Tree typically utilizes a node structure similar to that of a linked list. Each node in a Binary Tree consists of four primary components: the Element which stores the actual data, the Left address which points to the left child, the Right address which points to the right child, and the Parent address which points to the node's parent. This allows for a linked representation of the hierarchical structure.

Tree Traversing Operations

A traversal visits each node in a tree exactly once in a specific order. For a tree with $n$ nodes, there are $n!$ possible traversals. The two most common broad categories are Breadth-First and Depth-First traversals. In a Breadth-First Traversal (also known as level-order traversal), all nodes on a given level are visited (usually from left to right) before moving to the next level. Depth-First Traversal visits all nodes on a specific branch before visiting others. Standard conventions reduce the six possible ways to traverse a binary tree to three common methods by ensuring the left subtree is always traversed before the right subtree: Pre-order, In-order, and Post-order. Each of these is best implemented via recursive functions.

Depth-First Traversal Algorithms

Pre-order traversal follows the sequence: root, left subtree, right subtree. The recursive algorithm checks if the node is null, displays the node value, then recursively calls PreOrderPrint on the left and right children. In Java, this is written as:

public void preorderPrint(BinaryTreeNode bt) { if (bt == null) return; System.out.println(bt.value); preorderPrint(bt.leftChild); preorderPrint(bt.rightChild); }

In-order traversal follows the sequence: left subtree, root, right subtree. The Java implementation is:

public void inorderPrint(BinaryTreeNode bt) { if (bt == null) return; inorderPrint(bt.leftChild); System.out.println(bt.value); inorderPrint(bt.rightChild); }

Post-order traversal follows the sequence: left subtree, right subtree, root. The Java implementation is:

public void postorderPrint(BinaryTreeNode bt) { if (bt == null) return; postorderPrint(bt.leftChild); postorderPrint(bt.rightChild); System.out.println(bt.value); }

Arithmetic Expressions and Traversals

Binary trees can represent arithmetic formulas where internal nodes are operators and leaf nodes are operands. For an expression tree provided in the slides, the traversals correspond to different mathematical notations. An In-order traversal results in an infix expression (e.g., $A / B \times C \times D + E$). A Pre-order traversal results in a prefix expression (e.g., $+ \times \times / A B C D E$). A Post-order traversal results in a postfix expression (e.g., $A B / C \times D \times E +$). Level order traversal for the same tree results in $+ \times E \times D / C A B$.

Binary Search Trees (BST)

A Binary Search Tree (BST) is a specialized binary tree used for efficient searching. It possesses three key properties: every node is ordered by a key data field, for every node the key is greater than its left child's key and less than its right child's key, and the tree is not permitted to store duplicate values.

BST Insertion and Searching

Adding a new node to a BST involves searching for the correct placement and then inserting the element. The insertion rule states: if the new value equals the current node value, a duplicate is found and the process exits. If the new value is less than the current node's value, the algorithm moves to the left subtree; otherwise, it moves to the right. Finally, the node is inserted when a null position is reached. Searching operates similarly, traversing depth-wise and comparing the target value with visited nodes.

Recursive algorithms for finding the minimum and maximum values in a BST follow a simple logic: To find the minimum, repeatedly move to the left child until no more left children exist. To find the maximum, repeatedly move to the right child. The specific Java code for finding the minimum is:

public binaryNode findMin(binaryNode node){ if (isEmpty()) return null; while(node.getLeft() != null ) node = node.getLeft(); return node; }

BST Deletion Cases

Deleting a node from a BST requires careful management of the deleted node's children. Three specific cases arise. Case 1 involves deleting a leaf node, which is removed immediately by setting the parent's pointer to null. Case 2 involves a node with one child; in this instance, the node is replaced by its child node. Case 3 occurs when the node has two children. The strategy is to replace the target node with the minimum element from its right subtree (the in-order successor), then delete that redundant minimum element.

Java Implementation Overview

The BinarySearchTree class in Java includes inner private BinaryTreeNode objects. Key methods provided in the lab section include insert(int keyVal), delete(BinaryTreeNode TreeNode, int keyVal), and find(BinaryTreeNode node, int keyVal). Traversal methods (inorder, preorder, postorder) and helper functions (findMin, findMax, getRoot, getSize, isEmpty) are also essential components of the class structure.

Real-World Applications of Tree Structures

Trees are used extensively in computer science for diverse applications. These include File Systems (such as the hierarchical structures of Windows and Linux File Systems), representing algebraic formulas, and serving as efficient methods for searching large dynamic lists (e.g., primary keys in databases). In Artificial Intelligence (AI), trees are used for knowledge representation and dictionary data storing. Specific AI examples include Natural Language Processing (NLP) using Parse Trees to analyze sentence structures (NP, S, VP nodes) and Game Programming, such as using game trees to visualize various stages, wins, and losses in Tic-Tac-Toe.