|
Arabic
Bengali
Chinese
English
French
German
Hebrew
Hindi
Italian
Japanese
Korean
Malay
Polish
Portuguese
Spanish
Turkish
Ukrainian
Vietnamese|
Lecture notes, cheat sheets
Computer science and information technology. Graphs (lecture notes)
Directory / Lecture notes, cheat sheets Table of contents (expand) LECTURE No. 9. Tree-like data structures 1. Tree Data Structures A tree-like data structure is a finite set of elements-nodes between which there are relations - the connection between the source and the generated. If we use the recursive definition proposed by N. Wirth, then a tree data structure with base type t is either an empty structure or a node of type t, with which a finite set of tree structures with base type t, called subtrees, is associated. Next, we give the definitions used when operating with tree structures. If node y is located directly below node x, then node y is called the immediate descendant of node x, and x is the immediate ancestor of node y, i.e., if node x is at the i-th level, then node y is accordingly at (i + 1) - th level. The maximum level of a tree node is called the height or depth of the tree. An ancestor does not have only one node of the tree - its root. Tree nodes that have no children are called leaf nodes (or leaves of the tree). All other nodes are called internal nodes. The number of immediate children of a node determines the degree of that node, and the maximum possible degree of a node in a given tree determines the degree of the tree. Ancestors and descendants cannot be interchanged, i.e., the connection between the original and the generated acts only in one direction. If you go from the root of the tree to some particular node, then the number of branches of the tree that will be traversed in this case is called the length of the path for this node. If all branches (nodes) of a tree are ordered, then the tree is said to be ordered. Binary trees are a special case of tree structures. These are trees in which each child has at most two children, called the left and right subtrees. Thus, a binary tree is a tree structure whose degree is two. The ordering of a binary tree is determined by the following rule: each node has its own key field, and for each node the key value is greater than all keys in its left subtree and less than all keys in its right subtree. A tree whose degree is greater than two is called strongly branched. 2. Operations on trees Further, we will consider all operations in relation to binary trees. I. Tree construction We present an algorithm for constructing an ordered tree. 1. If the tree is empty, then the data is transferred to the root of the tree. If the tree is not empty, then one of its branches is descended in such a way that the order of the tree is not violated. As a result, the new node becomes the next leaf of the tree. 2. To add a node to an already existing tree, you can use the above algorithm. 3. When deleting a node from the tree, you should be careful. If the node to be removed is a leaf, or has only one child, then the operation is simple. If the node to be deleted has two descendants, then it will be necessary to find a node among its descendants that can be put in its place. This is necessary due to the requirement that the tree be ordered. You can do this: swap the node to be removed with the node with the largest key value in the left subtree, or with the node with the smallest key value in the right subtree, and then delete the desired node as a leaf. II. Finding a node with a given key field value When performing this operation, it is necessary to traverse the tree. It is necessary to take into account different forms of tree notation: prefix, infix and postfix. The question arises: how to represent the nodes of the tree so that it is most convenient to work with them? It is possible to represent a tree using an array, where each node is described by a combined type value, which has a character-type information field and two reference-type fields. But this is not very convenient, since the trees have a large number of nodes that are not predetermined. Therefore, it is best to use dynamic variables when describing a tree. Then each node is represented by a value of the same type, which contains a description of a given number of information fields, and the number of corresponding fields must be equal to the degree of the tree. It is logical to define the absence of descendants with nil. Then, in Pascal, the description of a binary tree might look like this: TYPE TreeLink = ^Tree; tree = record; Inf : <datatype>; Left, Right : TreeLink; End. 3. Examples of the implementation of operations 1. Construct a tree of n nodes of minimum height, or a perfectly balanced tree (the number of nodes of the left and right subtrees of such a tree must differ by no more than one). Recursive construction algorithm: 1) the first node is taken as the root of the tree. 2) the left subtree of nl nodes is built in the same way. 3) the right subtree of nr nodes is built in the same way; nr = n - nl - 1. As an information field, we will take the node numbers entered from the keyboard. The recursive function that implements this construction will look like this: Function Tree(n : Byte) : TreeLink; Var t : TreeLink; nl,nr,x : Byte; Begin If n = 0 then Tree := nil else Begin nl := n div 2; nr = n - nl - 1; writeln('Enter vertex number '); readln (x); new(t); t^.inf := x; t^.left := Tree(nl); t^.right := Tree(nr); Tree := t; End; {Tree} End. 2. In the binary ordered tree, find the node with the given value of the key field. If there is no such element in the tree, then add it to the tree. Search Procedure(x : Byte; var t : TreeLink); Begin If t = nil then Begin New(t); t^inf := x; t^.left := nil; t ^ .right: = nil; End Else if x < t^.inf then Search(x, t^.left) Else if x > t^.inf then Search(x, t^.right) else Begin {process found element} ... End; End. 3. Write tree traversal procedures in forward, symmetric and reverse order, respectively. 3.1. Procedure Preorder(t : TreeLink); Begin If t <> nil then Begin WriteIn(t^.inf); Preorder(t^.left); Preorder(t^.right); End; End; 3.2. Procedure Inorder(t : TreeLink); Begin If t <> nil then Begin Inorder(t^.left); WriteIn(t^.inf); Inorder(t^.right); End; End. 3.3. Procedure Postorder(t : TreeLink); Begin If t <> nil then Begin postorder(t^.left); postorder(t^.right); WriteIn(t^.inf); End; End. 4. In the binary ordered tree, delete the node with the given value of the key field. Let us describe a recursive procedure that will take into account the presence of the required element in the tree and the number of descendants of this node. If the node to be deleted has two children, then it will be replaced by the largest key value in its left subtree, and only then will it be permanently deleted. Procedure Delete1(x : Byte; var t : TreeLink); Var p : TreeLink; Procedure Delete2(var q : TreeLink); Begin If q^.right <> nil then Delete2(q^.right) else Begin p^.inf := q^.inf; p := q; q := q^.left; End; End; Begin If t = nil then Writeln('no element found') Else if x < t^.inf then Delete1(x, t^.left) Else if x > t^.inf then Delete1(x, t^.right) else Begin P := t; If p^.left = nil then t := p^.right else If p^.right = nil then t := p^.left else Delete2(p^.left); End; End. Author: Tsvetkova A.V. << Back: Tree Data Structures (Tree data structures. Operations on trees. Examples of implementation of operations) >> Forward: Object data type (Object type in Pascal. The concept of an object, its description and use. Inheritance. Creating instances of objects. Components and scope)
▪ Summary of works of Russian literature of the first half of the XNUMXth century ▪ Criminal executive law. Lecture notes ▪ State and municipal finance. Lecture notes
The existence of an entropy rule for quantum entanglement has been proven
09.05.2024 Mini air conditioner Sony Reon Pocket 5
09.05.2024 Energy from space for Starship
08.05.2024
▪ Beosound Balance wireless speaker ▪ Artificial eyelashes controlled by magnet and light ▪ Gravitational waves could help predict tsunamis ▪ E Ink Mobius screens for smartwatches ▪ Quiet New Fujitsu Celsius Workstations
▪ section of the site Mobile communications. Article selection ▪ article Long box. Popular expression ▪ article Is there a lot of water in a cactus? Detailed answer ▪ article Machinist of dust pumps. Standard instruction on labor protection
Home page | Library | Articles | Website map | Site Reviews
www.diagram.com.ua |
We recommend interesting articles Section 
See other articles Section 
Latest news of science and technology, new electronics:
All languages of this page