Easy Notes Of Data structure using C unit-6 @Computer Diploma

Description

6.1 Introduction to Trees Terminologies

• Tree: A non-linear data structure consisting of nodes connected by edges, where any two nodes are connected by exactly one path. It must be an acyclic (no cycles) connected graph.

• Root (Node): The topmost node in a tree.

• Node: An entity in a tree that stores data and links to other nodes.

• Edge: The link connecting two nodes.

• Degree of a Node: The total number of subtrees attached to that node. (For a general tree)

• Degree of a Tree: The maximum degree of any node in the tree.

• Level of Node: The number of edges on the path from the root to the node. The root is typically at level 0.

• Leaf Node (Terminal Node): A node with a degree of zero (no children).

• Depth / Height of a Tree: The maximum level of any node in the tree.

• In-Degree: The number of edges coming into a node (always 1 for a non-root node in a standard tree, and 0 for the root).

• Out-Degree: The number of edges going out of a node (equivalent to the degree of a node).

• Path: The sequence of nodes and edges from one node to another.

• Ancestor Nodes: All nodes on the path from the root to the node, excluding the node itself.

• Descendant Nodes: All nodes in the subtree rooted at the node.

6.2 Tree Types and Traversal Methods

Tree Types

• • General Tree: A tree where a node can have any number of children.

  • Binary Tree: A tree where each node can have a maximum of two children (referred to as the left child and the right child).

• Binary Search Tree (BST): A special type of binary tree where, for every node:

  • All values in the left subtree are less than the node’s value.

  • All values in the right subtree are greater than the node’s value.

Binary Tree Traversal

Traversal is the process of visiting every node in the tree exactly once.

• In-Order Traversal: Left $\rightarrow$ Root $\rightarrow$ Right. For a BST, this yields the nodes in sorted order.

• Preorder Traversal: Root $\rightarrow$ Left $\rightarrow$ Right. Used to create a copy of the tree or for prefix expression.

• Post-Order Traversal: Left $\rightarrow$ Right $\rightarrow$ Root. Used to delete a tree or for postfix expression.

6.3 Expression Tree and Heap

• Expression Tree: A binary tree used to represent algebraic expressions. Operands are stored in leaf nodes, and operators are stored in internal nodes.

• Heap: A complete binary tree that satisfies the Heap Property.

  • Max Heap: For every node, the value is greater than or equal to its children’s values.

  • Min Heap: For every node, the value is less than or equal to its children’s values.

• Heap Sort: A comparison-based sorting algorithm that uses the Heap data structure to efficiently find the largest (or smallest) element.