构建二叉树

2019-11-06 08:41:55

字体：大中小

来源：转载

供稿：网友

本文通过输入二叉树的前序和中序遍历，构建该二叉树，并输出二叉树的后序遍历。 注：程序针对输入不合法情况使用抛出异常 的方法来进行处理。 原理不再介绍，以下为程序：

#include<iostream>#include<vector>using namespace std;struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_PRight;};BinaryTreeNode * PreConstruct(const vector<int> &preorder, const vector<int> &inorder);BinaryTreeNode * ConstructCore(const vector<int> &preorder, int startOfPreorder, int endOfPreorder, const vector<int> &inorder, int startOfInorder, int endOfInorder);//构建二叉树的preorder区间[startOfPreorder，endOfPreorder]和inorder区间[startOfInorder, endOfInorder]所形成的子树，返回子树的根结点。void test(const vector<int> &preorder, const vector<int> &inorder);int main(){ vector<int> preorder_1 = { 1, 2, 4, 9, 3, 6, 7 }; //不完全二叉树 vector<int> inorder_1 = { 4, 9, 2, 1, 6, 3, 7 }; vector<int> postorder_1 = { 9, 4, 2, 6, 7, 3, 1 }; vector<int> preorder_2 = { 1, 2, 4, 5, 3, 6, 7 }; //完全二叉树 vector<int> inorder_2 = { 4, 2, 5, 1, 6, 3, 7 }; vector<int> postorder_2 = { 4, 5, 2, 6, 7, 3, 1 }; vector<int> preorder_3 = { 1, 2, 3, 4, 5, 6, 7 }; //无右子结点二叉树 vector<int> inorder_3 = { 7, 6, 5, 4, 3, 2, 1 }; vector<int> postorder_3 = { 7, 6, 5, 4, 3, 2, 1 }; vector<int> preorder_4 = { 1, 2, 3, 4, 5, 6, 7 }; //无左子结点二叉树 vector<int> inorder_4 = { 1, 2, 3, 4, 5, 6, 7 }; vector<int> postorder_4 = { 7, 6, 5, 4, 3, 2, 1 }; vector<int> preorder_5 = { 1 }; //只有根结点二叉树 vector<int> inorder_5 = { 1 }; vector<int> postorder_5 = { 1 }; vector<int> preorder_6 = {}; //空二叉树 vector<int> inorder_6 = {}; vector<int> postorder_6 = {}; vector<int> preorder_7 = { 1, 2, 3, 9, 3, 6, 7 }; //不可能二叉树：前序与中序不匹配 vector<int> inorder_7 = { 4, 9, 1, 2, 6, 3, 7 }; vector<int> preorder_8 = { 1, 2, 3, 9, 3, 6, 7 }; //不可能二叉树：前序与中序不匹配 vector<int> inorder_8 = { 4, 9, 1, 1, 6, 3, 7 }; vector<int> preorder_9 = { 1, 2, 3, 9, 3, 6, 7 }; //不可能二叉树：前序与中序不匹配 vector<int> inorder_9 = { 4, 9, 2, 1, 6, 3 }; test(preorder_1, inorder_1); //功能测试 test(preorder_2, inorder_2); test(preorder_3, inorder_3); //边界测试 test(preorder_4, inorder_4); test(preorder_5, inorder_5); test(preorder_6, inorder_6); //负面测试 test(preorder_7, inorder_7); test(preorder_8, inorder_8); test(preorder_9, inorder_9); return 0;}//后序遍历二叉树void PostOrderTraversal(const BinaryTreeNode *root) { if (NULL == root) { return; } PostOrderTraversal(root->m_pLeft); PostOrderTraversal(root->m_pRight); cout << root->m_nValue << ' ';}void test(const vector<int> &preorder, const vector<int> &inorder) { cout << "The preorder of the BinaryTree is: "; int lengthOfPreorder = preorder.size(); for (int i = 0; i<lengthOfPreorder; i++) { cout << preorder.at(i) << ' '; } cout << endl; cout << "The inorder of the BinaryTree is: "; int lengthOfInorder = inorder.size(); for (int i = 0; i<lengthOfInorder; i++) { cout << inorder.at(i) << ' '; } cout << endl; BinaryTreeNode *root = NULL; try { root = PreConstruct(preorder, inorder); } catch (const char* msg) { cout << msg << endl << endl; return ; } cout << "The postorder of the BinaryTree is: "; PostOrderTraversal(root); cout << endl << endl;}BinaryTreeNode * PreConstruct(const vector<int> &preorder, const vector<int> &inorder) { BinaryTreeNode *root = NULL; int lengthOfPreorder = preorder.size(); int lengthOfInorder = inorder.size(); if (lengthOfPreorder != lengthOfInorder) { throw "Error: the Preorder and Inorder don't match"; } else if (0 == lengthOfPreorder) { throw "the Input is empty"; } else { root = ConstructCore(preorder, 0, lengthOfPreorder - 1, inorder, 0, lengthOfInorder - 1); return root; }}BinaryTreeNode * ConstructCore(const vector<int> &preorder, int startOfPreorder, int endOfPreorder, const vector<int> &inorder, int startOfInorder, int endOfInorder) { BinaryTreeNode *root = new BinaryTreeNode(); root->m_nValue = preorder.at(startOfPreorder); int indexOfRoot_Inorder = startOfInorder; while (indexOfRoot_Inorder <= endOfInorder && inorder.at(indexOfRoot_Inorder) != root->m_nValue) { ++indexOfRoot_Inorder; } if (indexOfRoot_Inorder > endOfInorder) { throw "Error: the Preorder and Inorder don't match"; } int nodeNumbersOfLeftSubtree = indexOfRoot_Inorder - startOfInorder; int nodeNumbersOfRightSubtree = endOfInorder - indexOfRoot_Inorder; if (nodeNumbersOfLeftSubtree > 0) { root->m_pLeft = ConstructCore(preorder, startOfPreorder + 1, startOfPreorder + nodeNumbersOfLeftSubtree, inorder, startOfInorder, indexOfRoot_Inorder - 1); } else root->m_pLeft = NULL; if (nodeNumbersOfRightSubtree > 0) { root->m_pRight = ConstructCore(preorder, endOfPreorder - nodeNumbersOfRightSubtree + 1, endOfPreorder, inorder, indexOfRoot_Inorder + 1, endOfInorder); } else root->m_pRight = NULL; return root;}

上一篇：给定一个字符串，求它的最长回文子串的长度，并打印出最长回文子串

下一篇：Markdown语法帮助