Trees Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka ATCZ62 - CLIL jako výuková strategie na vysoké škole C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Tree •In computer science, a tree is an abstract model of a hierarchical structure •A tree consists of nodes with a parent-child relation •Applications: •Organization charts •File systems •Programming environments C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Tree Terminology •Root: node without parent (A) •Internal node: node with at least one child (A, B, C, F) •External node (a.k.a. leaf ): node without children (E, I, J, K, G, H, D) •Ancestors of a node: parent, grandparent, grand-grandparent, etc. •Depth of a node: number of ancestors •Height of a tree: maximum depth of any node (3) •Descendant of a node: child, grandchild, grand-grandchild, etc •Subtree: tree consisting of a node and its descendants C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Tree – ADT C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Trees - traversal •Pre-order Traversal •Check if the current node is empty / null. •Display the data part of the root (or current node). •Traverse the left subtree by recursively calling the pre-order function. •Traverse the right subtree by recursively calling the pre-order function. •In-order průchod •Check if the current node is empty / null. •Traverse the left subtree by recursively calling the in-order function. •Display the data part of the root (or current node). •Traverse the right subtree by recursively calling the in-order function. C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Tree Traversal •Post-order průchod •Check if the current node is empty / null. •Traverse the left subtree by recursively calling the post-order function. •Traverse the right subtree by recursively calling the post-order function. •Display the data part of the root (or current node). • •Pre-order: F, B, A, D, C, E, G, I, H •In-order: A, B, C, D, E, F, G, H, I •Post-order: A, C, E, D, B, H, I, G, F • C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Binary tree •A binary tree is a tree with the following properties: •Each internal node has two children •The children of a node are an ordered pair •Applications: •arithmetic expressions •decision processes •searching • C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Binary Tree – ADT •The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT •Additional methods: •position leftChild(p) •position rightChild(p) •position sibling(p) •Update methods may be defined by data structures implementing the BinaryTree ADT •