【面试题6】重建二叉树

二叉树中最重要的操作莫过于遍历，即按照某一顺序访问树中的所有结点。

以下这三种遍历都有递归和循环两种实现方法，每一种遍历的递归都要比循环实现简洁地多。

前序遍历：

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 递归实现：

void PreOrder(BTNode *b) { if(b!=NULL) { printf("%c",b->data);//访问根结点 PreOrder(b->lchild); //递归访问左子树 PreOrder(b->rchild); //递归访问右子树 } }

循环实现：

void PreOrder(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if(b!=NULL) { top++; //根结点入栈 St[top]=b; while(top>-1)(栈不为空时循环） { p=St[top];//退栈并访问该结点 top--; printf("%c",p->data); if(p->rchild!=NULL)//右孩子入栈 { top++; St[top]=p-rchild; } if(p->lchild!=NULL)//左孩子入栈 { top++; St[top]=p-lchild; } } printf("\n"); } }

中序遍历：

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。 递归实现：

void InOrder(BTNode *b) { if(b!=NULL) { InOrder(b->lchild); //递归访问左子树 printf("%c",b->data);//访问根结点 InOrder(b->rchild); //递归访问右子树 } }

循环实现：

void InOrder(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if(b!=NULL) { p=b; while(top>-1||p!=NULL) { while(p!=NULL) { top++; St[top]=p; p=p->lchild; } if(top>-1) { p=St[top]; top--; printf("%c",p->data); p=p->rchild; } } printf("\n"); } }

后序遍历：

后序遍历首先遍历左子树，然后访问右子树，最后遍历根结点。在遍历左，右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。 递归实现：

void PostOrder(BTNode *b) { if(b!=NULL) { PostOrder(b->lchild); //递归访问左子树 PostOrder(b->rchild); //递归访问右子树 printf("%c",b->data);//访问根结点 } }

循环实现：

void PostOrder(BTNode *b) { BTNode *St[MaxSize]; BTNode *p; int flag,top=-1; //栈指针置初值 if(b!=NULL) { do { while(b!=NULL)//将t的所有左结点入栈 { top++; St[top]=b; b=b->child; } p=NULL; //p指向当前结点的前一个已访问结点 flag=1; while(top!=-1&&flag) { b=St[top];//取出当前的栈顶元素 if(b->rchild==p)//右子树不存在或已被访问 { printf("%c",b->data);//访问*b结点 top--; p=b; //p指向被访问结点 } else { b=b->rchild;//b指向右子树 flag=0; } } }while(top!=-1); printf("\n"); }

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。例如：输入前序遍历{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6}。

BinaryTreeNode* Construct(int* preorder,int* inorder,int length) { if(preorder==NULL||inorder==NULL||length<=0) return NULL; return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1); } BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder;int* startInorder,int* endInorder) { //前序遍历序列的第一个数字是根结点的值 int rootValue=startPreorder[0]; BinaryTreeNode* root=new BinaryTreeNode(); root->m_nValue=rootValue; root->m_pLeft=root->m_pRight=NULL: if（startPreorder==endPreorder) { if(startInorder==endInorder && *startPreorder== *startInorder) return root; else throw std::exception("invalid input."); } //中序遍历中找到根结点的值 int* rootInorder=startInorder; while(rootInorder<=endInorder && *rootInorder!=rootValue) ++rootInorder; if(rootInorder==endInorder && *rootInorder!=rootValue) throw std::exception("Invalid input."); int leftLength=rootInorder-startInorder; int* leftPreorderEnd=startPreorder+leftLength; if(leftLength>0) { //构建左子树 root->m_pLeft=ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1); } if(leftLength<endPreorder-startPreorder) { //构建右子树 root->m_pRight=ConstructCore(leftPreorderEnd+1,endPreorder,rootInorder+1,endInorder); } return root; }