二叉樹的鏡像

二叉樹的鏡像

完成一個函數，輸入一顆二叉樹，該函數輸出它的鏡像。

思路：先序遍歷這顆樹的每個節點，如果遍歷到的節點有位元組點，

就得到了樹的鏡像。

參考代碼：

root@gt:/home/git/Code# ./a.out 8 6 5 7 10 9 11 8 10 11 9 6 7 5 root@gt:/home/git/Code# cat mirror.c #include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct BinaryTreeNode{ int value; struct BinaryTreeNode* pLeft; struct BinaryTreeNode* pRight;}BTNode;void mirror(BTNode* proot){ if(proot == NULL) return; if(proot->pLeft == NULL && proot->pRight == NULL) return; BTNode* pTmp = proot->pLeft; proot->pLeft = proot->pRight; proot->pRight = pTmp; if(proot->pLeft) mirror(proot->pLeft); if(proot->pRight) mirror(proot->pRight);}BTNode* core(int* preStart,int* preEnd,int* inStart,int* inEnd){//前序遍歷的地一個元素就是根節點 int rootValue = preStart[0]; BTNode* root = malloc(sizeof(BTNode)); root->value = rootValue; root->pLeft = root->pRight = NULL;//在中序遍歷序號中找到根節點的值 int* rootIn = inStart; while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn; int leftLen = rootIn - inStart; int* leftPreEnd = preStart + leftLen; if(leftLen>0) { root->pLeft = core(preStart+1,leftPreEnd,inStart,inStart+leftLen-1); } if(leftLen < preEnd - preStart) { root->pRight = core(leftPreEnd+1,preEnd,rootIn+1,inEnd); } return root;}BTNode* construct(int* pre,int* in,int len){ if(pre==NULL || in==NULL || len<=0) return 0; return core(pre,pre+len-1,in,in+len-1);}void preOrder(BTNode* root){ if(root ==NULL) return; printf("%d ",root->value); preOrder(root->pLeft); preOrder(root->pRight);}int main(){ int pre[] = {8,6,5,7,10,9,11}; int in[] = {5,6,7,8,9,10,11}; BTNode* root = construct(pre,in,sizeof(pre)/sizeof(int)); preOrder(root); printf("
"); mirror(root); preOrder(root); printf("
"); return 0;}

推薦閱讀：