#include<iostream>
#include <cstdio>
using namespace std;
typedef struct BiTNode //一颗二叉树的结构体
{
int data;
struct BiTNode* lchild, * rchiild;
}BiTNode, * BiTree;
void CreatBiTree(BiTree& T, char s[], int& i) {
if (s[i] == '#') {
T = NULL;
}
else {
T = new BiTNode;
T->data = int(s[i]) - 60;
CreatBiTree(T->lchild, s, ++i);
CreatBiTree(T->rchiild, s, ++i);
}
}
void insert(BiTree& T, int value)//这是二叉排序树的插入 跟此要求无关
{
BiTNode* node = new BiTNode;//创建一个节点
node->data = value;
node->rchiild = NULL;
node->lchild = NULL;
if (T == NULL)//判断树是不是空树{
T = node;
}
else {//不是空树
BiTNode* temp = T;//从树根开始
while (temp != NULL)
{
if (value < temp->data)//小于就进左儿子
{
if (temp->lchild == NULL)
{
temp->lchild = node;
return;
}
else {//继续判断
temp = temp->lchild;
}
}
else {//否则进右儿子
if (temp->rchiild == NULL)
{
temp->rchiild = node;
return;
}
else {//继续判断
temp = temp->rchiild;
}
}
}
}
return;
}
int num(BiTree T) {//递归求最大带权和 即递归到最底层从下往上筛选
if (T == NULL) return 0;
if (T->lchild == NULL && T->rchiild == NULL) return T->data;
if (num(T->lchild) >= num(T->rchiild))
return num(T->lchild) + T->data;
return num(T->rchiild) + T->data;
}
}
int main() {
char s[200];
BiTree T;
cin >> s;
int i = -1;
CreatBiTree(T, s, ++i);
cout << num(T) << endl;
return 0;
}
输入输出
ab#d##c#e##
117