重建二叉树－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. */