树的同构、树的层次遍历输出叶子结点

1、树的同构

题目 03-树1 树的同构 (25分)分析 1.程序主体基本上是： int main() { 建二叉树1； 建二叉树2； 判断是否同构并输出； return 0; }

2.如何存储和表示树 经分析，可以直接用数组来存储树。 具体树的表示可以用一个结构体。

struct TreeNode{ char data; int L; int R; };

3.如何确定树根 树根是没有任何一个结点的左右子树指向它的。 所以可以用一个数组checked[]来保存是否有某一个结点的子树指向它，如果checked[i]==false，那么说明i所在的结点就是树根。 4.如何判断两个树是否同构 首先判断是否有空树； 然后判断根结点中的data是否相同； 再判断是否：

树1的左子树和树2的左子树同构 && 树1的右子树和树2的右子树同构 || 树1的左子树和树2的右子树同构 && 树1的右子树和树2的左子树同构

我的代码 #include<iostream> using namespace std; struct TreeNode{ char data; int L; int R; }; const int maxn = 10; struct TreeNode trees1[maxn],trees2[maxn]; //输入根结点，判断两棵树是否同构 bool isomorphism(int root1, int root2) { if(root1==-1 || root2==-1) { return ((root1==-1) && (root2==-1)); }else if(trees1[root1].data != trees2[root2].data){ return false; }else{ return isomorphism(trees1[root1].L, trees2[root2].L) && isomorphism(trees1[root1].R, trees2[root2].R) || isomorphism(trees1[root1].L, trees2[root2].R) && isomorphism(trees1[root1].R, trees2[root2].L); } } int main() { int N; int root1 = -1,root2 = -1; //-1表示为空 bool checked[maxn]; char c1,c2; //freopen("case2.txt","r",stdin); //构建第一棵树 cin>>N; for(int i=0; i<N; i++) checked[i] = false; for(int i=0; i<N; i++) { cin>>trees1[i].data>>c1>>c2; //处理左子树 if(c1 != '-') { trees1[i].L = c1-'0'; checked[trees1[i].L] = true; }else{ trees1[i].L = -1; //-1表示为空 } //处理右子树 if(c2 != '-') { trees1[i].R = c2-'0'; checked[trees1[i].R] = true; }else{ trees1[i].R = -1; } } //找到树根 for(int i=0; i<N; i++) { if(!checked[i]) { root1 = i; break; } } //构建第二棵树 cin>>N; for(int i=0; i<N; i++) { checked[i] = false; cin>>trees2[i].data>>c1>>c2; //处理左子树 if(c1 != '-') { trees2[i].L = c1-'0'; checked[trees2[i].L] = true; }else{ trees2[i].L = -1; //-1表示为空 } //处理右子树 if(c2 != '-') { trees2[i].R = c2-'0'; checked[trees2[i].R] = true; }else{ trees2[i].R = -1; } } //找到树根 for(int i=0; i<N; i++) { if(!checked[i]) { root2 = i; break; } } if(isomorphism(root1,root2)){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }

2、树的层次遍历并输出叶子结点

题目 03-树2 List Leaves 分析 其实本题的的思路很简单，就是读入数据后建树，层次遍历，并输出叶子结点。我的代码 // // main.cpp // ListLeaves // #include <iostream> #include <queue> using namespace std; struct TreeNode{ int left; //-1 means NULL int right; }; const int maxn = 10; struct TreeNode tree[maxn]; queue<int> myQueue; void printLeaves(int root){ // 层序遍历，输出叶子结点 myQueue.push(root); bool flag = false; while (!myQueue.empty()) { int node = myQueue.front(); myQueue.pop(); // 访问该结点 if(tree[node].left==-1 && tree[node].right==-1){ if(flag){ cout<<" "<<node; }else{ cout<<node; flag = true; } } //左右非空子树入队 if(tree[node].left != -1) myQueue.push(tree[node].left); if(tree[node].right != -1) myQueue.push(tree[node].right); } cout<<endl; } int main(int argc, const char * argv[]) { int N,root = -1; char c1,c2; bool checked[maxn]; //freopen("test.txt", "r", stdin); cin>>N; //必须都先全部初始化为false，不能在下面初始化，因为可能在赋值之后修改值 for(int i=0; i<N; i++) checked[i] = false; for(int i=0; i<N; i++){ cin>>c1>>c2; if(c1 != '-'){ tree[i].left = c1-'0'; checked[tree[i].left] = true; }else{ tree[i].left = -1; } if(c2 != '-'){ tree[i].right = c2-'0'; checked[tree[i].right] = true; }else{ tree[i].right = -1; } } for(int i=0; i<N; i++){ if(!checked[i]){ root = i; //cout<<root<<endl; break; } } printLeaves(root); return 0; }