如何非递归解决二叉树重构
void Rebuild(char *pre,char *in,int len,node &*root);
已知中序遍历和前序遍历的结果，重构二叉树
用非递归实现
[解决办法]
非递归代码：
#include "stdafx.h"
#include <stack>
#include <conio.h>
using namespace std;
struct BTreeNode{
int value;
BTreeNode *left,*right;
BTreeNode(int val,BTreeNode *top=NULL){
left=right=NULL;
value=val;
printf("create node %d\n",val);
}
void print(){
printf("%d",value);
}
};
int findIndex(int val,int arr[],int count){
for(int i =0;i< count;++i){
if(arr[i]==val)
return i;
}
return -1;
}
/*
return: the offset of val and curVal in arr
*/
int getOffset(int val,int arr[],int count,int curVal){
int idx = findIndex(val,arr,count);
int idxCur = findIndex(curVal,arr,curVal);
int offset=idx-idxCur;
return offset;
}
/**
已知中序遍历和前序遍历的结果，重构二叉树
用非递归实现
foreSearch：前序遍历结果
midSearch：中序遍历结果
count：个数
*/
BTreeNode* reConstructBTree(int foreSearch[],int midSearch[],int count){
BTreeNode* root = NULL;
BTreeNode* last=NULL;
BTreeNode* cur;
stack<BTreeNode*> mystack;
stack<int> curIndexStack;
int forindex=0;
int curIndex=0;
if(count < 1)
return root;
cur = root=new BTreeNode(foreSearch[forindex++]);
mystack.push(cur);
curIndexStack.push(forindex);
while((cur!=NULL||!mystack.empty())&&forindex<count){
int offset = getOffset(foreSearch[forindex],midSearch,count,foreSearch[curIndex]);
if(cur==NULL){
cur=mystack.top();
mystack.pop();
curIndex=curIndexStack.top();
curIndexStack.pop();
}
if(offset<0 && curIndex+1==forindex){//left child
BTreeNode* tmp = new BTreeNode(foreSearch[forindex++],cur);
cur->left = tmp;
mystack.push(cur);
cur=tmp;curIndex=forindex-1;
curIndexStack.push(curIndex);
}else if(offset>0){ //possible right child
if(!mystack.empty()){
if(mystack.top()->value<foreSearch[forindex]){//no,maybe parent's child
cur = NULL;
continue;
}
}
BTreeNode* tmp = new BTreeNode(foreSearch[forindex++],cur);
cur->right = tmp;
cur=tmp;
mystack.push(cur);
cur=tmp;curIndex=forindex-1;
curIndexStack.push(curIndex);
}else{
printf("unexpected error");
return NULL;
}
}
return root;
}
