2008级计算机 内部资料,仅供课堂教学使用 Chapter 10 BINARY TREES P. 429 1. General Binary Trees 3. Buildi Binary Search Tree 2. Binary Search Trees 4. Height Balance: AVL Trees 110.1 General Binary Trees Binary Trees P 430 10.1.1 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.2 Traversal of Binary Tree 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 RL V By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right V LR: preorder LVR inorder LR V: postorder 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 righ subtree ■With the left subtree. then traverse the right subtr and finally visit Expression Trees P. 435 tree of the quadratic formula P 436 10.1.3 Linked Binary Trees Comparison tree: P. 430 Linked implementation of binary tree: P. 439 Linked Binary Tree Specifications P 437-438 Binary tree class: P. 438 Binary node class: P 438 Constructor: P. 438 Empty: P. 438 10. 2| Binary Search Trees Can we find an implementation for ordered lists in which we can search quickly (as with binary search on a contiguous list) and in which we can make insertions and deletions quickly (as with a linked list)? DEFINITION: A binary search tree is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions The key of the left child of a node(if it exists) is less than the key of its parent node The key of the right child of a node (if it exists) is greater than the key of its parent node The left and right subtrees of the root are again binary search trees We always require: No two entries in a binary search tree may have equal keys We can regard binary search trees as a new AD We may regard binary search trees as a specialization of binary trees We may study binary search trees as a new implementation of the ADT ordered list 10. 2. 1 The Binary Search Tree Class The binary search tree class will be derived from the binary tree class, hence all binary tree methods are inherited P.446 The inherited methods include the constructors, the destructor, clear, empty, size, height, and the traversals reorder,inorder, and postorder A binary search tree also admits specialized methods called insert, remove, and tree search be compared with the usual comparison operators. By casting records to their corresponding keys, the s can The class Record has the behavior outlined in Chapter 7: Each Record is associated with a Key. The keys can comparison operators apply to records as well as to keys 10.2.2 Tree Search P 447 Error code Search tree<Record >: tree search( Record &target)const; P 447 This method will often be called with a parameter target that contains only a key value. The method will fill target with the complete data belonging to any corresponding Record in the tree To search for the target, we first compare it with the entry at the root of the tree. If their keys match, then we are finished. Otherwise, we go to the left subtree or right subtree as appropriate and repeat the search in that subtree2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 1 0 BINAR Y TREES P.429 ----------------------------------------------------------------------------------------------------------------------------- ---------- 1. General Binary Trees 2. Binary Search Trees 3. Building a Binary Search Tree 4. Height Balance: AVL Trees [10.1] General Binary Trees Binary Trees P. 430 10.1.1 DEFINITIO N: 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. 10.1.2 Traversal of Binary Trees P. 432 ⚫ 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: V L R L V R L R V V R L R V L R L V. By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right. V L R: preorder L V R: inorder L R V: postorder ⚫ 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 finally visit the node. Expression Trees P. 435 Expression tree of the quadratic formula P. 436 10.1.3 Linked Binary Trees Comparison tree: P. 430 Linked implementation of binary tree: P. 439 Linked Binary Tree Specifications P. 437-438 Binary tree class: P. 438 Binary node class: P. 438 Constructor: P. 438 Empty: P. 438 Inorder traversal: P. 439-440 Binary Tree Class Specification P. 441 [10.2] Binary Search Trees Can we find an implementation for ordered lists in which we can search quickly (as with binary search on a contiguous list) and in which we can make insertions and deletions quickly (as with a linked list)? DEFINITION: A binary search tree is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions: ◼ The key of the left child of a node (if it exists) is less than the key of its parent node. ◼ The key of the right child of a node (if it exists) is greater than the key of its parent node. ◼ The left and right subtrees of the root are again binary search trees. We always require: No two entries in a binary search tree may have equal keys. ⚫ We can regard binary search trees as a new ADT. ⚫ We may regard binary search trees as a specialization of binary trees. ⚫ We may study binary search trees as a new implementation of the ADT ordered list. 10.2.1 The Binary Search Tree Class ⚫ The binary search tree class will be derived from the binary tree class; hence all binary tree methods are inherited. P. 446 ⚫ The inherited methods include the constructors, the destructor, clear, empty, size, height, and the traversals preorder, inorder, and postorder. ⚫ A binary search tree also admits specialized methods called insert, remove, and tree_search. ⚫ The class Record has the behavior outlined in Chapter 7: Each Record is associated with a Key. The keys can be compared with the usual comparison operators. By casting records to their corresponding keys, the comparison operators apply to records as well as to keys. 10.2.2 Tree Search P. 447 Error_code Search_tree<Record > :: tree_search(Record &target) const; P. 447 ⚫ This method will often be called with a parameter target that contains only a key value. The method will fill target with the complete data belonging to any corresponding Record in the tree. ⚫ To search for the target, we first compare it with the entry at the root of the tree. If their keys match, then we are finished. Otherwise, we go to the left subtree or right subtree as appropriate and repeat the search in that subtree