Solved

Building Binary Trees

Posted on 2000-05-09
8
409 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 50 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
 
LVL 1

Expert Comment

by:yz
ID: 2796061
The tree is ((DB(GE-))A(-C(HFI)))
0
U.S. Department of Agriculture and Acronis Access

With the new era of mobile computing, smartphones and tablets, wireless communications and cloud services, the USDA sought to take advantage of a mobilized workforce and the blurring lines between personal and corporate computing resources.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

The article will include the best Data Recovery Tools along with their Features, Capabilities, and their Download Links. Hope you’ll enjoy it and will choose the one as required by you.
This guide will walk you through the essential considerations and tech stack for building scalable websites. Know how to grow your business the smart way!
This video will demonstrate how to find the puppet warp tool from the edit menu and where to put the points to edit.
Using Adobe Premiere Pro, the viewer will learn how to set up a sequence with proper settings, importing pictures, rendering, and exporting the finished product.

932 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now