Binary Trees and Binary Tree Traversals PDF
Document Details
Uploaded by Deleted User
Tags
Summary
This document provides an overview of binary trees, including their recursive definition, implementation, traversals (preorder, inorder, postorder), and methods for printing and reconstructing them. It also includes exercises on the topic.
Full Transcript
Binary Tree Traversals Recall the Recursive Definition A binary tree is a data structure that is either: empty (null), or comprised of a root node with disjoint left and right binary subtrees. Root node Left subtre...
Binary Tree Traversals Recall the Recursive Definition A binary tree is a data structure that is either: empty (null), or comprised of a root node with disjoint left and right binary subtrees. Root node Left subtree Right subtree Recursive Implementation public class Node { public T Item { get; set; } item public Node Left { get; set; } public Node Right { get; set; } left right public Node (T item, Node left, Node right) { Item = item; Left = left; Right = right; } } Binary Tree Class root class BinaryTree { Node root; public BinaryTree( ) { root = null; // Empty tree }... } root = new Node (x, leftroot, rightroot); root leftroot x rightroot Traversals A systematic way of traversing (visiting) the nodes of a binary tree There are three classical ways to do so: 1. Preorder traversal 2. Inorder traversal 3. Postorder traversal Traversals (follow the dots) Preorder Traversal (Red): FBADCEGIH Inorder Traversal (Yellow): ABCDEFGHI Postorder Traversal (Green): A C E D B H I G F Retrieved from Wikipedia, November 11, 2020 Preorder Traversal (Top Down) public void Preorder( ) private void Preorder (Node root) { { Preorder(root); if (root != null) } { Process root (red dot) Preorder(root.Left); Preorder(root.Right); } } Inorder Traversal (Left to Right) public void Inorder( ) private void Inorder (Node root) { { Inorder(root); if (root != null) } { Inorder(root.Left); Process root (yellow dot) Inorder(root.Right); } } Postorder Traversal (Bottom Up) public void Postorder( ) private void Postorder (Node root) { { Postorder(root); if (root != null) } { Postorder(root.Left); Postorder(root.Right); Process root (green dot) } } How To Print An OK Binary Tree public void Print( ) { Print(root, 0); } private void Print (Node root, int indent) { if (root != null) The indentation is larger as you go deeper into the tree { Print(root.Right, indent + 5); Console.WriteLine(new String(‘ ‘, indent) + root.Item); Print(root.Left, indent + 5); } } OK if you look sideways root 14 13 10 8 7 6 4 3 1 Reconstructing a Binary Tree It is not possible rebuild a unique binary tree given a single traversal For example, the prefix traversal A B yields two possible binary trees A A B B But two traversals will... but which two? The preorder or postorder traversal gives us the root of the binary tree The inorder traversal tells us which nodes are left and right of the root Therefore, we can reconstruct a binary tree using inorder AND (preorder OR postorder) traversals Let’s consider the following traversals Preorder F B A D C E G I H Inorder A B C D E F G H I Postorder A C E D B H I G F We’ll choose the Inorder and Preorder traversals to build the unique binary tree F Preorder: B A D C E Preorder: G I H Inorder: A B C D E Inorder: G H I F B G A Preorder: D C E Preorder: I H Inorder: C D E Inorder: H I F B G A D I C E H Look familiar? Exercises 1. Build a binary tree from its postorder and inorder traversals. 2. Is any one binary tree defined by the following traversals? Preorder: A B C D E F Inorder: B C F A D E 3. Write a recursive method that returns the minimum item in a binary tree. Think postorder. 4. What is the time complexity of an inorder traversal of a binary tree on n nodes?
