ECE250 Lecture Notes - Lecture 13: Binary Tree, Type Class, Microsoft Powerpoint
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.