樹的子結構

樹的子結構

輸入兩顆二叉樹A，B。判斷B是不是A的子結構。

思路：

2.判斷樹A中以R為根節點的子樹是不是包含和樹B一樣的結構

tips：如果二叉樹中含有相同值的節點，構造二叉樹的方法會出現錯誤

參考代碼：

root@gt:/home/git/Code# ./a.out 11.000000 2.000000 4.000000 7.000000 3.000000 5.000000 6.000000 ---------------3.000000 5.000000 6.000000 root@gt:/home/git/Code# cat hasSubTree.c #include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdbool.h>typedef struct BinaryTreeNode{ double value; struct BinaryTreeNode* pLeft; struct BinaryTreeNode* pRight;}BTNode;bool equalValue(double a,double b){ if(a - b > -0.000001 && a - b < 0.000001) return true; else return false;}bool equalNode(BTNode* pTree1,BTNode* pTree2){ if((pTree1->value - pTree2->value > -0.000001)&& (pTree1->value - pTree2->value < 0.000001)) return true; else return false;}bool hasSub(BTNode* pTree1,BTNode* pTree2){ if(pTree2 == NULL) return true; if(pTree1 == NULL) return false; if(!equalNode(pTree1,pTree2)) return false; return hasSub(pTree1->pLeft,pTree2->pLeft) && hasSub(pTree1->pRight,pTree2->pRight);}bool hasSubTree(BTNode* pTree1,BTNode* pTree2){ bool res = false; if(pTree1 != NULL && pTree2 != NULL) { if(equalNode(pTree1,pTree2)) res = hasSub(pTree1,pTree2); if(!res) res = hasSubTree(pTree1->pLeft,pTree2); if(!res) res = hasSubTree(pTree1->pRight,pTree2); } return res;}BTNode* core(double* preStart,double* preEnd,double* inStart,double* inEnd){ double rootValue = preStart[0]; BTNode* root = malloc(sizeof(BTNode)); root->value = rootValue; root->pLeft = root->pRight = NULL; if(preStart == preEnd) { if(inStart == inEnd && equalValue(*preStart,*inStart)) return root; else return NULL; } double* rootIn = inStart; while(rootIn <= inEnd && equalValue(*rootIn,rootValue)) ++rootIn; int leftLen =rootIn - inStart; double* 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(double* pre,double* in,int len){ if(pre == NULL || in == NULL || len <= 0) return NULL; return core(pre,pre + len - 1,in,in + len -1);}void preOrder(BTNode* root){ if(root == NULL) return; printf("%lf ",root->value); preOrder(root->pLeft); preOrder(root->pRight);}int main(){ bool res = false; double pre1[] = {1,2,4,7,3,5,6,8}; double in1[] = {4,7,2,1,5,3,8,6}; double pre2[] = {3,5,6}; double in2[] = {5,3,6}; BTNode* pTree1 = construct(pre1,in1,8); BTNode* pTree2 = construct(pre2,in2,3); res = hasSubTree(pTree1,pTree2); printf("%d
",res); preOrder(pTree1); printf("
---------------
"); preOrder(pTree2); printf("
"); return 0;}

推薦閱讀：