#include "stdafx.h" #include <iostream> #include <exception> #include <stack> using namespace std;/*重建二叉樹(shù) 題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果,請(qǐng)重建出該二叉樹(shù).假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字.例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建出圖所示的二叉樹(shù)并輸出它的頭結(jié)點(diǎn)。二叉樹(shù)結(jié)點(diǎn)的定義如下: */struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_PRight; };BinaryTreeNode* ConstructConre(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;elsethrow std::exception("invalid input");}//在中序遍歷中找到根結(jié)點(diǎn)的值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){//構(gòu)建左子樹(shù)root->m_pLeft = ConstructConre(startPreorder+1,leftPreorderEnd,startInorder,rootInorder -1);}if(leftLength<endPreorder - startPreorder){//構(gòu)建右子樹(shù)root->m_PRight = ConstructConre(leftPreorderEnd +1,endPreorder,rootInorder+1,endInorder);}return root; }BinaryTreeNode* Construct(int *preOrder,int* inOrder,int length) {if(preOrder==NULL||inOrder==NULL||length<=0){return NULL;}return ConstructConre(preOrder,preOrder+length-1,inOrder,inOrder+length-1); } int _tmain(int argc, _TCHAR* argv[]) { return 0 ; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/crazycodehzp/p/3556863.html

總結(jié)

以上是生活随笔為你收集整理的根据先序和中序序列重建二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。