重建二叉树－C++

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程https://www.captainai.net/troubleshooter

// 面试题7：重建二叉树 // 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输 // 入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, // 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出 // 图2.6所示的二叉树并输出它的头结点。 #include <exception> #include <cstdio> #include <stdexcept> struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; }; BinaryTreeNode *CreateBinaryTreeNode(int value) { BinaryTreeNode *pNode = new BinaryTreeNode(); pNode->m_nValue = value; pNode->m_pLeft = nullptr; pNode->m_pRight = nullptr; return pNode; } void ConnectTreeNodes(BinaryTreeNode *pParent, BinaryTreeNode *pLeft, BinaryTreeNode *pRight) { if (pParent != nullptr) { pParent->m_pLeft = pLeft; pParent->m_pRight = pRight; } } void PrintTreeNode(const BinaryTreeNode *pNode) { if (pNode != nullptr) { printf("value of this node is: %d\n", pNode->m_nValue); if (pNode->m_pLeft != nullptr) printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue); else printf("left child is nullptr.\n"); if (pNode->m_pRight != nullptr) printf("value of its right child is: %d.\n", pNode->m_pRight->m_nValue); else printf("right child is nullptr.\n"); } else { printf("this node is nullptr.\n"); } printf("\n"); } void PrintTree(const BinaryTreeNode *pRoot) { PrintTreeNode(pRoot); if (pRoot != nullptr) { if (pRoot->m_pLeft != nullptr) PrintTree(pRoot->m_pLeft); if (pRoot->m_pRight != nullptr) PrintTree(pRoot->m_pRight); } } void DestroyTree(BinaryTreeNode *pRoot) { if (pRoot != nullptr) { BinaryTreeNode *pLeft = pRoot->m_pLeft; BinaryTreeNode *pRight = pRoot->m_pRight; delete pRoot; pRoot = nullptr; DestroyTree(pLeft); DestroyTree(pRight); } } BinaryTreeNode *ConstructCore(int *startPreorder, int *endPreorder, int *startInorder, int *endInorder); BinaryTreeNode *Construct(int *preorder, int *inorder, int length) { if (preorder == nullptr || inorder == nullptr || length <= 0) return nullptr; 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 = nullptr; if (startPreorder == endPreorder) { if (startInorder == endInorder && *startPreorder == *startInorder) return root; else throw std::logic_error("Invalid input."); } // 在中序遍历中找到根结点的值 int *rootInorder = startInorder; while (rootInorder <= endInorder && *rootInorder != rootValue) ++rootInorder; if (rootInorder == endInorder && *rootInorder != rootValue) throw std::logic_error("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; } // ====================测试代码==================== void Test(char *testName, int *preorder, int *inorder, int length) { if (testName != nullptr) printf("%s begins:\n", testName); printf("The preorder sequence is: "); for (int i = 0; i < length; ++i) printf("%d ", preorder[i]); printf("\n"); printf("The inorder sequence is: "); for (int i = 0; i < length; ++i) printf("%d ", inorder[i]); printf("\n"); try { BinaryTreeNode *root = Construct(preorder, inorder, length); PrintTree(root); DestroyTree(root); } catch (std::exception &exception) { printf("Invalid Input.\n"); } } // 普通二叉树 // 1 // / \ // 2 3 // / / \ // 4 5 6 // \ / // 7 8 void Test1() { const int length = 8; int preorder[length] = {1, 2, 4, 7, 3, 5, 6, 8}; int inorder[length] = {4, 7, 2, 1, 5, 3, 8, 6}; Test("Test1", preorder, inorder, length); } // 所有结点都没有右子结点 // 1 // / // 2 // / // 3 // / // 4 // / // 5 void Test2() { const int length = 5; int preorder[length] = {1, 2, 3, 4, 5}; int inorder[length] = {5, 4, 3, 2, 1}; Test("Test2", preorder, inorder, length); } // 所有结点都没有左子结点 // 1 // \ // 2 // \ // 3 // \ // 4 // \ // 5 void Test3() { const int length = 5; int preorder[length] = {1, 2, 3, 4, 5}; int inorder[length] = {1, 2, 3, 4, 5}; Test("Test3", preorder, inorder, length); } // 树中只有一个结点 void Test4() { const int length = 1; int preorder[length] = {1}; int inorder[length] = {1}; Test("Test4", preorder, inorder, length); } // 完全二叉树 // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 void Test5() { const int length = 7; int preorder[length] = {1, 2, 4, 5, 3, 6, 7}; int inorder[length] = {4, 2, 5, 1, 6, 3, 7}; Test("Test5", preorder, inorder, length); } // 输入空指针 void Test6() { Test("Test6", nullptr, nullptr, 0); } // 输入的两个序列不匹配 void Test7() { const int length = 7; int preorder[length] = {1, 2, 4, 5, 3, 6, 7}; int inorder[length] = {4, 2, 8, 1, 6, 3, 7}; Test("Test7: for unmatched input", preorder, inorder, length); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); return 0; } // ------ Output ------ /* Test1 begins: The preorder sequence is: 1 2 4 7 3 5 6 8 The inorder sequence is: 4 7 2 1 5 3 8 6 value of this node is: 1 value of its left child is: 2. value of its right child is: 3. value of this node is: 2 value of its left child is: 4. right child is nullptr. value of this node is: 4 left child is nullptr. value of its right child is: 7. value of this node is: 7 left child is nullptr. right child is nullptr. value of this node is: 3 value of its left child is: 5. value of its right child is: 6. value of this node is: 5 left child is nullptr. right child is nullptr. value of this node is: 6 value of its left child is: 8. right child is nullptr. value of this node is: 8 left child is nullptr. right child is nullptr. Test2 begins: The preorder sequence is: 1 2 3 4 5 The inorder sequence is: 5 4 3 2 1 value of this node is: 1 value of its left child is: 2. right child is nullptr. value of this node is: 2 value of its left child is: 3. right child is nullptr. value of this node is: 3 value of its left child is: 4. right child is nullptr. value of this node is: 4 value of its left child is: 5. right child is nullptr. value of this node is: 5 left child is nullptr. right child is nullptr. Test3 begins: The preorder sequence is: 1 2 3 4 5 The inorder sequence is: 1 2 3 4 5 value of this node is: 1 left child is nullptr. value of its right child is: 2. value of this node is: 2 left child is nullptr. value of its right child is: 3. value of this node is: 3 left child is nullptr. value of its right child is: 4. value of this node is: 4 left child is nullptr. value of its right child is: 5. value of this node is: 5 left child is nullptr. right child is nullptr. Test4 begins: The preorder sequence is: 1 The inorder sequence is: 1 value of this node is: 1 left child is nullptr. right child is nullptr. Test5 begins: The preorder sequence is: 1 2 4 5 3 6 7 The inorder sequence is: 4 2 5 1 6 3 7 value of this node is: 1 value of its left child is: 2. value of its right child is: 3. value of this node is: 2 value of its left child is: 4. value of its right child is: 5. value of this node is: 4 left child is nullptr. right child is nullptr. value of this node is: 5 left child is nullptr. right child is nullptr. value of this node is: 3 value of its left child is: 6. value of its right child is: 7. value of this node is: 6 left child is nullptr. right child is nullptr. value of this node is: 7 left child is nullptr. right child is nullptr. Test6 begins: The preorder sequence is: The inorder sequence is: this node is nullptr. Test7: for unmatched input begins: The preorder sequence is: 1 2 4 5 3 6 7 The inorder sequence is: 4 2 8 1 6 3 7 Invalid Input. */