Nguyen Ho Man Rang a Chapter 7 s Trees —— Concepts. Binary Trees Data Structures and Algorithms Expression Trees Binary Search Trees Dr. Nguyen Ho Man Rang Faculty of Computer Science and Engineering University of Technology, VNU-HCM Outcomes Trees Dr. Nguyen Ho Man Rang L.1 - Depict the following concepts: binary tree, complete binary tree, balanced binary tree, AVL tree, s multi-way tree, etc.2 - Describe the strorage structure for tree Ease structures using pseudocode.3 - List necessary methods supplied for tree Expression Trees structures, and describe them using pseudocode.
Binary Search Trees L.4 - Identify the importance of “blanced” feature in tree structures and give examples to demonstate it.5 - Identiy cases in which AVL tree and B-tree are unblanced, and demonstrate methods to resolve all the cases step-by-step using figures. Outcomes Trees Dr. Nguyen Ho Man Rang L.6 - Implement binary tree and AVL tree using C/C++.7 - Use binary tree and AVL tree to solve s problems in real-life, especially related to searching techniques.8 - Analyze the complexity and develop Bien Tes experiment (program) to evaluate methods supplied for Expression Trees tree structures. Binary Search Trees L.4 - Develop recursive implementations for methods supplied for the following structures: list, tree, heap, searching, and graphs.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion).
Contents @ Basic Tree Concepts @ Binary Trees © Expression Trees @ Binary Search Trees Trees Dr. Nguyen Ho Man Rang a <3 Basic Tree Concepts Binary Trees Expression Trees Binary Search Trees TA Basic Tree Concepts Trees Basic Tree Concepts Dr. Nguyen Ho Man Rang Definition A tree (cay) consists of a finite set of elements, called nodes đà (nút), and a finite set of directed lines, called branches TS (nhánh), that connect the nodes. (a) Binary Trees Expression Trees Binary Search Trees Basic Tree Concepts Trees Dr.
Nguyen Ho © Degree of a node (Bac ciia nit): the number of __: branches associated with the node. đà ® Indegree branch (Nhánh vào): directed branch toward BK the node. © Outdegree branch (Nhanh ra): directed branch away from the node. 8m Binary Trees đà For the node d: Expression Trees Binary Search ° Degree = 4 Trees e Indegree branches: ad — indegree = 1 @) (2 (a) © Outdegree branches: dg, dh, di — outdegree = 3 Tử Basic Tree Concepts ® The first node ¡is called the root.
® indegree of the root = 0 ® Except the root, the indegree of a node = 1 ® outdegree of a node = 0 or 1 or more. Nguyen Ho Man Rang g- 8mm Binary Trees Expression Trees Binary Search Trees Basic Tree Concepts Trees Dr. Nguyen Ho Terms Man Rang © A root (nit géc) is the first node with an indegree of đà zero. s ® A leaf (nút lá) is any node with an outdegree of zero.
® A internal node (nút nội) is not a root or a leaf. mw ® A parent (nút cha) has an outdegree greater than zero. Binary Trees ® A child (nút con) has an indegree of one. Expression Trees — a internal node is both a parent of a node and a Binary Search Trees child of another one.
© Siblings (nit anh em) are two or more nodes with the same parent. e For a given node, an ancestor is any node in the path from the root to the node. e For a given node, an descendent is any node in the paths from the node to a leaf. Basic Tree Concepts Terms ® A path (đường đi) is a sequence of nodes in which each node is adjacent to the next one.
© The level (bac) of a node is its distance from the root. — Siblings are always at the same level. © The height (d6 cao) of a tree is the level of the leaf in the longest path from the root plus 1. e A subtree (cay con) is any connected structure below the root.
Nguyen Ho Man Rang đà <3 ene Binary Trees Expression Trees Binary Search Trees Trees Basic Tree Concepts Dr. Nguyen Ho Level 0 -------------- Man Rang Branch ad 4 BK ù Level 1 -------( b }---( € } ----- Branch di Binary Trees Expression Trees Level 2----{ € } 4 f } ----- ee @ Parents: a,b,d @ Internal nodes: b,d © Children: e Siblings: b,c, d,e, f,g,h,t {b, c,d}, {e, fF}, {9, h, a} ® Leaves: c,e, ƒ,g,h,¡ ® Height = 3 Basic Tree Concepts Subtree b Subtree d Trees Dr. Nguyen Ho Man Rang a <3 ene Binary Trees Expression Trees Binary Search Trees Trees Tree representation Dr. Nguyen Ho Man Rang © organization chart © indented list pr ©.
b Cy © Xa ts (See f Binary Trees OQ GOO re c Binary Search Trees © parenthetical listing a(b(e fed (ghi)) ° Trees Applications of Trees Dr. Nguyen Ho Man Rang g- e Representing hierarchical data s ® Storing data in a way that makes it easily =n. Binary Trees searchable (ex: binary search tree) : Expression Trees Binary Search Trees © Representing sorted lists of data e Network routing algorithms Binary Trees Trees Dr. Nguyen Ho Man Rang đà Basic Tree Concepts Expression Trees Binary Search Trees Binary Trees A binary tree node cannot have more than two subtrees.
Right subtree Trees Dr. Nguyen Ho Man Rang a <3 Basic Tree Concepts Expression Trees Binary Search Trees Binary Trees Properties © To store N nodes in a binary tree: © The minimum height: Hmin = [logy N| +1 or Hmin = [logo(N + 1)] ® The maximum height: H„„„„ = © Given a height of the binary tree, H: © The minimum number of nodes: Nmin = H © The maximum number of nodes: Nmax = 2” Balance The balance factor of a binary tree is the difference between its left and right subtrees. B=Hị;¡- Hạ Balanced tree: ® balance factor is 0, -1, or 1 ® subtrees are balanced —1 in height Trees Dr. Nguyen Ho Man Rang e ¢: Basic Tree Concepts Expression Trees Binary Search Trees Trees Binary Trees Properties Dr.
Nguyen Ho Man Rang Complete tree N = Naz = 24 —1 (a) & The last level is full. Basic Tree Concepts (4) C) Œ) (9) Expression Trees Binary Search Trees Nearly complete tree H = Anin = |logg N| +1 (a) Nodes in the last level are on the left. (53 (2) Binary Tree Structure Definition A binary tree is either empty, or it consists of a node called root together with two binary trees called the left and the right subtree of the root. ~ €&> <=> © © CA €? & @& @) 0 (9) Trees Dr.
Nguyen Ho Man Rang đà Basic Tree Concepts Expression Trees Binary Search Trees Binary Tree Structure: Linked implementation node data <dataType> left <pointer> right <pointer> end node // General dataTye: dataType key <keyType> fieldl <.> end dataType Trees Dr. Nguyen Ho Man Rang binaryTree pr root <pointer> BK end binaryTree s Basic Tree Concepts Expression Trees root Binary Search | Trees Leaf node xi» xi Leaf node Trees Binary Tree Structure: Array-based implementation i Dr. Nguyen Ho Suitable for complete tree, nearly complete tree. Reece ca iow Basic Tree Concepts Expression Trees Binary Search Hinh: Conceptual Trees binaryTree data <array of dataType> 0123456 end binaryTree AIBICIDIEIEIG Hinh: Physical Binary Tree Traversals ® Depth-first traversal (duyệt theo chiều sâu): the processing proceeds along a path from the root through one child to the most distant descendent of that first child before processing a second child, i.
processes all of the descendents of a child before going on to the next child. © Breadth-first traversal (duyệt theo chiều rộng): the processing proceeds horizontally from the root to all of its children, then to its children’s children, i. each level is completely processed before the next level is started. Nguyen Ho Man Rang e ¢: Basic Tree Concepts Expression Trees Binary Search Trees Trees Depth-first traversal Dr.
Nguyen Ho Man Rang © Preorder traversal pr @ Inorder traversal s3 ® Postorder traversal Basic Tree Concepts. Expression Trees Binary Search Trees 2 3 t 1 2 w PreOrder InOrder PostOrder NLR LNR LRN Preorder traversal (NLR) In the preorder traversal, the root is processed first, before the left and right subtrees. Processing order Walking order Trees Dr. Nguyen Ho Man Rang đà Basic Tree Concepts Expression Trees Binary Search Trees Preorder traversal (NLR) Algorithm preOrder(val root <pointer>) Traverse a binary tree in node-left-right sequence.
Pre: root is the entry node of a tree or subtree Post: each node has been processed in order if root is not null then process(root) preOrder(root->left) preOrder(root->right) end Return Trees Dr. Nguyen Ho Man Rang e q: Basic Tree Concepts Expression Trees Binary Search Trees Inorder traversal (LNR) Trees Dr. Nguyen Ho Man Rang In the inorder traversal, the root is processed between its pr subtrees. BK a 3 Basic Tree Concepts Expression Trees Binary Search Trees Walking order [e}s(o}} «| LJe le] Processing order Inorder traversal (LNR) Algorithm inOrder(val root <pointer>) Traverse a binary tree in left-node-right sequence.
Pre: root is the entry node of a tree or subtree Post: each node has been processed in order if root is not null then inOrder(root->left) process(root) inOrder(root->right) end Return Trees Dr. Nguyen Ho Man Rang e q: Basic Tree Concepts Expression Trees Binary Search Trees Postorder traversal (LRN) Trees Dr. Nguyen Ho Man Rang In the postorder traversal, the root is processed after its pr subtrees. s¬» exc Basic Tree Concepts Expression Trees Binary Search Trees Walking order [ole | |LILe e} a Processing order Postorder traversal (LRN) AIgorithm postOrder(val root <pointer>) Traverse a binary tree in left-right-node sequence.
Pre: root is the entry node of a tree or subtree Post: each node has been processed in order if root is not null then postOrder(root->left) postOrder(root->right) process(root) end Return Trees Dr. Nguyen Ho Man Rang e q: Basic Tree Concepts Expression Trees Binary Search Trees Breadth-First Traversals Trees Dr. Nguyen Ho Man Rang In the breadth-first traversal of a binary tree, we process all pr of the children of a node before proceeding with the next s level. Basic Tree Concepts Expression Trees Binary Search Trees Walking order Processing order Breadth-First Traversals Algorithm breadthFirst(val root <pointer>) Process tree using breadth-first traversal.
Pre: root is node to be processed Post: tree has been processed currentNode = root bfQueue = createQueue() Trees Dr. Nguyen Ho Man Rang e q: Basic Tree Concepts Expression Trees Binary Search Trees Breadth-First Traversals while currentNode not null do process(currentNode) if currentNode->left not null then | enqueue(bfQueue, currentNode->left) end if currentNode->right not nul then | enqueue(bfQueue, currentNode->right) end if not emptyQueue(bfQueue) then | currentNode = dequeue(bfQueue) else | currentNode = NULL end end destroyQueue(bfQueue) End breadthFirst Trees Dr. Nguyen Ho Man Rang e q: Basic Tree Concepts Expression Trees Binary Search Trees Expression Trees Trees Dr. Nguyen Ho Man Rang a <3 Basic Tree Concepts Binary Trees Binary Search Trees Expression Trees © Each leaf is an operand © The root and internal nodes are operators ® Sub-trees are sub-expressions a*(b+c)+d Trees Dr.
Nguyen Ho Man Rang a c2 Basic Tree Concepts Binary Trees Binary Search Trees Trees Infix Expression Tree Traversal Dr. Nguyen Ho Man Rang a c2 Basic Tree Concepts Binary Trees _ [@*ob+o+*)). Binary Search Trees Infix Expression Tree Traversal AIgorithm infix(val tree <pointer>) Print the infix expression for an expression tree. Pre: tree is a pointer to an expression tree Post: the infix expression has been printed if tree not empty then if tree->data is an operand then | print (tree->data) else print (open parenthesis) infix (tree->left) print (tree->data) infix (tree->right) print (close parenthesis) end end End infix Trees Dr.