?
Solved

Building Binary Trees

Posted on 2000-05-09
8
Medium Priority
?
435 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Moving data to the cloud? Find out if you’re ready

Before moving to the cloud, it is important to carefully define your db needs, plan for the migration & understand prod. environment. This wp explains how to define what you need from a cloud provider, plan for the migration & what putting a cloud solution into practice entails.

 
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

Simplifying Server Workload Migrations

This use case outlines the migration challenges that organizations face and how the Acronis AnyData Engine supports physical-to-physical (P2P), physical-to-virtual (P2V), virtual to physical (V2P), and cross-virtual (V2V) migration scenarios to address these challenges.

Question has a verified solution.

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

In this article, you will read about the trends across the human resources departments for the upcoming year. Some of them include improving employee experience, adopting new technologies, using HR software to its full extent, and integrating artifi…
All of the resources available today make learning a new digital media easier than ever-- if you know where to begin. This is a clear, simple guide to a few of the basic digital art mediums and how to begin learning them on your own.
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
An overview on how to enroll an hourly employee into the employee database and how to give them access into the clock in terminal.

771 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