Binary tree construct

[lamx]

construct a binary tree from in-order and pre-order and i need to printout the level-order
the first string is pre-order and the second one is in-order

n(1<=n<=25)
the length of string (1<=L<=10)


Input Example
2 (this is n)
DBACEGF ABCDEFG
ABDFHCGI DBHFACIG
Output Example
DBEACGF
ABCDFGHI

Can you guys help me with the code?
It's very important to me
I was suffered to this problem for 3 days
thanks for your helping!

[Duthomhas]

Terminology is important, and it actually makes sense when you know what it means. A binary tree is composed of nodes. Each node has:

 • a value
 • a left child
 • a right child

The “some-order” phrase talks about the way we draw or display each node’s value with respect to the position of the node’s children. So:

  In-order means we show left, value, right.
  Pre-order means we show value, left, right.
  Post-order means we show left, right, value.

In all cases, the child nodes are always listed in left, right order.

Level-order has nothing to do with parent-child relationships.
It is just a right-to-left listing of nodes in each level.

────────────────────

So you are given two representations and asked to reconstruct the tree that generated them.

  pre-order: DBACEGF
  in-order:  ABCDEFG

So lets break those down. In the pre-order, we know that the root node comes first. Let’s split it out:

  pre-order: D BACEGF
  in-order:  ABCDEFG

Conveniently, this also allows us to find it in the in-order representation. Let’s split it out there too:

  pre-order: D BACEGF
  in-order:  ABC D EFG

Great! This shows us the left side of the tree contains node ABC and the right side contains FEG. Let’s update our pre-order spacing too:

  pre-order: D BAC EGF
  in-order:  ABC D EFG

Our tree, currently:

        D
      /   \
   ABC     EFG

The left sub-tree follows the same process:

  pre-order: BAC  →   B AC      B AC   →   B A C
  in-order:  ABC      ABC   →   A B C      A B C

Our tree, currently:

        D
      /   \
    B      EFG  
   / \
  A   C   

The right sub-tree (of D) also follows the same process:

  pre-order: EGF   →   E GF       E GF
  in-order:  EFG       EFG    →   E FG    *what?

So, we notice that E is first in both pre-order and in-order representations.
That is because E does not have a left child.
Our tree, currently:

        D
      /   \
    B      E  
   / \      \
  A   C      FG

The right sub-tree of E again follows the same process:

  pre-order: GF  →   G F      G F
  in-order:  FG      FG   →   F G

This time it is G that has no right-child node. Our final tree representation is:

        D
      /   \
    B       E  
   / \        \
  A   C         G
               /
              F

At this point we perform a BFS and just print out each line of node names, left-to-right:

1 2 3 4 5 6 7

D / \ B E / \ \ A C G / F

D BE ACG F

  D BE ACG F     →     DBEACGF

Things we have observed
The first is that we can always distinguish between left and right children by comparing the pre-order and in-order lists.

The next is that we can phrase the problem recursively. Every node is split into a left and a right. We know the node value from the pre-order. All we need to do is find it in the in-order, and then we have found the left and right halves of the tree in the pre-order list too.

────────────────────

Well, that is most of the battle. Use this knowledge to build your tree so that you can print it with a BFS. (Both the building and the printing are recursive problems!)

(Once you have that working, you might want to consider that it is possible to do this without actually building a tree. DO IT BY BUILDING THE TREE FIRST.)

Post back with code and we will help you through it.

[lamx]

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<cstring>
#include<cctype>
#include<cstdio>
int n;
char inorder[10],preorder[10];
int checkpt;
using namespace std;
struct node
{
char data{1000};
struct node* left;
struct node* right;
};


int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;

if(inStrt > inEnd)
return 0;

struct node *tNode = newNode(pre[preIndex++]);


if(inStrt == inEnd)
return tNode;


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;
}

int search(char arr[], int strt, int end, char value)
{
int i;
for(i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}

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

return(node);
}

void printLevelOrder( node* root)
{
queue<node*>q;
q.push(root);
while(!q.empty())
{
node* node = q.front();
q.pop();
cout<< node->data;
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);

}
cout<<endl;
}

int main()
{
node x ;

cin >> n;
for(int i=0; i<n ; i++)
{
cin >>preorder >>inorder ;

int len = sizeof(inorder)/sizeof(inorder[0]);
struct node *root = buildTree(inorder, preorder, 0, len - 1);
printLevelOrder(root);
getchar();
memset(&x ,0,sizeof(x));
}

}

my code is here but someting go wrong
i can't output two answer
can you tell me what the problem is ?
when i input the second one in it output as something i can't read
pls reply me asap thank you~

[Duthomhas]

Most of your problems are syntax errors. I copied your code to dink with it, but you are stuck with an awkward mix of C and C++. You should pick a language and stick to it.

(Most of what you wrote is C.)

Here is your code cleaned up a lot:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<cstring>
#include<cctype>
#include<cstdio>

int n;                          // you should move these to main()
char inorder[10],preorder[10];  // you should move these to main()
//int checkpt;                                          // not used
using namespace std;

struct node
{
  char data; //char data {1000};                        // 1000 does not fit in a char, range [0..127]
  struct node* left;                                    // see commentary on 'struct' below
  struct node* right;
};


int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd, /*yes:*/ int preIndex = 0)
{
  //static int preIndex = 0;                            // :no -- this should also be an argument!

  if(inStrt > inEnd)
    return 0;

  struct node *tNode = newNode(pre[preIndex++]);


  if(inStrt == inEnd)
    return tNode;


  int inIndex = search(in, inStrt, inEnd, tNode->data);
  // you should be checking for search failure here: if (inIndex == inEnd), 
  // otherwise you are playing with UNDEFINED BEHAVIOR!

  tNode->left = buildTree(in, pre, inStrt, inIndex-1, /*yes:*/ /*preIndex   */);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd, /*yes:*/ /*preIndex+? */);

  return tNode;
}

int search(char arr[], int strt, int end, char value)
{
  int i;
  for(i = strt; i <= end; i++)
  {
    if(arr[i] == value)
      return i;
  }
  return end;                                           // Don't forget! See notes on compiler warnings below.
}

struct node* newNode(char data)                         // Very nice!
{
  struct node* node = (struct node*) malloc(sizeof(struct node));
  node->data = data;
  node->left = nullptr;  //0;                           // ...or NULL, use the proper construct for the type
  node->right = nullptr; //0;                           // in this case, you are assigning a null pointer

  return(node);
}

void deleteNode( struct node* tNode )                   // Fill me in!
{
  // TODO!
}

void printLevelOrder( node* root)                       // Very nice
{
  queue<node*>q;
  q.push(root);
  while(!q.empty())
  {
    node* node = q.front();
    q.pop();
    cout<< node->data;
    if(node->left) q.push(node->left);
    if(node->right) q.push(node->right);

  }
  cout<<endl;
}

int main()
{
//  node x ;                                            // not used

  cin >> n;
  for(int i=0; i<n ; i++)
  {
    cin >>preorder >>inorder ;                          // c-strings in a C++ program?

//    int len = sizeof(inorder)/sizeof(inorder[0]);     // this will get you a 10: size of array in bytes / size of element in bytes
    int len = strlen( inorder );                        // what you really want is the length of the input string
    // (btw, this would be a good spot to check that strlen(inorder) == strlen(preorder).)
    struct node *root = buildTree(inorder, preorder, 0, len - 1);
    printLevelOrder(root);
    getchar();
//    memset(&x ,0,sizeof(x));                          // see commentary on memory management below
    deleteNode( root );                                 // this is how you should do it, again, see commentary below
  }                                                     

}

[Duthomhas]

Global Variables
You should try to avoid them as much as possible.
Global variables come in two forms: those everyone can see and those only one function can see. Here are the global variables found in your program:

int n;
char inorder[10],preorder[10];
int checkpt;

static int preIndex = 0;

The first two really belong to main(). It is where they first gain value and last have it.
The last one is, yes, also a form of global variable with restricted visibility. In this case, it is a crutch for maintaining state between function calls. Make it an argument instead.

Struct in C and C++
In C, a structure type name gets its own section in the compiler’s symbol table. In order to use it, you must signal to the compiler that you want a ‘struct’ name and not a normal type name by using the keyword struct.

In C++, that still happens, but the name is added to both symbol tables. So you no longer need to type “struct” before a structure type name.

Compiler warnings
A lot of these errors would be caught if you crank up your compiler’s warning level to maximum. It may seem opprobrious at first, but it really does help you to find and repair errors in your code.

Google around your IDE+compiler combination for increasing the warning level.

C-string vs std::string
In C, strings are just arrays of characters. To find the declared (that is, actual amount of memory taken up by the array), use the sizeof operator.

That is not what you want, though. You want the number of characters used in the array. That is what std::strlen() is for.

You have one other potential problem: overflow. Your two arrays can store at maximum only nine characters entered by the user (9 + 1 for the '\0' value at the end of the string = 10 characters of available space).

Using the stream extraction operator on a char* is just as dangerous as using std::gets() — the computer will be happy to add characters to the end of the string as long as there is input, even if it is adding way past the actual space available.

Granted, C++ could have easily fixed this problem, but the die is currently cast...

You should instead use a bounded input function, such as:

  cin.getline( preorder, sizeof(preorder) );
  cin.getline( inorder,  sizeof(inorder) );

(You could also consider making both arrays a bit larger, say 50 elements or so.)

The other option is to just use a std::string:

  string preorder, inorder;
  cin >> preorder >> inorder;

You are guaranteed there will be no bounds/overflow failures. You can then use the data as before, since a std::string is a managed character array:

  node* root = buildTree(inorder.c_str(), preorder.c_str(), 0, inorder.size() - 1);

The only thing you would have to do is change all the char* to const char* — which is fine since buildTree() never attempts to modify the strings.

Dynamic Memory Management
Whenever you create something you must destroy it. That is, for every malloc() there must be a free().

I suspect you were endeavoring to do something with x to free stuff. Don’t do that.

Pointers are special. An no matter what you read anywhere, you really should avoid simply writing zeros across all bytes of a pointer. See, the value of a zero pointer might not actually be zero. So whenever you have to initialize a pointer variable, assign it a nullptr or NULL directly, even in structs.

struct foozle
{
  foozle* next;
  int x;
};

foozle* createFoozle( int x )
{
  foozle* fooz = new foozle;
  fooz->next = nullptr;
  fooz->x = x;
  return fooz;
}

Using memset() or some other thing is technically a no-no, even though so much code on PC systems does it.

Having allocated memory from the dynamic store you must give it up at some point. For a linked tree like yours (or a linked list like foozle), it is entirely likely that left and right (or next) will point to data that also needs to be freed.

This is where you need a procedure to clean up. I have added a function shell to your code which you can fill out to do the cleanup. Remember, it may call itself to free children of the argument node. (Hint hint!)

Overflow and Undefined Behavior
As already mentioned above, attempts to access memory beyond the bounds of an array is not guaranteed to do anything benign. The first potential problem is where you read the input strings. The second is in the indices to your buildTree() algorithm. What you have currently works, but not because it is doing exactly what you think it is.

It might be worth your time to trace through the function for the given input strings. Keep track of where each index points as you follow the code, line-by-line.

You might also check your algorithm against invalid input, like:

  3
  DBACE   ACDEB
  HELLO   WORLD
  Y   AEIOU

It should fail gracefully — return nothing or an error message. (Check your assignment for any instructions regarding invalid input.)


Final thoughts
I hope not to sound rude or condescending — it is clear you have cobbled this together from several sources. (The BFS was clearly not written by you.) I hope you have taken the time to understand what is going on at each step.

The fact that you have gotten so close helps me to believe that you are competently approaching the problem.

Hope this helps.

[lamx]

OK... I GOT IT
THANKS FOR HELPING
i should write it in the same langauage
oh..... it always confuses me .