二叉树前序中序恢复

typedef struct BTreeNode{

int data; //默认是int内容

struct BTreeNode * lchild;

struct BTreeNode * rchild;

}BTreeNode;

int searchInmid( int * mid ,int data, int start,int end)

{

//查找数据返回

for(int i = start, i

{

if(mid[i]==pre[i])

return i;

}

}

//curBit应该为静态或者改为zhizhen

BTreeNode * generationTree(int * pre, int preLen,int & curBit, int * mid, int start,int end  )

{

BTreeNode * newNode = NULL; 

if(preLen-1 == curBit)

return NULL;

newNode = malloc(sizeof(BTreeNode));

newNode->data = pre[curBit];

newNode ->lchild =newNode->rchild =NULL;

if(start == end)

return newNode;

int index = searchInmid(mid, pre[curBit],start, end);

newNode->lchild = generationTree(pre,preLen,++curBit,mid,start, --index);

newNode->rchild = generationTree(pre,preLen,++curBit,mid,++index,end);

return BTreeNode;

}

BTreeNode * genFun(int * pre, int len, int * mid)

{

BTreeNode * root =NULL;

int parentIndex = 0;

BTreeNode * parent = NULL;

stack tmp;

if(len == 0)

return root;

root = malloc(sizeof(BTreeNode ));

parent=root;

if(len ==1 )

{

return root;

}

start = 0;

end = len -1;

tmp.push(parent);

start.push(start);

end.push(end);

parentIndex = searchInmid(pre[0],start,end);

for(int i=0; i

{

newNode = malloc(sizeof(BTreeNode));

newNode->data = pre[i];

curIndex = searchInmid(pre[i],start,end);

if (curIndex < parentIndex)

{

parent->lchild = newNode;

end = curIndex-1;

}else{

parent->rchild = newNode;

start = curIndex +1;

}

if(curIndex > start){

//左子树；

tmp.push(newNode);

start.push(start);

end.push(end);

}

if (curIndex != start )

{

parent=newNode;

parentIndex = curIndex;

}

while (curIndex == start)

{

end = tmp.pop();

start = start.pop();

parent = end.pop();

parentIndex = searchInmid(parent->data,start,end);

}

}

return root;

}

阅读(951) | 评论(0) | 转发(0) |

0

上一篇：C++ 多线程编程总结

下一篇：快速排序的递归与非递归算法实现