分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程https://www.captainai.net/troubleshooter// 面试题32三之字形打印二叉树 // 题目请实现一个函数按照之字形顺序打印二叉树即第一行按照从左到右的顺 // 序打印第二层按照从右到左的顺序打印第三行再按照从左到右的顺序打印 // 其他行以此类推。 #include cstdio #include stack 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); } } void Print(BinaryTreeNode *pRoot) { if (pRoot nullptr) return; std::stackBinaryTreeNode * levels[2]; int current 0; int next 1; levels[current].push(pRoot); while (!levels[0].empty() || !levels[1].empty()) { BinaryTreeNode *pNode levels[current].top(); levels[current].pop(); printf(%d , pNode-m_nValue); if (current 0) { if (pNode-m_pLeft ! nullptr) levels[next].push(pNode-m_pLeft); if (pNode-m_pRight ! nullptr) levels[next].push(pNode-m_pRight); } else { if (pNode-m_pRight ! nullptr) levels[next].push(pNode-m_pRight); if (pNode-m_pLeft ! nullptr) levels[next].push(pNode-m_pLeft); } if (levels[current].empty()) { printf(\n); current 1 - current; next 1 - next; } } } // 测试代码 // 8 // 6 10 // 5 7 9 11 void Test1() { BinaryTreeNode *pNode8 CreateBinaryTreeNode(8); BinaryTreeNode *pNode6 CreateBinaryTreeNode(6); BinaryTreeNode *pNode10 CreateBinaryTreeNode(10); BinaryTreeNode *pNode5 CreateBinaryTreeNode(5); BinaryTreeNode *pNode7 CreateBinaryTreeNode(7); BinaryTreeNode *pNode9 CreateBinaryTreeNode(9); BinaryTreeNode *pNode11 CreateBinaryTreeNode(11); ConnectTreeNodes(pNode8, pNode6, pNode10); ConnectTreeNodes(pNode6, pNode5, pNode7); ConnectTreeNodes(pNode10, pNode9, pNode11); printf(Test1 Begins: \n); printf(Expected Result is:\n); printf(8 \n); printf(10 6 \n); printf(5 7 9 11 \n\n); printf(Actual Result is: \n); Print(pNode8); printf(\n); DestroyTree(pNode8); } // 5 // 4 // 3 // 2 void Test2() { BinaryTreeNode *pNode5 CreateBinaryTreeNode(5); BinaryTreeNode *pNode4 CreateBinaryTreeNode(4); BinaryTreeNode *pNode3 CreateBinaryTreeNode(3); BinaryTreeNode *pNode2 CreateBinaryTreeNode(2); ConnectTreeNodes(pNode5, pNode4, nullptr); ConnectTreeNodes(pNode4, pNode3, nullptr); ConnectTreeNodes(pNode3, pNode2, nullptr); printf(Test2 Begins: \n); printf(Expected Result is:\n); printf(5 \n); printf(4 \n); printf(3 \n); printf(2 \n\n); printf(Actual Result is: \n); Print(pNode5); printf(\n); DestroyTree(pNode5); } // 5 // 4 // 3 // 2 void Test3() { BinaryTreeNode *pNode5 CreateBinaryTreeNode(5); BinaryTreeNode *pNode4 CreateBinaryTreeNode(4); BinaryTreeNode *pNode3 CreateBinaryTreeNode(3); BinaryTreeNode *pNode2 CreateBinaryTreeNode(2); ConnectTreeNodes(pNode5, nullptr, pNode4); ConnectTreeNodes(pNode4, nullptr, pNode3); ConnectTreeNodes(pNode3, nullptr, pNode2); printf(Test3 Begins: \n); printf(Expected Result is:\n); printf(5 \n); printf(4 \n); printf(3 \n); printf(2 \n\n); printf(Actual Result is: \n); Print(pNode5); printf(\n); DestroyTree(pNode5); } void Test4() { BinaryTreeNode *pNode5 CreateBinaryTreeNode(5); printf(Test4 Begins: \n); printf(Expected Result is:\n); printf(5 \n\n); printf(Actual Result is: \n); Print(pNode5); printf(\n); DestroyTree(pNode5); } void Test5() { printf(Test5 Begins: \n); printf(Expected Result is:\n); printf(Actual Result is: \n); Print(nullptr); printf(\n); } // 100 // / // 50 // \ // 150 void Test6() { BinaryTreeNode *pNode100 CreateBinaryTreeNode(100); BinaryTreeNode *pNode50 CreateBinaryTreeNode(50); BinaryTreeNode *pNode150 CreateBinaryTreeNode(150); ConnectTreeNodes(pNode100, pNode50, nullptr); ConnectTreeNodes(pNode50, nullptr, pNode150); printf(Test6 Begins: \n); printf(Expected Result is:\n); printf(100 \n); printf(50 \n); printf(150 \n\n); printf(Actual Result is: \n); Print(pNode100); printf(\n); } // 8 // 4 12 // 2 6 10 14 // 1 3 5 7 9 11 13 15 void Test7() { BinaryTreeNode *pNode8 CreateBinaryTreeNode(8); BinaryTreeNode *pNode4 CreateBinaryTreeNode(4); BinaryTreeNode *pNode12 CreateBinaryTreeNode(12); BinaryTreeNode *pNode2 CreateBinaryTreeNode(2); BinaryTreeNode *pNode6 CreateBinaryTreeNode(6); BinaryTreeNode *pNode10 CreateBinaryTreeNode(10); BinaryTreeNode *pNode14 CreateBinaryTreeNode(14); BinaryTreeNode *pNode1 CreateBinaryTreeNode(1); BinaryTreeNode *pNode3 CreateBinaryTreeNode(3); BinaryTreeNode *pNode5 CreateBinaryTreeNode(5); BinaryTreeNode *pNode7 CreateBinaryTreeNode(7); BinaryTreeNode *pNode9 CreateBinaryTreeNode(9); BinaryTreeNode *pNode11 CreateBinaryTreeNode(11); BinaryTreeNode *pNode13 CreateBinaryTreeNode(13); BinaryTreeNode *pNode15 CreateBinaryTreeNode(15); ConnectTreeNodes(pNode8, pNode4, pNode12); ConnectTreeNodes(pNode4, pNode2, pNode6); ConnectTreeNodes(pNode12, pNode10, pNode14); ConnectTreeNodes(pNode2, pNode1, pNode3); ConnectTreeNodes(pNode6, pNode5, pNode7); ConnectTreeNodes(pNode10, pNode9, pNode11); ConnectTreeNodes(pNode14, pNode13, pNode15); printf(Test7 Begins: \n); printf(Expected Result is:\n); printf(8 \n); printf(12 4 \n); printf(2 6 10 14 \n); printf(15 13 11 9 7 5 3 1 \n\n); printf(Actual Result is: \n); Print(pNode8); printf(\n); DestroyTree(pNode8); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); return 0; } // ------ Output ------ /* Test1 Begins: Expected Result is: 8 10 6 5 7 9 11 Actual Result is: 8 10 6 5 7 9 11 Test2 Begins: Expected Result is: 5 4 3 2 Actual Result is: 5 4 3 2 Test3 Begins: Expected Result is: 5 4 3 2 Actual Result is: 5 4 3 2 Test4 Begins: Expected Result is: 5 Actual Result is: 5 Test5 Begins: Expected Result is: Actual Result is: Test6 Begins: Expected Result is: 100 50 150 Actual Result is: 100 50 150 Test7 Begins: Expected Result is: 8 12 4 2 6 10 14 15 13 11 9 7 5 3 1 Actual Result is: 8 12 4 2 6 10 14 15 13 11 9 7 5 3 1 */