Solved

Building Binary Trees

Posted on 2000-05-09
8
422 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
Enterprise Mobility and BYOD For Dummies

Like “For Dummies” books, you can read this in whatever order you choose and learn about mobility and BYOD; and how to put a competitive mobile infrastructure in place. Developed for SMBs and large enterprises alike, you will find helpful use cases, planning, and implementation.

 
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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

This article describes how to use the timestamp of existing data in a database to allow Tableau to calculate the prior work day instead of relying on case statements or if statements to calculate the days of the week.
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!
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

726 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