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(); } } } |