Microsoft coding(已知先序和中序序列,求树).

Microsoft | Coding
from CareerCup by sarthak
Given a preorder and inorder traversal of a binary tree, can you reproduce the tree? if yes, then write a function using C/C++ that builds the tree and returns the root node of the tree.

 

#include < stdio.h>
#include 
<iostream>
#include 
<stack>
#include 
<Windows.h>
#include 
<string>

using namespace std;
#define CHECK(x) {if(!(x)){printf("Fatal error: " #x);exit(0);}}
void Trace(char* szFormat,)
{
 va_list l;
 
char s[500];

 va_start(l,szFormat);
 vsprintf(s,szFormat,l);
 OutputDebugStringA(s);
}


typedef 
class  BiTNode
{
public:
 
char data;
 BiTNode 
*lc,*rc; 
}
*BiTree;

//根据先序和中序创建二叉树
/************************************************************************/
/* Microsoft | Coding
from CareerCup by sarthak
Given a preorder and inorder traversal of a binary tree, can you reproduce the tree? 
if yes, then write a function using C/C++ that builds the tree and returns the root node of the tree.                                                                     
*/

/************************************************************************/
BiTree BiTreeCreate(
string preStr,string inStr)
{
 CHECK(preStr.size() 
==inStr.size() && inStr.size()>0);
 
char c=preStr[0];
 
int pos=inStr.find_first_of(c);
 CHECK(pos
!=-1);
 
 BiTree p
=new BiTNode;
 p
->data=c;
 
 
if(pos==0)
  p
->lc=0;
 
else
 
{
  
string ins1=inStr.substr(0,pos);
  
string pres1=preStr.substr(1,pos);
  Trace(
"ins1:%s ,pres1:%s",ins1.c_str(),pres1.c_str());
  p
->lc=BiTreeCreate(pres1,ins1);
 }

 
 
if(pos==preStr.size()-1)
  p
->rc=0;
 
else
 
{
  
string ins2=inStr.substr(pos+1);
  
string pres2=preStr.substr(1+pos);
  Trace(
"ins2:%s ,pres2:%s",ins2.c_str(),pres2.c_str());
  p
->rc=BiTreeCreate(pres2,ins2);
 }

 
return p;
}


void TraverseInOrder2(BiTree T)
{
 
if(T)
 
{
  TraverseInOrder2(T
->lc);
  cout
<<T->data;
  TraverseInOrder2(T
->rc);
 }

}


//先序遍历
void Traverse1Order(BiTree T)
{
 
if(T)
 
{
  cout
<<T->data;
  Traverse1Order(T
->lc);
  Traverse1Order(T
->rc);
 }

}


void Test()
{
 BiTree tree
=BiTreeCreate("ABDECFG","DBEAFCG");
 cout
<<"preOrder:"<<endl;
 Traverse1Order(tree);
 cout
<<endl<<"inOrder:"<<endl;
 TraverseInOrder2(tree);
 cout
<<endl;
}
 

Powered by Jekyll and Theme by solid

本站总访问量