Binary Tree - C Program source code

​

1. #include < stdio.h>

2. #include<stdlib.h>

3.  

4. struct Node  {

5.           int value; //store the value of Node

6.           int index; // pointer to storing index of the tree

7.           struct Node* leftChild; // pointer to the left Node

8.           struct Node* rightChild; // pointer to the right Child

9. };

10.  

11. struct Node* root; // global variable - pointer for root of the tree

12. int numElements; // global variable - no   of elements in the tree

13.  

14. int add_left_child(Node* parent, int inputValue){

15.           Node*  newLeaf;

16.           if (parent->leftChild == NULL){

17.                     newLeaf = new Node( );

18.                     parent->leftChild = newLeaf;

19.                     newLeaf->value = inputValue;

20.                     return 1;

21.           }

22.           else{

23.                     return -1;

24.           }

25. }

26.  

27. int add_right_child ( Node* parent , int inputValue ){

28.           Node* newLeaf;

29.           if ( parent->rightChild == NULL ){

30.                     newLeaf = new Node( );

31.                     parent->rightChild = newLeaf;

32.                     newLeaf->value = inputValue;

33.                     return 1;

34.           }

35.           else{

36.                     return -1;

37.           }

38. }

39.  

40. struct Node* create_Tree( int inputArray[ ] , int index , int arraySize ) {

41.           numElements = arraySize; // store the number of elements in the array

42.           root = new Node ( ) ;

43.           root->value = inputArray [ index ] ;

44.           root->index = index;

45.           //if left child node excised the index of array return null, thats leaf

46.           if ( ( 2 * index + 1 ) >= arraySize ) {

47.                     return root;

48.           }

49.           //adding left child node

50.           if ( add_left_child ( root , inputArray[2 * index + 1] ) ) {

51.                     root->leftChild = create_Tree( inputArray , ( 2 * index + 1 ) ,  arraySize ) ;

52.           }

53.           //if right child node excised the inex of array return null, thats leaf

54.           if ((2 * index + 2 ) >=  arraySize ){

55.                     return root;

56.           }

57.           // adding right child node

58.           if (add_right_child(root, inputArray [2 * index + 2 ] ) ) {

59.                     root->rightChild = create_Tree ( inputArray ,   ( 2 * index + 2 ) ,  arraySize ) ;

60.           }

61.           return root; // return the sub tree node pointer

62. }

63.  

64. // pre- order traversal : *Node *Left sub Tree *Right sub Tree

65. void traverse_preorder(Node* root){

66.           if ( root )

67.           {          printf ( root->value + " " ) ;

68.                     traverse_preorder ( root->leftChild ) ;

69.                     traverse_preorder ( root->rightChild ) ;

70.           }

71. }

72.  

73. //post order Traversal : *Left sub Tree * Right sub Tree * Node

74. void traverse_postorder ( Node* root ) {

75.           if ( root )

76.           {          traverse_postorder( root->leftChild ) ;

77.                     traverse_postorder( root->rightChild ) ;

78.                     printf ( root->value + " " ) ;

79.           }

80. }

81. //  In-order Travesal : *Left sub Tree *Node  *Right sub Tree

82. void traverse_inorder( Node* root ){

83.           if ( root ){

84.                     traverse_inorder ( root->leftChild ) ;

85.                     printf ( root->value + " " ) ;

86.                     traverse_inorder ( root-> rightChild ) ;

87.           }

88. }

89. // to expand methord

90. void get_inputOrder ( Node* root ,  int inputs[ ] ) {

91.           if ( root )

92.           {          inputs [ root->index ] = root->value;

93.                     get_inputOrder ( root->leftChild , inputs ) ;

94.                     get_inputOrder( root->rightChild , inputs ) ;

95.           }

96. }

97.  

98. Node* expand_Tree(Node* root , int elements[ ] , int ArraySize ){

99.           int allElements = numElements + ArraySize;

100.           int NewArray[12]; //  int allElement should be the array size   but in V  S   it consider as not constant value   therefore i had to set it manually

101.           get_inputOrder(root, NewArray); // get all the elements in the Tree and put in to array

102.           int j = 0;

103.           for (int i = 8; i < allElements; i++){

104.                     NewArray [ i ] = elements [ j ];

105.                     j++;

106.           }

107.           return create_Tree(NewArray, 0, allElements); // all elemtment put in to the one new aray and create new tree and return the root

108. }

109.  

110. int main( ) {

111.           printf( "Create tree [1,45,23,33,25,53,54,11] \n");

112.           int array [ 8 ] = { 1, 45, 23, 33, 25, 53, 54, 11 };

113.           Node* Root = create_Tree(array, 0, 8);

114.           printf ( " InOrderTraversal of Tree : \n ");

115.           traverse_inorder ( Root ) ;

116.           printf( "  \n " ) ;

117.           printf(" pre- order traversal : \n " );

118.           traverse_preorder(Root);

119.           printf( "\n");

120.           printf("post order Traversal :\n");

121.           traverse_postorder(Root);

122.           printf("\n");

123.           printf("\n \n" );

124.           printf("Expand the same tree [3,22,7,64]  \n  ");

125.           int expand[] = { 3, 22, 7, 64 };

126.           Root = expand_Tree(Root, expand, 4);

127.           printf( "InOrderTraversal of Tree :\n ");

128.           traverse_inorder(Root);

129.           printf( "\n" );

130.           printf("pre- order traversal : \n" );

131.           traverse_preorder(Root);

132.           printf("\n" );

133.           printf( "post order Traversal :\n" );

134.           traverse_postorder(Root);

135.           printf( "\n" );

1. }