当前位置：首页 > news >正文

之字形打印二叉树－C++

news 2026/4/28 10:30:54

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程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::stack<BinaryTreeNode *> 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 */

查看全文

http://www.jsqmd.com/news/713357/