名稱:判斷兩個二叉樹是否相似
說明:此處的兩個方法一個是非遞歸，一個是遞歸算法。其實兩個算法的本質思路是一樣的就是，判斷位置相同的兩個結點是否同時為空或同時不為空。只是具體的實現不一樣。
對于層次遍歷法：此處不小心用錯了，本應該用隊列來當作排列下一層元素的。歪打正著，此處用棧也可以，只是判斷的結點順序不一樣。隊列的話，是從每一層的左端到右端。棧的話，是從右端到左端。在此處都沒影響。我去，有發現一點，要從右到左訪問一層的元素的話，應該用棧。
對于遞歸，看起來比非遞歸要簡單不少?；镜乃悸泛芎唵?，要注意的是，在程序需要從子樹接收返回是否相似的信息。這樣的話，有一個問題，就是必須等樹完全判斷完才可以最終返回。不想上面的，過程中發現不一樣就可以立即返回了。
//層次遍歷法判斷兩棵樹是否相似bool IsSemblable1(BiTree T1,BiTree T2){ stack<BiTNode* > _sta1,_sta2; //用來存放下一層元素的容器，此處棧和隊列都行 BiTNode *p1 = T1,*p2 = T2; //p1用來跟蹤T1,p2用來跟蹤T2 while((_sta1.empty() == false || p1 != NULL) &&(_sta2.empty() == false || p2 != NULL)) { if(p1 != NULL && p2 != NULL ) //如果p1和p2都不為空時 { if(p1->lchild != NULL && p2->lchild != NULL) //如果p1和p2的左子樹都不為空時 { _sta1.push(p1->lchild); _sta2.push(p2->lchild); } else if( p1->lchild != NULL || p2->lchild != NULL) //如果p1的左子樹為空，但是p2的左子樹不為空，或者相反 return false; if(p1->rchild != NULL && p2->rchild != NULL) //如果p1和p2的右子樹都不為空時 { _sta1.push(p1->rchild); _sta2.push(p2->rchild); } else if(p1->rchild != NULL || p2->rchild != NULL) //如果p1的右子樹為空，但是p2的右子樹不為空，或者相反 return false; //訪問完兩棵樹的當前結點后，置空讓下一次循環彈出棧中元素（此處其實直接彈出元素也行） p1 = NULL; p2 = NULL; } else if(p1 != NULL || p2 != NULL) //當前節點有一個為空 return false; else { //彈出兩個樹的棧頂元素 p1 = _sta1.top(); p2 = _sta2.top(); _sta1.pop(); _sta2.pop(); } } return true;}//遞歸判斷兩棵樹是否相似bool IsSemblable2(BiTree T1,BiTree T2){ bool leftS = false,rightS = false; //用來接受子樹返回的信息 if(T1 == NULL && T2 == NULL) //兩個結點都為空 return true; else if(T1 == NULL || T2 == NULL) //有一個結點不為空 return false; else { int leftS = IsSemblable2(T1->lchild,T2->lchild); //遞歸左子樹 int rightS = IsSemblable2(T1->rchild,T2->rchild); //遞歸右子樹 return leftS && rightS ; //返回兩個子樹的信息 }}總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對武林網的支持。如果你想了解更多相關內容請查看下面相關鏈接
新聞熱點
疑難解答
圖片精選
