二叉樹鏡像，二叉樹的鏡像

二叉樹鏡像，二叉樹的鏡像

題目：請完成一個函數，輸入一個二叉樹，該函數輸出它的鏡像。

二叉樹結點的定義如下:

struct BinaryTreeNode
{
    int              m_nValue;
    BinaryTreeNode*  m_pLeft;
    BinaryTreeNode*  m_pRight;
};

1.遞歸實現

2.循環實現

  1 #include<stdio.h>
  2 #include<stack>
  3 
  4 struct BinaryTreeNode
  5 {
  6     int              m_nValue;
  7     BinaryTreeNode*  m_pLeft;
  8     BinaryTreeNode*  m_pRight;
  9 };
 10 
 11 BinaryTreeNode* CreateBinaryTreeNode(int value)
 12 {
 13     BinaryTreeNode* pNode = new BinaryTreeNode();
 14     pNode->m_nValue = value;
 15     pNode->m_pLeft = NULL;
 16     pNode->m_pRight = NULL;
 17 }
 18 
 19 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, 
 20                     BinaryTreeNode* pRight)
 21 {
 22     if(pParent != NULL)
 23     {
 24         pParent->m_pLeft = pLeft;
 25         pParent->m_pRight = pRight;
 26     }
 27 }
 28 
 29 void PrintTreeNode(BinaryTreeNode* pNode)
 30 {
 31     if(pNode != NULL)
 32     {
 33         printf("value of this node is: %d.\n", pNode->m_nValue);
 34 
 35         if(pNode->m_pLeft != NULL)
 36             printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
 37         else
 38             printf("left child is null .\n");
 39 
 40         if(pNode->m_pRight != NULL)
 41             printf("value of its right child is: %d.\n", pNode->m_pRight->m_nValue);
 42         else
 43             printf("right child is null.\n");
 44     }
 45     else
 46     {
 47         printf("this node is null.\n");
 48     }
 49     printf("\n");
 50 }
 51 
 52 void PrintTree(BinaryTreeNode* pRoot)
 53 {
 54     PrintTreeNode(pRoot);
 55 
 56     if(pRoot != NULL)
 57     {
 58         if(pRoot->m_pLeft != NULL)
 59             PrintTree(pRoot->m_pLeft);
 60         if(pRoot->m_pRight != NULL)
 61             PrintTree(pRoot->m_pRight);
 62     }
 63 }
 64 
 65 void DestroyTree(BinaryTreeNode* pRoot)
 66 {
 67     if(pRoot != NULL)
 68     {
 69         BinaryTreeNode* pLeft = pRoot->m_pLeft;
 70         BinaryTreeNode* pRight = pRoot->m_pRight;
 71         
 72         delete pRoot;
 73         pRoot = NULL;
 74         
 75         DestroyTree(pLeft);
 76         DestroyTree(pRight);
 77     }
 78 }
 79 
 80 //方法1 遞歸實現 
 81 void MirrorRecursively(BinaryTreeNode* pNode)
 82 {
 83     if(pNode == NULL)
 84         return;
 85     if(pNode->m_pLeft == NULL && pNode->m_pRight == NULL)
 86         return;
 87 
 88     BinaryTreeNode *pTemp = pNode->m_pLeft;
 89     pNode->m_pLeft = pNode->m_pRight;
 90     pNode->m_pRight = pTemp;
 91 
 92     if(pNode->m_pLeft)
 93         MirrorRecursively(pNode->m_pLeft);
 94     if(pNode->m_pRight)
 95         MirrorRecursively(pNode->m_pRight);
 96 }
 97 
 98 //方法二 循環實現 
 99 void MirrorIteratively(BinaryTreeNode* pRoot)
100 {
101     if(pRoot == NULL)
102         return;
103 
104     std::stack<BinaryTreeNode*> stackTreeNode;
105     stackTreeNode.push(pRoot);
106 
107     while(stackTreeNode.size() > 0)
108     {
109         BinaryTreeNode *pNode = stackTreeNode.top();
110         stackTreeNode.pop();
111 
112         BinaryTreeNode *pTemp = pNode->m_pLeft;
113         pNode->m_pLeft = pNode->m_pRight;
114         pNode->m_pRight = pTemp;
115 
116         if(pNode->m_pLeft)
117                 stackTreeNode.push(pNode->m_pLeft);
118         if(pNode->m_pRight)
119                 stackTreeNode.push(pNode->m_pRight);
120     }
121 }
122 
123 // 測試完全二叉樹：除了葉子節點，其他節點都有兩個子節點
124 //            8
125 //          /   \
126 //        6      10
127 //       / \     / \
128 //      5   7   9  11
129 
130 int main()
131 {
132     BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
133     BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
134     BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
135     BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
136     BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
137     BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
138     BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);
139 
140     ConnectTreeNodes(pNode8, pNode6, pNode10);
141     ConnectTreeNodes(pNode6, pNode5, pNode7);
142     ConnectTreeNodes(pNode10, pNode9, pNode11);
143 
144     PrintTree(pNode8);
145 
146     printf("===== MirrorRecursively=====\n");
147     MirrorRecursively(pNode8);
148     PrintTree(pNode8);
149 
150     printf("===== MirrorIteratively=====\n");
151     MirrorIteratively(pNode8);
152     PrintTree(pNode8);
153 
154     DestroyTree(pNode8);
155 }