Chapter 10 BINARY TREES 1. General Binary trees 2. Binary Search Trees 3. Building a Binary Search Tree I4. Height Balance: AVL Trees I5. Splay Trees I6. Pointers and Pitfalls
Chapter 10 BINARY TREES 1. General Binary Trees 2. Binary Search Trees 3. Building a Binary Search Tree 4. Height Balance: AVL Trees 5. Splay Trees 6. Pointers and Pitfalls
10.1 Binary Trees 1. Definitions DEFINITION A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root (c)left subtree isn't empty (d)right subtree isn't empty d O (a) Empty (b)only root △ △△△ Basic shaper of Binary tree (e)both left right are not empty
10.1 Binary Trees DEFINITION A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root. 1. Definitions
2. Traversal of Binary Trees postorder At a given node there are three Ho in some order: Visit the node itself ere ts left subtree (L); traverse its rib sukeVA. Ty Are are six ways to arrange these tasks VLR LVR RV VRL RVL RLV By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right These three names are chosen according to the step at which the given node is visited
2. Traversal of Binary Trees At a given node there are three tasks to do in some order: Visit the node itself (V); traverse its left subtree (L); traverse its right subtree (R). There are six ways to arrange these tasks: VLR LVR LRV VRL RVL RLV By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right. postorder preorder inorder These three names are chosen according to the step at which the given node is visited
With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree With inorder traversal we first traverse the left subtree, then visit the node, and then traverse its right subtree. With postorder traversal we first traverse the left subtree, then traverse the right subtree, and nally visit the node See pg 432-434
◆With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree. ◆With inorder traversal we first traverse the left subtree, then visit the node, and then traverse its right subtree. ◆With postorder traversal we first traverse the left subtree, then traverse the right subtree, and nally visit the node. See pg.432-434
Expression tree b b Epression: a+b logx n! a(bxc)(a< b)or(c< d) Preorder: +a b log x! a×bcor<ab<cd nordel a +b log x ni a-bxc a< b or c< d Postorder: a b+ x log n! a bcx- a b< cd < or
Expression tree