construct a tree from in-order and pre-order traversal

my code

    public TreeNode constructTree( TreeNode[] inOrderSeq, TreeNode[] preOrderSeq )
    {
        if( inOrderSeq == null || inOrderSeq.length == 0 )
        {
            return null;
        }
        if( preOrderSeq == null || preOrderSeq.length == 0 )
        {
            return null;
        }
        // for pre-order( root->left-right), the first element would be the root of the tree   
        TreeNode root = preOrderSeq[0];
        // find the root index in the in-order sequence   
        // all the elements left to this index would be left substree,
        // and the right part would be the right substree
        int rootIndexForInorder = Array.binarySearch( inOrderSeq, root );
        TreeNode[] leftSubInorder = new TreeNode[rootIndexForInorder-1];
        System.arraycopy( inOrderSeq,0, lefSub, 0, rootIndexForInorder-1 );
        TreeNode[] rightSubInorder = new TreeNode[inOrderSeq.length - rootIndexForInorder );

        // after got left subtree and right subtree in inorder sequence, we need to get countpart
        // in pre-order sequence
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for( int i = 0; i < leftSubInorder.length; i++ )
        {
            int pos = Array.binarySearch( preOrderSeq, leftSubInorder[i] );
            if( pos < min )
            {
                min = pos;
            }
            else if( pos > max )
            {
                max = pos;
            }
        }

        TreeNode[] leftSubPreOrder = new TreeNode[max-min+1];
        System.arraycopy( preOrderSeq, min, leftSubPreOrder, max - min + 1 );
        TreeNode[] rightSubPreOrder = new TreeNode[preOrderSeq.length - max];
        System.arraycopy( preOrderSeq, max+1 rightSubPreOrder, 0, preOrderSeq.length - max];   

        root.lChild = constructTree( leftSubInorder, leftSubPreOrder );
        root.rChild = constructTree( rightSubInorder, rightSubPreOrder );

        return root;
    }

see another one:

struct node
{
  char data;
  struct node *left;
  struct node *right;
};
int search(char in[],int inStrt, int inEnd, char data);
struct node *buildTree(char in[], char pre[], int inStrt, int inEnd);
struct node* newNode(char data);

int search(char arr[], int inStrt, int inEnd, char data)
{
  int i;
  for(i = inStrt; i <= inEnd; i++)
  {
     if(arr[i] == data)
     {
        return i;
     }
  }
}

struct node *buildTree(char in[], char pre[], int inStrt, int inEnd)
{
  static int preIndex = 0;
  if(inStrt > inEnd)
     return NULL;
  // pick the current node from pre-order traversal
  struct node *tNode = newNode(pre[preIndex++]);
  // if this node has no childern then return
  if(inStrt == inEnd)
     return tNode;
  // find the index of this node in inorder traversal
  int inIndex = search(in, inStrt, inEnd, tNode->data);
  tNode->left = buildTree(in, pre, inStrt, inIndex -1);
  tNode->right = buildTree(in, pre, inIndex + 1, inEnd);
  return tNode;
}

struct node* newNode(char data)
{
  struct node *node = (struct node *)malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  return node;
}

void printInorder(struct node *root)
{
  if(root == NULL)
    return;
  printInorder(root->left);
  printf(" %c ", root->data);
  printInorder(root->right);
}

main()
{
  char in[] = {'C', 'B', 'F', 'D', 'G', 'A', 'E'};
  char pre[] = {'A', 'B', 'C', 'D', 'F', 'G', 'E'};
  int len = sizeof(in)/sizeof(in[0]);
  struct node *root = buildTree(in, pre, 0, len-1);
  printInorder(root);
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s