RECURSIVE DATATYPES
Recursive datatypes play a crucial role in defining complex data structures such as binary trees. This content delves into the concept of recursive datatypes, specifically focusing on binary trees and their node structures. Each node in a binary tree contains a value and two other binary trees, illustrating the recursive nature of this data structure. Through examples and visual representations, the content demonstrates how nodes are constructed within a binary tree, showcasing different scenarios with values and empty nodes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
RECURSIVE DATATYPES David Kauchak CS52 Spring 2017
Recursive datatype - Defines a type variable for use in the datatype constructors - Still just defines a new type called binTree
Recursive datatype What is this?
Recursive datatype Binary Tree! a A binary tree is a recursive data structure where each node in the tree consists of a value and then two other binary trees. a binTree a binTree
Recursive datatype Node(Empty, 1, Empty); What does this look like?
Recursive datatype Node(Empty, 1, Empty); 1 Empty Empty
Recursive datatype Node(Node(Empty, 3, Node(Empty, 4, Empty)), 5, Node(Empty, 9, Empty)); What does this look like?
Recursive datatype Node(Node(Empty, 3, Node(Empty, 4, Empty)), 5, Node(Empty, 9, Empty)); 5 9 3 4 Empty Empty Empty Empty Empty
Recursive datatype Node(Node(Empty, apple , Node(Empty, banana , Empty)), carrot , Node(Empty, rhubarb , Empty)); What does this look like?
Recursive datatype Node(Node(Empty, apple , Node(Empty, banana , Empty)), carrot , Node(Empty, rhubarb , Empty)); carrot apple rhubarb banana Empty Empty Empty Empty Empty
