C++基于先序、中序遍历结果重建二叉树的方法分享

—-想了解C++基于先序、中序遍历结果重建二叉树的方法分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

C++基于先序、中序遍历结果重建二叉树的方法分享实例讲述了C++基于先序、中序遍历结果重建二叉树的方法。分享给大家供大家参考，具体如下：

题目：

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

实现代码：

  #include <iostream>  #include <vector>  #include <stack>  using namespace std;  struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}  };  //创建二叉树算法  TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> mid)  {    int nodeSize = mid.size();    if (nodeSize == 0)      return NULL;    vector<int> leftPre, leftMid, rightPre, rightMid;    TreeNode* phead = new TreeNode(pre[0]); //第一个当是根节点    int rootPos = 0; //根节点在中序遍历中的位置    for (int i = 0; i < nodeSize; i++)    {      if (mid[i] == pre[0])      {        rootPos = i;        break;      }    }    for (int i = 0; i < nodeSize; i++)    {      if (i < rootPos)      {        leftMid.push_back(mid[i]);        leftPre.push_back(pre[i + 1]);      }      else if (i > rootPos)      {        rightMid.push_back(mid[i]);        rightPre.push_back(pre[i]);      }    }    phead->left = reConstructBinaryTree(leftPre, leftMid);    phead->right = reConstructBinaryTree(rightPre, rightMid);    return phead;  }  //打印后续遍历顺序  void printNodeValue(TreeNode* root)  {    if (!root){      return;    }    printNodeValue(root->left);    printNodeValue(root->right);    cout << root->val<< " ";  }  int main()  {    vector<int> preVec{ 1, 2, 4, 5, 3, 6 };    vector<int> midVec{ 4, 2, 5, 1, 6, 3 };    cout << "先序遍历序列为 1 2 4 5 3 6" << endl;    cout << "中序遍历序列为 4 2 5 1 6 3" << endl;    TreeNode* root = reConstructBinaryTree(preVec, midVec);    cout << "后续遍历序列为 ";    printNodeValue(root);    cout << endl;    system("pause");  }  /*  测试二叉树形状：        1    2       3    4  5    6  */    

运行结果：

  先序遍历序列为 1 2 4 5 3 6  中序遍历序列为 4 2 5 1 6 3  后续遍历序列为 4 5 2 6 3 1  请按任意键继续. . .    

希望C++基于先序、中序遍历结果重建二叉树的方法分享所述对大家C++程序设计有所帮助。