帮人建网站价格,广告电话,深圳夫博网站建设有限公司,wordpress的用户管理实现原理试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似#xff0c;指的是T1和T2都是空的二叉树或都只有一个根节点#xff1b;或者T1的左子树和T2的左子树是相似的#xff0c;且T1的右子树和T2的右子树是相似的 #include iostream
#include stack
#inc… 试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似指的是T1和T2都是空的二叉树或都只有一个根节点或者T1的左子树和T2的左子树是相似的且T1的右子树和T2的右子树是相似的 #include iostream
#include stack
#include queue
typedef struct treenode{char data;struct treenode *left;struct treenode *right;
}treenode,*ptreenode;ptreenode buytreenode(char x)
{ptreenode n(ptreenode) malloc(sizeof (treenode));n-datax;n-left nullptr,n-right nullptr;return n;
}
ptreenode build_tree1()
{ptreenode root buytreenode(A);root-left buytreenode(B);root-right buytreenode(C);root-left-left buytreenode(D);root-left-right buytreenode(E);root-right-left buytreenode(F);root-right-right buytreenode(G);root-left-left-left buytreenode(H);root-left-left-right buytreenode(I);return root;
}ptreenode build_tree2()
{ptreenode root buytreenode(A);root-left buytreenode(B);root-right buytreenode(C);root-left-left buytreenode(D);root-left-right buytreenode(E);root-right-left buytreenode(F);root-right-right buytreenode(G);root-left-left-left buytreenode(H);root-left-left-right buytreenode(I);root-left-right-left buytreenode(J);root-left-right-right buytreenode(K);root-right-left-left buytreenode(L);root-right-left-right buytreenode(M);root-right-right-left buytreenode(N);root-right-right-right buytreenode(O);return root;
}ptreenode build_tree3()
{ptreenode root buytreenode(Z);root-left buytreenode(Y);root-right buytreenode(W);root-left-left buytreenode(X);root-left-right buytreenode(E);root-right-left buytreenode(F);root-right-right buytreenode(G);root-left-left-left buytreenode(H);root-left-left-right buytreenode(I);root-left-right-left buytreenode(J);root-left-right-right buytreenode(K);root-right-left-left buytreenode(L);root-right-left-right buytreenode(M);root-right-right-left buytreenode(N);root-right-right-right buytreenode(O);return root;
}
void print_tree(ptreenode root) {std::queueptreenode tmp;tmp.push(root);int s tmp.size();while (!tmp.empty()) {ptreenode t tmp.front();tmp.pop();s--;printf(%3c, t-data);if (t-left) tmp.push(t-left);if (t-right) tmp.push(t-right);if (s 0) puts(), s tmp.size();}
}bool isSimilar(ptreenode root1,ptreenode root2)
{if(root1 nullptrroot2 nullptr) return true;if(root1 nullptr||root2 nullptr) return false;return isSimilar(root1-left,root2-left) isSimilar(root1-right,root2-right);
}
int main() {ptreenode root1build_tree1();ptreenode root2build_tree2();ptreenode root3build_tree3();printf(tree1:\n);print_tree(root1);printf(tree2:\n);print_tree(root2);printf(tree3:\n);print_tree(root3);if(isSimilar(root1,root2)) printf(tree1 and tree2 are similar);else printf(tree1 and tree2 are different\n);if(isSimilar(root2,root3)) printf(tree2 and tree3 are similar);else printf(tree2 and tree3 are different);return 0;
}
