数据结构实验之二叉树一：树的同构
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;struct tree
{struct tree *left, *right;char str;
};
struct node
{char x[10];char y[10];
};
bool vis[30];int rootNum( struct node a[], int n )
{int i;for ( i = 0;i < n; i++ ){if ( a[i].x[0] >= '0'&&a[i].x[0] <= '9' ) //目的查找root1的根节点vis[a[i].x[0]-'0'] = true;if ( a[i].y[0] >= '0'&&a[i].y[0] <= '9' )vis[a[i].y[0]-'0'] = true;}for ( i = 0; i < n; i++ ){if ( vis[i] == false )return i;}
}struct tree *create(struct node a[], int r, char ch[12][10])
{struct tree *root = new tree;root->str = ch[r][0];root->left = root->right = NULL;if ( a[r].x[0] != '-' )root->left = create( a, a[r].x[0]-'0', ch );if ( a[r].y[0] != '-' )root->right = create( a, a[r].y[0]-'0', ch );return root;
}bool compa(struct tree *root1, struct tree *root2)//比较两颗树是否同构
{if ( !root1 && !root2 )return 1;if ( (root1 && root2) && root1->str == root2->str )if ( ( compa(root1->left, root2->left) && compa(root1->right,root2->right) ) ||( compa(root1->left, root2->right) && compa(root1->right,root2->left ) ) )return 1;return 0;
}int main()
{int n, m, xx, yy, i;while ( ~scanf ( "%d", &n ) ){char ch1[12][10], ch2[12][10];node a[12], b[12];memset( vis, false, sizeof(vis) );for ( i = 0;i < n; i++ )scanf ( "%s %s %s", ch1[i], a[i].x, a[i].y );xx = rootNum(a, n); //根节点为ch1[i];memset( vis, false, sizeof(vis) );scanf ( "%d", &m );for ( i = 0;i < m; i++ )scanf ( "%s %s %s", ch2[i], b[i].x, b[i].y );yy = rootNum(b, m);if ( n != m ) //如果节点数都不相同就不用比较了{printf ( "No\n" );continue;}if ( n == 0 && m == 0 ) //这里我被亮瞎了，我服...十多发WA.做出来以后发现这也可以....{printf ( "Yes\n" );continue;}struct tree *root1 = create(a, xx, ch1);struct tree *root2 = create(b, yy, ch2);printf ( compa ( root1,root2 ) ? "Yes\n" : "No\n" );}
}
数据结构实验之二叉树二：遍历二叉树
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;struct node
{char data;struct node *left, *right;
};
char st[60];
int cnt;struct node *create()
{struct node *root;if ( st[++cnt] == ',' )root = NULL;else{root = (struct node *)malloc(sizeof(struct node));root->data = st[cnt];root->left = create();root->right = create();}return root;
}void midOrder(struct node *root)
{if ( root ){midOrder(root->left);printf ( "%c", root->data);midOrder(root->right);}
}void afterOrder(struct node *root)
{if ( root ){afterOrder(root->left);afterOrder(root->right);printf ( "%c", root->data);}
}int main()
{while ( ~scanf ( "%s", st ) ){cnt = -1;struct node *root;root = create();midOrder(root);printf ( "\n" );afterOrder(root);printf ( "\n" );}return 0;
}
数据结构实验之二叉树三：统计叶子数
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;struct tree
{char data;struct tree *left, *right;
};
char str[60];
int cnt;
int sum;struct tree *create()
{struct tree *root = new tree;if ( str[++cnt] == ',' )return root = NULL;root->data = str[cnt];root->left = create();root->right = create();return root;
}void Sum(struct tree *root)
{if ( root ){if ( !root->right && !root->left )sum++;Sum(root->left);Sum(root->right);}
}int main()
{while ( ~scanf ( "%s", str ) ){cnt = -1;sum = 0;struct tree *root = new tree;root = create();Sum(root);printf ( "%d\n", sum );}
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;struct tree
{char data;struct tree *left, *right;
};struct tree *create (int len, char *st1, char *st2)
{struct tree *root = new tree;int i;if ( len == 0 )return root = NULL;for ( i = 0;i < len; i++ ){if ( st1[0] == st2[i] )break;}root->data = st1[0];root->left = create(i, st1+1, st2);root->right = create(len-i-1, st1+i+1, st2+i+1);return root;
}int deep ( struct tree *root )
{int sum = 0;if ( root ){int sum1 = deep ( root->left );int sum2 = deep ( root->right );sum = max(sum1, sum2)+1;}return sum;
}int main()
{int n;char st1[60], st2[60];while ( ~scanf ( "%d", &n ) ){scanf ( "%s %s", st1, st2 );struct tree *root = new tree;root = create(n, st1, st2);int sum = deep ( root );printf ( "%d\n", sum );}
}
数据结构实验之二叉树五：层序遍历
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;struct tree
{char data;struct tree *left, *right;
};
char str[60];
int cnt;
int sum;struct tree *create()
{struct tree *root = new tree;if ( str[++cnt] == ',' )return root = NULL;root->data = str[cnt];root->left = create();root->right = create();return root;
}void leve(struct tree *root)
{struct tree *tr[60];int in = 0, out = 0;tr[in++] = root;while ( in > out ){if ( tr[out] ){printf ( "%c", tr[out]->data );tr[in++] = tr[out]->left;tr[in++] = tr[out]->right;}out++;}
}int main()
{int n;scanf ( "%d", &n );while ( n-- ){scanf ( "%s", str );cnt = -1;sum = 0;struct tree *root = new tree;root = create();leve(root);printf ( "\n" );}
}
数据结构实验之二叉树六：哈夫曼编码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;struct cmp
{bool operator()(int &a, int &b){return a > b; //优先队列从小到大排列}
};
priority_queue<int, vector<int>, cmp>q;
int b[300];int main()
{int i;int ma1,ma2;char st[10002];while ( ~scanf ( "%s", st ) ){memset( b, 0, sizeof(b) );int len = strlen(st);for ( i = 0;i < len; i++ )b[st[i]]++;for ( i = 0;i < 300; i++ ){if ( b[i] != 0 )q.push(b[i]);}int sum = 0;while ( q.size() != 1 ){ma1 = q.top();q.pop();ma2 = q.top();q.pop();sum = ma1+ma2+sum;q.push(ma1+ma2);}q.pop();printf ( "%d %d %.1lf\n", len*8, sum, (double)len*8/(double)sum );}
}#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;struct tree
{char data;struct tree *left, *right;
};
char str[60];
int cnt;
int sum;struct tree *create()
{struct tree *root = new tree;if ( str[++cnt] == ',' )return root = NULL;root->data = str[cnt];root->left = create();root->right = create();return root;
}void leve(struct tree *root)
{struct tree *tr[60];int in = 0, out = 0;tr[in++] = root;while ( in > out ){if ( tr[out] ){tr[in++] = tr[out]->left;tr[in++] = tr[out]->right;}if ( tr[out] ){if ( !tr[out]->left && !tr[out]->right )printf ( "%c", tr[out]->data );}out++;}
}int main()
{while ( ~scanf ( "%s", str ) ){cnt = -1;sum = 0;struct tree *root = new tree;root = create();leve(root);printf ( "\n" );}
}代码菜鸟，如有错误，请多包涵！！！
如有帮助记得支持我一下，谢谢！！！