Binary Search Tree Construction Help

[ahmed]

Can anyone please help me out on how to construct a tree from its traversals? i know that we see inorder and preorder traversal but i don't know how to

[WingedPanther]

Can you offer some sample data to illustrate the process with?

[ahmed]

pre order = A B C D E F G H I J K L M
in order = C E D F B A H J I K G M L

these are the pre order and in order traversal of the tree which i want to construct

[WingedPanther]

In order represents the order of the letters in the tree when scanned left-to-right, ignoring height in the tree.

pre-order gives you their position in height. So A, for example, is the root, and B is the left child of A.

So, preorder tells you that A is the root. in order tells you that C, E, D, F, and B are all on the left branch of A.

Tree traversal - Wikipedia, the free encyclopedia

[alienkinetics]

This is giving me a headache. An "inorder" (left, root, right) traversal is ment to give a sorted result. So, "C E D F B A H J I K G M L" either isn't inorder or the tree isn't sorted, so you cant work out the tree from this.

If "C E D F B A H J I K G M L" is preorder (root, left, right), then I get:

        H
   A         J
    B       I K
     C         G
      E       M
     D F     L

But, then a preorder traversal prints something else (?) Anyway, here is some code. use it as you will

Tree traversal - Wikipedia, the free encyclopedia

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node
{
  char c;
  struct Node* lt;
  struct Node* rt;
} Node;

Node* groot;

Node* NodeCreate(char c) {
  Node* node = calloc(1, sizeof(Node));
  node->c = c;
  return node;
}

Node** NodeFind(Node** node, char c) {
  return *node ? c < (*node)->c ?
    NodeFind(&(*node)->lt, c) :
    NodeFind(&(*node)->rt, c) : node;
}

Node* NodeAdd(char c) {
  return *NodeFind(&groot, c) = NodeCreate(c);
}

void NodeOrderPre(Node* node) {
  if (!node) return;
  printf("%c", node->c);
  NodeOrderPre(node->lt);
  NodeOrderPre(node->rt);
}

void NodeOrderIn(Node* node) {
  if (!node) return;
  NodeOrderIn(node->lt);
  printf("%c", node->c);
  NodeOrderIn(node->rt);
}

void NodeOrderPost(Node* node) {
  if (!node) return;
  NodeOrderPost(node->lt);
  NodeOrderPost(node->rt);
  printf("%c", node->c);
}

int main(int argc, char* argv[])
{
  char s[100], *p = "gmbdlahkfcjie";
  while (*p) NodeAdd(*p++);
  printf("preorder: "); NodeOrderPre(groot); puts("");
  printf("inorder : "); NodeOrderIn (groot); puts("");
  gets(s);
  return 0;
}

[ahmed]

thanks a lot i got it how we do it

[vanexa7]

hi i have a problem similar to this but in my case i have the inorder and postorder, i'm doing it in java but if you tell me what i need to change in my case i think probably i can adapt it to java...

[alienkinetics]

I did include a NodeOrderPost() function with the ANSIC code which is based on Wikipedia's definition.

I dont think the code will convert to Java because it relies on a language to have "pass by reference", so the code would have to be rewritten.