Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Building Binary Trees

Posted on 2000-05-09
8
Medium Priority
?
443 Views
Last Modified: 2013-11-15
Given the preorder and inorder traversal of a binary tree of N nodes, what is the code to create the binary tree?  (pointer-based please)
0
Comment
Question by:mkszeto
  • 5
  • 2
8 Comments
 
LVL 1

Expert Comment

by:BSoeters
ID: 2794129
You'll need to have more to go on.

If you ask this question like this, you'd be getting trees of which only the left branches are filled.

A tree can have many forms, while the preorder and inorder traversals still stay the same.
0
 
LVL 1

Expert Comment

by:yz
ID: 2795894
no, if u give any two of the three order of a tree, this tree is unique, and there is a standard recursion method to make the whole tree from these two order.
0
 
LVL 1

Accepted Solution

by:
yz earned 100 total points
ID: 2796053
I made a simple program to make a binrary tree from its preoder and inorder traversal, pls check it.
(I use vc6)

#include <stdio.h>
#include <Stdlib.h>

typedef struct node
      {
      int value;
      struct node * left, * right;
      } Node, * PNode;

char PreOrder[] = "ABDEGCFHI";                        // 9 nodes tree
char InOrder[]  = "DBGEACHFI";
int scan = 0;
PNode head;

int find(int from, int to, char ch)
      {
      int i;

      for (i=from;i<=to;i++)
            if (InOrder[i]==ch)
                  return i;

      return -1;
      }

void step(int left, int root, int right, PNode * parent)
      {
      int pos;
      PNode p = new Node;

      p->value = InOrder[root]; p->left = p->right = NULL;
      * parent = p;

      if (0 != left)
            {
            pos = find(root - left, root - 1, PreOrder[scan]);
            if (-1 == pos)
                  {
                  printf("Input error");
                  exit(-1);
                  }
            else
                  {
                  scan ++;
                  step(left - (root - pos), pos, root - pos - 1, &(p->left));
                  }
            }

      if (0 != right)
            {
            pos = find(root + 1, root + right, PreOrder[scan]);
            if (-1 == pos)
                  {
                  printf("Input error");
                  exit(-1);
                  }
            else
                  {
                  scan ++;
                  step(pos - root - 1, pos, right - (pos - root), &(p->right));
                  }
            }
      }


void main()
      {
      int pos;

      pos = find(0, 8, PreOrder[scan]);
      scan ++;
      step(pos , pos, 8 - pos, &head);
      }
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 1

Expert Comment

by:yz
ID: 2796061
The tree is ((DB(GE-))A(-C(HFI)))
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 2796119
yz, This is a C++ question, why not try some C++ code.
0
 
LVL 1

Expert Comment

by:yz
ID: 2798477
which code can be called C++ code? use class ? use iostream ? can u tell me? I feel some confused.
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 2799325
It was just that the program you presented is pure C. A class or two would be  nice.
0
 
LVL 1

Expert Comment

by:yz
ID: 2820682
? why give me a C ? does my code goes something wrong ? Please tell me and let me to gain progress.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When you discover the power of the R programming language, you are going to wonder how you ever lived without it! Learn why the language merits a place in your programming arsenal.
There are literally thousands of Exchange recovery applications out there. So how do you end up picking one that’s ideal for your business & purpose? By carefully scouting the product’s features, the benefits it offers you, & reading ample reviews f…
The viewer will learn how to successfully download and install the SARDU utility on Windows 8, without downloading adware.
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…

571 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question