Program Discussion :: Trees
42 / 17
Write a program to sort the elements of the tree
Answer:
#include
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
/* A utility function to create a new BST Node*/
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* Stores inoder traversal of the BST*/
/* in arr[]*/
void storeSorted(Node *root, int arr[], int &i)
{
if (root != NULL)
{
storeSorted(root->left, arr, i);
arr[i++] = root->key;
storeSorted(root->right, arr, i);
}
}
/* A utility function to insert a new
Node with given key in BST */
Node* insert(Node* node, int key)
{
/* If the tree is empty, return a new Node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) Node pointer */
return node;
}
/* This function sorts arr[0..n-1] using Tree Sort
void treeSort(int arr[], int n)
{
struct Node *root = NULL;
/* Construct the BST
root = insert(root, arr[0]);
for (int i=1; i
Asked In ::
Language:
Atul
7 Jul, 2017 9:30 AM
#include <stdio.h>
#include <conio.h>
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;
void insert ( struct btreenode **, int ) ;
void inorder ( struct btreenode * ) ;
int main( )
{
struct btreenode *bt ;
int arr[20], arr1[20];
int i, num, j ;
bt = NULL ; //initialize the node
printf("******** Binary tree sort Algorithm by Ccodechamp ***********\n" ) ;
printf("\n");
printf("\nEnter the number of elements in the list : ");
scanf("%d",&num);
printf("\nEnter the elements to be sorted: \n");
for(i=0;i < num;i++)
{
scanf("%d",&arr[i]);
arr1[i]=arr[i];
}
printf ( "\nDisplay Array contents:\n" ) ;
for ( i = 0 ; i < num ; i++ )
printf ( "%d\t", arr[i] ) ;
for ( j = 0 ; j < num ; j++ )
insert ( &bt, arr1[j] ) ;
printf ( "\nIn-order traversal of binary tree:\n" ) ;
inorder ( bt ) ;
getch( ) ;
}
void insert ( struct btreenode **sr, int num1 )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num1 ;
( *sr ) -> rightchild = NULL ;
}
else
{
if ( num1 < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num1 ) ;
else
insert ( &( ( *sr ) -> rightchild ), num1 ) ;
}
}
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
Language:
Neel
7 Jul, 2017 9:30 AM
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *left, *right;
};
/* A utility function to create a new BST Node*/
struct Node *newNode(int item)
{
struct Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
/* Stores inoder traversal of the BST*/
/* in arr[]*/
void storeSorted(Node *root, int arr[], int &i)
{
if (root != NULL)
{
storeSorted(root->left, arr, i);
arr[i++] = root->key;
storeSorted(root->right, arr, i);
}
}
/* A utility function to insert a new
Node with given key in BST */
Node* insert(Node* node, int key)
{
/* If the tree is empty, return a new Node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) Node pointer */
return node;
}
/* This function sorts arr[0..n-1] using Tree Sort
void treeSort(int arr[], int n)
{
struct Node *root = NULL;
/* Construct the BST
root = insert(root, arr[0]);
for (int i=1; i<n; i++)
insert(root, arr[i]);
/* Store inoder traversal of the BST
/* in arr[]
int i = 0;
storeSorted(root, arr, i);
}
/* Driver Program to test above functions
int main()
{
/*create input array*/
int arr[] = {5, 4, 7, 2, 11};
int n = sizeof(arr)/sizeof(arr[0]);
treeSort(arr, n);
cout << "Sorted Array : ";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}