Data Structur Tree PDF

Data Structur Tree A.Lec. Musafa ALkhazaji Tree Data Structrue A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of nodes (where the data is stored) that are connected via links. The tree data structure stems from a single node called a root node and...

Data Structur Tree A.Lec. Musafa ALkhazaji Tree Data Structrue A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of nodes (where the data is stored) that are connected via links. The tree data structure stems from a single node called a root node and has subtrees connected to the root. Trees are used in many areas of computer science, including: Database Indexing: Trees are used in databases to enable quick data retrieval. File Systems: Directories and files are structured as trees. GUIs: Graphical user interfaces use trees to manage the hierarchical view of elements. AI: Decision trees are used in artificial intelligence for decision-making processes. Networking: Trees are used in routing and network algorithms. Sorting: Trees play a role in several sorting algorithms, like heapsort. Important Terms Following are the important terms with respect to tree. Path − Path refers to the sequence of nodes along the edges of a tree. Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. Parent − Any node except the root node has one edge upward to a node called parent. Child − The node below a given node connected by its edge downward is called its child node. Leaf − The node which does not have any child node is called the leaf node. Subtree − Subtree represents the descendants of a node. Types of Trees There are three types of trees − -General Trees -Binary Trees -Binary Search Trees General Trees General trees are unordered tree data structures where the root node has minimum 0 or maximum ‘n’ subtrees. The General trees have no constraint placed on their hierarchy. The root node thus acts like the superset of all the other subtrees. Binary Tree Binary tree is a tree data structure(non-linear) in which each node can have at most two children which are referred to as the left child and the right child. The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves. A binary tree can be visualized as a hierarchical structure with the root at the top and the leaves at the bottom. Representation of Binary Tree Each node in a Binary Tree has three parts: Data Pointer to the left child Pointer to the right child Binary Search Trees Binary Search Trees possess all the properties of Binary Trees including some extra properties of their own, based on some constraints, making them more efficient than binary trees. The data in the Binary Search Trees (BST) is always stored in such a way that the values in the left subtree are always less than the values in the root node and the values in the right subtree are always greater than the values in the root node, i.e. left subtree < root node ≤ right subtree. Advantages of BST Binary Search Trees are more efficient than Binary Trees since time complexity for performing various operations reduces. Since the order of keys is based on just the parent node, searching operation becomes simpler. The alignment of BST also favors Range Queries, which are executed to find values existing between two keys. This helps in the Database Management System. Disadvantages of BST The main disadvantage of Binary Search Trees is that if all elements in nodes are either greater than or lesser than the root node, the tree becomes skewed. Simply put, the tree becomes slanted to one side completely. This skewness will make the tree a linked list rather than a BST, since the worst case time complexity for searching operation becomes O(n). To overcome this issue of skewness in the Binary Search Trees, the concept of Balanced Binary Search Trees was introduced. ‫>‪#include data‬‬ ‫;)‪root->left = insert(root->left, value‬‬ ‫}‬ ‫إذا كانت قيمة العقدة أكبر من الجذر‪ ،‬نضيفها في الفرع األيمن ‪//‬‬ ‫{ ‪else‬‬ ‫;)‪root->right = insert(root->right, value‬‬ ‫}‬ ‫;‪return root‬‬ ‫}‬ ( ‫ دالة لطباعة محتويات الشجرة بأسلوب الترتيب الوسطي‬//in-order traversal) void inorderTraversal(Node* root) { if (root != nullptr) { inorderTraversal(root->left); cout data right); } } int main() { Node* root = nullptr; // ‫جذر الشجرة‬ ‫ إدخال بعض القيم إلى الشجرة‬// root = insert(root, 50); insert(root, 30); insert(root, 70); insert(root, 20); insert(root, 40); insert(root, 60); insert(root, 80); cout