C++編寫算法判斷兩棵二叉樹是否相等

         筆試題目：C++編寫算法判斷兩棵二叉樹是否相等

 　　題目：請(qǐng)實(shí)現(xiàn)兩棵樹是否相等的比較，相等返回0否則返回其他值。

　　解析：A、B兩棵樹相等，當(dāng)且僅當(dāng)RootA->c == RootB->c，而且A的左右子樹對(duì)應(yīng)相等或者左右互換后相等。

　　思想是使用分治的方法，先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點(diǎn)不相等，直接返回兩棵樹不相等;如果當(dāng)前節(jié)點(diǎn)相等，那么就遞歸的判斷他們的左右孩子是否相等。因?yàn)檫@里是普通的二叉樹，所以A的左、右子樹和B的右、左子樹相等也是可以的。

　　C++代碼：

　　#include

　　using namespace std;

　　typedef struct TreeNode{

　　char c;

　　struct TreeNode * left;

　　struct TreeNode * right;

　　};

　　/*判斷兩棵二叉樹是否相等，如果相等返回0，如果不相等則返回1*/

　　int compareTree(TreeNode* tree1, TreeNode* tree2){

　　//用分治的方法做，比較當(dāng)前根，然后比較左子樹和右子樹

　　bool tree1IsNull = (tree1==NULL);

　　bool tree2IsNull = (tree2==NULL);

　　if(tree1IsNull != tree2IsNull){

　　return 1;

　　}

　　if(tree1IsNull && tree2IsNull){

　　//如果兩個(gè)都是NULL，則相等

　　return 0;

　　}

　　//如果根節(jié)點(diǎn)不相等，直接返回不相等，否則的話，看看他們孩子相等不相等

　　if(tree1->c != tree2->c){

　　return 1;

　　}

　　return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))

　　|

　　(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left))

　　;

　　}

【C++編寫算法判斷兩棵二叉樹是否相等】相關(guān)文章：

判斷兒童的心理是否健康的標(biāo)志05-08

怎么判斷是否是焦慮癥05-08

如何判斷面試是否成功11-19

如何判斷自己是否適合創(chuàng)業(yè)03-07

家電常識(shí)：如何判斷冰箱是否保鮮？07-14

如何判斷你是否適合創(chuàng)業(yè)呢12-21

DOS中判斷進(jìn)程是否存在的方法03-09

創(chuàng)業(yè)初期如何判斷項(xiàng)目是否賺錢11-02

創(chuàng)業(yè)初期如何判斷項(xiàng)目是否賺錢03-05

怎么判斷咖啡豆是否新鮮01-04