ECE250 Lecture Notes - Lecture 13: Binary Tree, Type Class, Microsoft Powerpoint

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE250
• Professor: Douglas Harder

Document Summary

A binary tree is a general tree, however the node has a restriction of exactly two children: each child is either empty or has two children. We also refer to the sub-trees as: the left hand sub tree, the right hand sub tree. A full node is defined to have a left and right sub-tree in which they are non-empty trees. An empty node is a null sub-tree in which a node can be appended to it. A full binary tree is defined in which all nodes are either a full node or a leaf node. Run times: recall that the run time for linked lists and arrays are (n, the run time of a binary tree will depend on the height of the tree. A rope is a general tree structure where all internal nodes represent the concatenation and all leaf nodes are strings: expression trees. Given any mathematical expression, we can express that in a tree structure.