问题一.请完成一个函数，输入一个二叉树，该函数输出它的镜像。二叉树的结点定义如下: struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
例子如下:
代码实现如下:
#include "stdafx.h" #include "..\Utilities\BinaryTree.h" #include <stack> void MirrorRecursively(BinaryTreeNode *pNode) { if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight)) return; BinaryTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; if(pNode->m_pLeft) MirrorRecursively(pNode->m_pLeft); if(pNode->m_pRight) MirrorRecursively(pNode->m_pRight); } void MirrorIteratively(BinaryTreeNode* pRoot) { if(pRoot == NULL) return; std::stack<BinaryTreeNode*> stackTreeNode; stackTreeNode.push(pRoot); while(stackTreeNode.size() > 0) { BinaryTreeNode *pNode = stackTreeNode.top(); stackTreeNode.pop(); BinaryTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; if(pNode->m_pLeft) stackTreeNode.push(pNode->m_pLeft); if(pNode->m_pRight) stackTreeNode.push(pNode->m_pRight); } } // ====================测试代码==================== // 测试完全二叉树：除了叶子节点，其他节点都有两个子节点 // 8 // 6 10 // 5 7 9 11 void Test1() { printf("=====Test1 starts:=====\n"); 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); PrintTree(pNode8); printf("=====Test1: MirrorRecursively=====\n"); MirrorRecursively(pNode8); PrintTree(pNode8); printf("=====Test1: MirrorIteratively=====\n"); MirrorIteratively(pNode8); PrintTree(pNode8); DestroyTree(pNode8); } // 测试二叉树：出叶子结点之外，左右的结点都有且只有一个左子结点 // 8 // 7 // 6 // 5 // 4 void Test2() { printf("=====Test2 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); ConnectTreeNodes(pNode8, pNode7, NULL); ConnectTreeNodes(pNode7, pNode6, NULL); ConnectTreeNodes(pNode6, pNode5, NULL); ConnectTreeNodes(pNode5, pNode4, NULL); PrintTree(pNode8); printf("=====Test2: MirrorRecursively=====\n"); MirrorRecursively(pNode8); PrintTree(pNode8); printf("=====Test2: MirrorIteratively=====\n"); MirrorIteratively(pNode8); PrintTree(pNode8); DestroyTree(pNode8); } // 测试二叉树：出叶子结点之外，左右的结点都有且只有一个右子结点 // 8 // 7 // 6 // 5 // 4 void Test3() { printf("=====Test3 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7); BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6); BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5); BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4); ConnectTreeNodes(pNode8, NULL, pNode7); ConnectTreeNodes(pNode7, NULL, pNode6); ConnectTreeNodes(pNode6, NULL, pNode5); ConnectTreeNodes(pNode5, NULL, pNode4); PrintTree(pNode8); printf("=====Test3: MirrorRecursively=====\n"); MirrorRecursively(pNode8); PrintTree(pNode8); printf("=====Test3: MirrorIteratively=====\n"); MirrorIteratively(pNode8); PrintTree(pNode8); DestroyTree(pNode8); } // 测试空二叉树：根结点为空指针 void Test4() { printf("=====Test4 starts:=====\n"); BinaryTreeNode* pNode = NULL; PrintTree(pNode); printf("=====Test4: MirrorRecursively=====\n"); MirrorRecursively(pNode); PrintTree(pNode); printf("=====Test4: MirrorIteratively=====\n"); MirrorIteratively(pNode); PrintTree(pNode); } // 测试只有一个结点的二叉树 void Test5() { printf("=====Test5 starts:=====\n"); BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8); PrintTree(pNode8); printf("=====Test4: MirrorRecursively=====\n"); MirrorRecursively(pNode8); PrintTree(pNode8); printf("=====Test4: MirrorIteratively=====\n"); MirrorIteratively(pNode8); PrintTree(pNode8); } int _tmain(int argc, _TCHAR* argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); return 0; } 运行结果如下:
问题二.输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如:
详细的代码实现如下:
#include "stdafx.h" void PrintMatrixInCircle(int** numbers, int columns, int rows, int start); void printNumber(int number); void PrintMatrixClockwisely(int** numbers, int columns, int rows) { if(numbers == NULL || columns <= 0 || rows <= 0) return; int start = 0; while(columns > start * 2 && rows > start * 2) { PrintMatrixInCircle(numbers, columns, rows, start); ++start; } } void PrintMatrixInCircle(int** numbers, int columns, int rows, int start) { int endX = columns - 1 - start; int endY = rows - 1 - start; // 从左到右打印一行 for(int i = start; i <= endX; ++i) { int number = numbers[start][i]; printNumber(number); } // 从上到下打印一列 if(start < endY) { for(int i = start + 1; i <= endY; ++i) { int number = numbers[i][endX]; printNumber(number); } } // 从右到左打印一行 if(start < endX && start < endY) { for(int i = endX - 1; i >= start; --i) { int number = numbers[endY][i]; printNumber(number); } } // 从下到上打印一行 if(start < endX && start < endY - 1) { for(int i = endY - 1; i >= start + 1; --i) { int number = numbers[i][start]; printNumber(number); } } } void printNumber(int number) { printf("%d\t", number); } // ====================测试代码==================== void Test(int columns, int rows) { printf("Test Begin: %d columns, %d rows.\n", columns, rows); if(columns < 1 || rows < 1) return; int** numbers = new int*[rows]; for(int i = 0; i < rows; ++i) { numbers[i] = new int[columns]; for(int j = 0; j < columns; ++j) { numbers[i][j] = i * columns + j + 1; } } PrintMatrixClockwisely(numbers, columns, rows); printf("\n"); for(int i = 0; i < rows; ++i) delete[] (int*)numbers[i]; delete[] numbers; } int _tmain(int argc, _TCHAR* argv[]) { /* 1 */ Test(1, 1); /* 1 2 3 4 */ Test(2, 2); /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 */ Test(4, 4); /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 */ Test(5, 5); /* 1 2 3 4 5 */ Test(1, 5); /* 1 2 3 4 5 6 7 8 9 10 */ Test(2, 5); /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */ Test(3, 5); /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 */ Test(4, 5); /* 1 2 3 4 5 */ Test(5, 1); /* 1 2 3 4 5 6 7 8 9 10 */ Test(5, 2); /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */ Test(5, 3); /* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 */ Test(5, 4); return 0; } 运行结果如下:
