题目描述
根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为:左子树，根结点，右子树。
输入描述
由大小写字母、左右大括号、逗号组成的字符串:
1、字母代表一个节点值，左右括号内包含该节点的子节点。
2、左右子节点使用逗号分隔，逗号前为空则表示左子节点为空,没有逗号则表示右子节点
为空。
3、二叉树节点数最大不超过100。
注:输入字符串格式是正确的，无需考虑格式错误的情况。
输出描述
输出一个字符串，为二叉树中序遍历各节点值的拼接结果。
示例：
输入：a{b{d,e{g,h{,I}}},c{f}｝
输出：dbgehiafc
#include
#include
#include
using namespace std;
struct TreeNode {
char val;
TreeNode *left;
TreeNode *right;
};
TreeNode* creatNode(char ch) {
TreeNode *node = new TreeNode;
memset(node, 0, sizeof(TreeNode));
node->val = ch;
node->left = NULL;
node->right = NULL;
return node;
}
void show(TreeNode* node) {
if (node == NULL) {
// cout << "noth" << endl;
return;
}
//前序
// printf("%c",node->val);
// show(node->left);
// show(node->right);
//中序
show(node->left);
printf("%c", node->val);
show(node->right);
}
int main() {
char sz[50];
printf("qaweawen");
// scanf("%s", sz);
std::cin.getline(sz, 50);
// sz << cin;
// char sz[50] = "a{b{d,e{g,h{,i}}},c{f}}";
int i = 0;
int len = strlen(sz);
TreeNode* root;
TreeNode* temp;
stack
root = creatNode(sz[0]);
temp = root;
stk.push(temp);
for (i = 1; i < len; i++) {
if (sz[i] == '{' && sz[i + 1] != ',') {
i++;
stk.push(temp);
temp->left = creatNode(sz[i]);
temp = temp->left;
}
else if (sz[i] == '{' && sz[i + 1] == ',') {
i = i + 2;
stk.push(temp);
temp->right = creatNode(sz[i]);
temp = temp->right;
}
else if (sz[i - 1] != '{' && sz[i - 1] != '}' && sz[i] == ',') {
i++;
temp = stk.top();
stk.pop();
temp->right = creatNode(sz[i]);
temp = temp->right;
}
else if(sz[i] == ',') {
i++;
stk.push(temp);
temp->right = creatNode(sz[i]);
temp = temp->right;
}
else if (sz[i] == '}') {
temp = stk.top();
stk.pop();
}
}
show(root);
return 0;
}
字符串朴素匹配
#include
#include
#include
using namespace std;
int main() {
char str11[100] = {NULL};
char strlow[20] = { NULL};
printf("input to strn");
cin.getline(str11,99);
cin.getline(strlow, 19);
int S1 = strlen(str11);
int S2 = strlen(strlow);
printf("S1=%d S2=%dn", S1,S2);
int i = 0;
int j = 0;
while (i < S1 && j < S2 ) {
if (str11[i] == strlow[j]) {
++i;
++j;
}
else {
i = i - j + 1;
j = 0;
}
}
if (j >= S2) {
printf("==is=%d", i - j + 1);
}
else {
printf("no==");
}
插入排序
#include
using namespace std;
int main() {
int a[20] = { 1,3,4,5,99,
44,555,222,111,44,
55,66,55,8,55,
5,11,666,8888,818};
int count = 0;
for (int i = 0; i <= 20 - 1; i++) {
int j = i - 1;
int key = a[i];
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
count++;
}
a[j + 1] = key;
}
for (int i = 0; i < 20; i++) {
printf(" %d ", a[i]);
}
printf(" n count = %d ", count);
}
1.递归
int Fibon1(int n){
if (n == 1 || n == 2){
return 1;
} else{
return Fibon1(n - 1) + Fibon1(n - 2);
}
}
int main(){
int n = 0;
int ret = 0;
scanf("%d", &n);
ret = Fibon1(n);
printf("ret=%d", ret);
return 0;
}
数组二叉树
#include
#include
#include
using namespace std;
struct treeNode {
int data;
treeNode* left;
treeNode* right;
};
treeNode* createTreeNode(int da)
{
treeNode* node = (treeNode*)malloc(sizeof(treeNode));
node->data = da;
node->left = NULL;
node->right = NULL;
return node;
}
treeNode* createTreeFromArray(int arr[], int len)
{
// 数组为空
if (len < 1) return NULL;
// 用指针数组保存每个节点的地址，初始化NULL
treeNode** nodesArr = (treeNode**)malloc(sizeof(treeNode*) * len);
memset(nodesArr, 0, sizeof(treeNode*) * len);
// 分配根节点
nodesArr[0] = createTreeNode(arr[0]);
// 扫描数组创建整棵二叉树
for (int i = 0; i < len; i++)
{
int leftIdx = 2 * i + 1; // 当前节点的左孩子下标
int rightIdx = 2 * i + 2; // 当前节点的右孩子下标
if (leftIdx < len && arr[leftIdx] >= 0)
{
nodesArr[leftIdx] = createTreeNode(arr[leftIdx]); // 创建左孩子，并存入数据
nodesArr[i]->left = nodesArr[leftIdx]; // 设置节点i的左孩子
}
if (rightIdx < len && arr[rightIdx] >= 0)
{
nodesArr[rightIdx] = createTreeNode(arr[rightIdx]); // 创建右孩子，并存入数据
nodesArr[i]->right = nodesArr[rightIdx]; //设置节点i的右孩子
}
}
// 返回根节点
return nodesArr[0];
}
void show(treeNode *node) {
if (node == NULL) return;
show(node -> left);
printf("%d ", node->data);
show(node->right);
}
int main() {
int len[20] = { 2,3,4,1,3,5,5555,212,333,12,1234,111,5551,11,2,3,5,4,1 };
treeNode *node = createTreeFromArray(len, 20);
show(node);
return 0;
}
合并排序
#include
using namespace std;
void dispsolution(char a[], int n) { //输出一个解
printf("(");
for (int i = 0; i < n -1; i++)
printf("%c,", a[i]);
printf("%c)n", a[n - 1]);
}
void allis(char list[], int k, int m) {
if (k == m) {
dispsolution(list, k);
} else
for (int i = k; i < m; i++) {
swap(list[k], list[i]);
allis(list, k + 1, m);
swap(list[k], list[i]);
}
}
int main() {
char list[10] = { NULL };
list[0] = 'a';
list[1] = 'b';
list[2] = 'c';
list[3] = '1';
list[4] = '2';
int len = strlen(list);
allis(list, 0, 3);
// printf(" %c %c %c n", list[0], list[1], list[2]);
return 0;
}
元素存储11111
#include
#include
#include
#include
//统计字符串中每个字符出现的次数
//typedef pair
//
//bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {
// return lhs.second < rhs.second;
//}
//
//struct CmpByValue {
// bool operator()(const PAIR& lhs, const PAIR& rhs) {
// return lhs.second < rhs.second;
// }
//};
//int main()
//{
//
//
// map
// name_score_map["LiMin"] = 90;
// name_score_map["ZiLinMi"] = 79;
// name_score_map["BoB"] = 92;
// name_score_map.insert(make_pair("Bing", 99));
// name_score_map.insert(make_pair("Albert", 86));
// //把map中元素转存到vector中
// vector
// sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());
// // sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value);
// for (int i = 0; i != name_score_vec.size(); ++i) {
// cout << name_score_vec[i].first <<" " << name_score_vec[i].second << endl;
//
// }
// return 0;
//}
typedef pair
bool cmp(const PA& lhs, const PA& rhs) {
return lhs.second > rhs.second;
}
int main()
{
string s;
cin >> s;
map
for (auto& i : s)
{
m[i]++;
}
for (auto& i : m)
{
cout << i.first << ' ' << i.second << endl;
}
map
for (iter; iter != m.end(); iter++) {
cout << iter->first << endl;
}
int c = 0;
vector
sort(vec.begin(), vec.end(), cmp );
for (int i = 0; i != vec.size(); ++i) {
cout << vec[i].first << " " << vec[i].second << endl;
}
//system("pause");
return 0;
}
#include
#include
#include
#include
//统计字符串中每个字符出现的次数
//typedef pair
//
//bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {
// return lhs.second < rhs.second;
//}
//
//struct CmpByValue {
// bool operator()(const PAIR& lhs, const PAIR& rhs) {
// return lhs.second < rhs.second;
// }
//};
//int main()
//{
//
//
// map
// name_score_map["LiMin"] = 90;
// name_score_map["ZiLinMi"] = 79;
// name_score_map["BoB"] = 92;
// name_score_map.insert(make_pair("Bing", 99));
// name_score_map.insert(make_pair("Albert", 86));
// //把map中元素转存到vector中
// vector
// sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());
// // sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value);
// for (int i = 0; i != name_score_vec.size(); ++i) {
// cout << name_score_vec[i].first <<" " << name_score_vec[i].second << endl;
//
// }
// return 0;
//}
typedef pair
bool cmp( PAIR& lhf, PAIR& rhf) {
return lhf.second > rhf.second;
}
// bbbdddeeeeeeewwwhhh
int main()
{
string s;
cin >> s;
map
for (auto& i : s) {
m[i]++;
}
for (auto& i : m) {
cout << i.first <<" " << i.second << endl;
}
cout << " 1123123123" << endl;
vector
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < vec.size(); i++) {
cout << vec[i].first << " " << vec[i].second << endl;
}
//system("pause");
return 0;
}
