Introduction to Tree
Tree program in C data structuredata structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as set of linked nodes. A tree can also be seen as collection of nodes, where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.
A tree exhibits following properties:
• There is exactly one root
• All nodes except the root have precisely one parent.
• There are no cycles.
Binary Tree C Implementation
The simplest form of a tree is a binary tree, one in which all nodes have at most two children. For a given node in a binary tree, the first child is referred to as the left child, while the second child is referred to as the right child.
Terminology
Parent Node: A node that has a child is called the child’s parent node.
Root Node: Special node of the tree having no parent.
Siblings: Any pair of node having same parent node.
Ancestor: The predecessor of a node together with all the ancestors of the predecessor of a node. The root node has no ancestors.
Descendant: The children of a node together with all the descendants of the children of a node. A leaf node has no descendants.
Binary Search tree
Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree property.
The height of a binary (search) tree equals the number of nodes from the root node to the deepest node of the tree.
Implementation of Binary Search Tree in C Programming (BsT)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace DataStructure { class BST { // Creating Binary Search Tree node class class Node { public int data; public Node left; public Node right; public Node( int value) { this .data = value; left = null ; right = null ; } } class BinarySearchTree { public Node root; static int count; public BinarySearchTree() { root = null ; } // Creates and returns a BST node public Node addNode( int data) { Node temp = new Node(data); if (root == null ) root = temp; count++; return temp; } // Procedure inserts 'newNode' in BST at proper position public void insert(Node root, Node newNode) { while (root != null ) { if (newNode.data > root.data) { if (root.right == null ) { root.right = newNode; break ; } root = root.right; } else { if (root.left == null ) { root.left = newNode; break ; } root = root.left; } } } // Recursive Procedure travels BST tree in Inorder Fashion (left subtree -> root -> right Subtree) public void inorder(Node root) { if (root!= null ) { inorder(root.left); Console.Write(root.data + " " ); inorder(root.right); } } } static void Main( string [] args) { BinarySearchTree bst = new BinarySearchTree(); // Inserting Nodes to Binary search Tree bst.insert(bst.root, bst.addNode(21)); bst.insert(bst.root, bst.addNode(19)); bst.insert(bst.root, bst.addNode(7)); bst.insert(bst.root, bst.addNode(19)); bst.insert(bst.root, bst.addNode(16)); bst.insert(bst.root, bst.addNode(13)); bst.insert(bst.root, bst.addNode(8)); bst.insert(bst.root, bst.addNode(22)); // Traversing BST in Inorder fashion bst.inorder(bst.root); Console.ReadKey(); } } } |