How to convert an array representation of Binary tree into actual Bina

How to convert an array representation of Binary tree into actual Bina

Page 1 of 1

3 Replies - 7193 Views - Last Post: 11 November 2009 - 05:30 AM Rate Topic: -----

#1 Pandurang  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 04-October 09

How to convert an array representation of Binary tree into actual Bina

Post icon  Posted 10 November 2009 - 08:08 AM

I am having one array representation of binary tree.
I need to tell whether its Binary Search Tree or not.
I am trying to first convert an array into binary tree, which can be checked quickly.
I have written following code.
I am sure , i am messing up with the insert part of it.
Can someone please help me out here.
Below is my code.
First element in array is the number of elements.Blank spaces in the array are indicated by -1.

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define true 1
#define false 0
struct node {
  int data, pos;
  struct node* left;
  struct node* right;
}; 


struct node* NewNode(int data, int pos) {
  struct node* node = malloc(sizeof(struct node)); 
  node->data = data;
  node->pos = pos;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

struct node* insert(struct node* node,int data, int pos) 
{
  if (node == NULL) {
	return(NewNode(data, pos));
  }

	if(node->left == NULL && pos%2==0)
		node->left=insert(node->left,data, pos);
	else
		node->right=insert(node->right,data, pos);

  return(node); // return the (unchanged) node pointer
} 


void printTree(struct node* node) {
  if (node == NULL) return;

  printTree(node->left);
  printf("%d ", node->data);
  printTree(node->right);
}

int minValue(struct node* node) {
  struct node* current = node;

  // loop down to find the leftmost leaf
  while (current->left != NULL) {
	current = current->left;
  }

  return(current->data);
} 


int maxValue(struct node* node) {
  struct node* current = node;
  while (current->left != NULL) {
	current = current->right;
  }
  return(current->data);
} 


int isBST(struct node* node) {
  if (node==NULL) return(true);

  if (node->left!=NULL && maxValue(node->left) > node->data)
	return(false);

  // false if the min of the right is <= than us
  if (node->right!=NULL && minValue(node->right) <= node->data)
	return(false);

  // false if, recursively, the left or right is not a BST
  if (!isBST(node->left) || !isBST(node->right))
	return(false);

  // passing all that, it's a BST
  return(true);
} 

int main()
{
  struct node* N1=malloc(sizeof(struct node));
  int i;
  int arr[]={14,17,12,25,9,15,21,29,-1,11,-1,-1,19,-1,27};
  N1 = NULL;
  for(i=1;i<=arr[0];i++)
	{
	  N1 = insert(N1,arr[i],i);
	}
  printTree(N1);
  printf("\nisBST = %d\n",isBST(N1) );
}
  



Is This A Good Question/Topic? 0
  • +

Replies To: How to convert an array representation of Binary tree into actual Bina

#2 Pandurang  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 04-October 09

Re: How to convert an array representation of Binary tree into actual Bina

Posted 10 November 2009 - 08:22 AM

Please note that I am not trying to build a BST but just a binary tree from array( breadth first )
Was This Post Helpful? 0
  • +
  • -

#3 Pandurang  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 04-October 09

Re: How to convert an array representation of Binary tree into actual Bina

Posted 10 November 2009 - 07:00 PM

Any expert to help me out here....!
Was This Post Helpful? 0
  • +
  • -

#4 Pandurang  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 04-October 09

Re: How to convert an array representation of Binary tree into actual Bina

Posted 11 November 2009 - 05:30 AM

Finally solved the problem, but not using linked list....!
Used the same IsBST logic but on an array....!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1