临沂专业网站建设设计公司,智慧团建网站登录密码,优秀企业门户网站建设,域名和服务器多少钱题目链接#xff1a;http://poj.org/problem?id1577
题目大意#xff1a; 二叉查找树按照叶子节点#xff0c;从下往上抹去该树#xff0c;给出抹除字符序列#xff0c;求该二叉树#xff0c;并前序打印
解题思路#xff1a; 最后抹除的是根节点#xff0c;把抹除的…题目链接http://poj.org/problem?id1577
题目大意 二叉查找树按照叶子节点从下往上抹去该树给出抹除字符序列求该二叉树并前序打印
解题思路 最后抹除的是根节点把抹除的字符序列逆序插入到一棵空的二叉查找树就是答案。
AC代码
/*** description: poj1577,告知一层层的叶子节点求二叉查找树* author: michael ming* date: 2019/5/18 23:24* modified by: */
#include iostream
#include vector
using namespace std;
struct node
{char ch;node *left, *right;node(char ch):ch(ch),left(NULL),right(NULL){}
};
class BST
{
public:node* root;BST():root(NULL){}void insert(char ch){node *p root, *prev;while(p ! NULL){prev p;if(ch p-ch)p p-left;elsep p-right;}if(root NULL){root new node(ch);return;}if(ch prev-ch)prev-left new node(ch);elseprev-right new node(ch);}void del(){del(root);}void del(node* p){if(p ! NULL){del(p-left);del(p-right);delete p;}}void preOrderPrint(node* p){if(p ! NULL){cout p-ch;preOrderPrint(p-left);preOrderPrint(p-right);}}
};
bool saveChToStr(string str)
{bool flag;char ch;while(cin.get(ch)){if(ch *){flag true;break;}else if(ch $){flag false;break;}if(ch \n)continue;str.push_back(ch);}return flag;
}
int main()
{bool flag;do{string str;BST tree;flag saveChToStr(str);for(int i str.length()-1; i 0; --i){tree.insert(str[i]);}tree.preOrderPrint(tree.root);cout endl;tree.del();}while(flag);return 0;
}
