Solved

Building Binary Trees

Posted on 2000-05-09
8
418 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
Comprehensive Backup Solutions for Microsoft

Acronis protects the complete Microsoft technology stack: Windows Server, Windows PC, laptop and Surface data; Microsoft business applications; Microsoft Hyper-V; Azure VMs; Microsoft Windows Server 2016; Microsoft Exchange 2016 and SQL Server 2016.

 
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: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

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

Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
The viewer will learn how to successfully create a multiboot device using the SARDU utility on Windows 7. Start the SARDU utility: Change the image directory to wherever you store your ISOs, this will prevent you from having 2 copies of an ISO wit…

829 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