《劍指offer》:[59]對稱的二叉樹
來源：程序員人生 發(fā)布時間：2016-08-29 08:30:01 閱讀次數(shù)：2428次
題目；請實現(xiàn)1個函數(shù)，用來判斷1棵2叉樹是否是對稱的。如果1顆2叉樹和它的鏡像1樣，那末它是對稱的。
例如，下面2棵樹圖（1）就是對稱的2叉樹，而圖（2）（3）就不是的。
分析：我們知道樹的遍歷有3種方式：前，中，后。顧名思義，對稱就是左側(cè)的和右側(cè)的相等，中間的自己等于自己。
所以我們自己可以定義1種對稱遍歷算法，例如前序遍歷中的前，左，右。對稱算法就是：前，右，左。恰好對稱比較。固然了其他的中和后序遍歷也行，我們也能夠定義與其對應的對稱算法。
但是其中為了不出現(xiàn)樹（3）中的遍歷出來的數(shù)據(jù)1樣，造成誤判，我們需要對葉子結(jié)點加上標識，如空節(jié)點需要設置為NULL。而不能只是比較遍歷后的數(shù)據(jù)。
具體是實現(xiàn)代碼以下：
#include <iostream>
using namespace std;
struct BinaryTree
{
int data;
BinaryTree *pLeft;
BinaryTree *pRight;
};
BinaryTree *pRoot1=NULL;
BinaryTree *pRoot2=NULL;
BinaryTree *pRoot3=NULL;
void CreateTree(BinaryTree * &root)
{
int data;
cin>>data;
if(0==data)
root=NULL;
else
{
root=new BinaryTree;
root->data=data;
//前序遍歷構(gòu)建2叉樹；
CreateTree(root->pLeft);
CreateTree(root->pRight);
}
}
bool IsSymmetricalHelp(BinaryTree *root1,BinaryTree *root2)
{
if(root1==NULL && root2==NULL)
return true;
if(root1==NULL || root2==NULL)//把null也算上，很重要，避免數(shù)據(jù)1樣的特殊情況；
return false;
if(root1->data!=root2->data)
return false;
return IsSymmetricalHelp(root1->pLeft,root2->pRight)
&& IsSymmetricalHelp(root1->pRight,root2->pLeft);
}
bool IsSymmetrical(BinaryTree *root)
{
return IsSymmetricalHelp(root,root);
}
void PreOrder(BinaryTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pLeft);
PreOrder(root->pRight);
}
}
void UntiPreOrder(BinaryTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pRight);
PreOrder(root->pLeft);
}
}
int main()
{
bool result=false;
CreateTree(pRoot1);
cout<<"樹1的--前序遍歷：";
PreOrder(pRoot1);
cout<<endl;
cout<<"樹1的反前序遍歷：";
UntiPreOrder(pRoot1);
result=IsSymmetrical(pRoot1);
if(result)
cout<<endl<<"該樹是對稱樹！"<<endl;
else
cout<<"該樹不是對稱樹！"<<endl;
cout<<endl;
CreateTree(pRoot2);//樹3雖然遍歷1樣，但是否是對成樹！
cout<<"樹2的--前序遍歷：";
PreOrder(pRoot2);
cout<<endl;
cout<<"樹2的反前序遍歷：";
UntiPreOrder(pRoot2);
cout<<endl;
result=IsSymmetrical(pRoot2);
if(result)
cout<<"該樹是對稱樹！"<<endl;
else
cout<<"該樹不是對稱樹！"<<endl;
cout<<endl;
system("pause");
return 0;
}
運行結(jié)果以下；
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
