Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Algorithms and data structures (CSC112) - Chapter 27

Chapter 27 - Binary Tree. In this chapter, you learned about the notation used in entity relationship diagrams, important data modeling patterns, guidelines to avoid common modeling errors, and conversion of entity relationship diagrams (ERDs) into relational tables. You applied this knowledge to construct ERDs for small, narrative problems. This chapter extends your database design skills by presenting normalization techniques to remove redundancy in relational tables. | Review Binary Tree Binary Tree Representation Array Representation Link List Representation Operations on Binary Trees Traversing Binary Trees Pre-Order Traversal Recursively In-Order Traversal Recursively Post-Order Traversal Recursively For Example The preorder traversal of this binary tree is A, B, D, E, H, I, C, F, G, J. 2 For Example The in order traversal of this binary tree is D, B, H, E, I, A, F, C, J, G. 3 For Example The post order traversal of this binary tree is D, H, I, E, B, F, J, G, C, A 4 Binary Search Trees Binary Search Trees Operations on Binary Search Tree Inserting a Node Searching a Node Deleting a Node Expression Tree Decision Tree Binary Search Trees A Binary Search Tree is a binary tree, which is either empty or satisfies the following properties: 1. Every node has a value and no two nodes have the same value (i.e., all the values are unique) 2. If there exists a left child or left sub tree then its value is less than the value of the root 3. The value(s) in the right child or right sub tree is larger than the value of the root node All the nodes or sub trees of the left and right children follows above rules 6 For Example This figure shows an example of binary search tree Here the root node information is 50 The right sub tree node’s value is greater than 50, and the left sub tree nodes value is less than 50 Again right child node of 25 has large values than 25 and left child node has small values than 25 Similarly right child node of 75 has large values than 75 and left child node has small values that 75 and so on 7 Operations on Binary Search Tree The operations performed on binary tree can also be applied to Binary Search Tree (BST) Most commonly performed operation on BST is, traversal. The tree traversal algorithm (pre-order, post-order and in-order) are the standard way of traversing a binary search tree In this section we discuss few other operations performed on BST: 1. Inserting/Adding a node 2. Searching a node 3. Deleting a . | Review Binary Tree Binary Tree Representation Array Representation Link List Representation Operations on Binary Trees Traversing Binary Trees Pre-Order Traversal Recursively In-Order Traversal Recursively Post-Order Traversal Recursively For Example The preorder traversal of this binary tree is A, B, D, E, H, I, C, F, G, J. 2 For Example The in order traversal of this binary tree is D, B, H, E, I, A, F, C, J, G. 3 For Example The post order traversal of this binary tree is D, H, I, E, B, F, J, G, C, A 4 Binary Search Trees Binary Search Trees Operations on Binary Search Tree Inserting a Node Searching a Node Deleting a Node Expression Tree Decision Tree Binary Search Trees A Binary Search Tree is a binary tree, which is either empty or satisfies the following properties: 1. Every node has a value and no two nodes have the same value (i.e., all the values are unique) 2. If there exists a left child or left sub tree then its value is less than the value of the root 3. The value(s) in .