二叉查找树 POJ Falling Leaves

2019-11-08 03:06:56

字体：大中小

来源：转载

供稿：网友

原题描述（我的翻译版）：这里写图片描述图1显示了字母二叉树的图形表示。熟悉字母二叉树概念的人可以跳过接下来的定义，切入正题。字母二叉树满足下面两条之一： 1. 它可以是空树， 2. 它可以有一个根节点，该节点以；一个字母作为数据并且指向左子树和右子树。左子树和右子树也是字母二叉树。在字母二叉树的图形表示中： 1. 空树完全省略 2. 每一个节点都代表: 一个字母，左子树不为空将该节点和左子树相连，右子树不为空将该节点和右子树相连，叶子节点就是左右子树为空的节点。图1中的B, D, H, P和Y为叶子节点。问题：在字母二叉查找树上考虑以下操作顺序：删除叶子节点，并列出数据删除，重复这个过程直到树为空，从树的左下方开始，我们产生树的显示序列，然后通过删除数据的叶子节点使得树为空。

节点删除如下： BDHPY CM GQ K 给个图：这里写图片描述你的问题是通过这些序列，输出原树的先序遍历。输入：输入将包含一个或多个数据集。每个数据集是一行或多行大写字母的序列。该行包含在上述阶段中从二叉搜索树中移除的叶子节点。一行的字母将按字母顺序排列。数据集是由一行只有一个星号（“*”）分离。最后一个数据集后面是一行只包含一个美元的符号（$）。输入中没有空格或空行。输出：对于每个输入数据集，有一个唯一的二叉搜索树对应产生的叶子节点的序列。输出一行即那棵树的先序遍历，不能有空格。输入样例： BDHPY CM GQ K * AC B

$ 输出样例： KGCBDHQMPY BAC 大意是让我们对每一个数据集建立一个二叉树，这个二叉树是很特殊的，它是一个二叉查找树（观察左右子树与根结点的关系，左子树比其小，右子树大），所以我们不难写出代码，这个题是一道二叉查找树的基础例题。代码如下：

#include<cstdio>#include<string>#include<queue>#include<iostream>using namespace std;struct node{ char data; node* lch; node* rch;}*root;void insert(node *&root,char x){ if(root==NULL) { root=new node; root->data=x; root->lch=NULL;//一定要对左右子树赋初值NULL root->rch=NULL; return; } if(root->data==x) return; else { if(x-'A'>root->data-'A') { insert(root->rch,x); } if(x-'A'<root->data-'A') { insert(root->lch,x); } }}void fir(node *root){ if(root==NULL) return; else { PRintf("%c",root->data); fir(root->lch); fir(root->rch); }}int main(){ string str,s; int i,len; node *root=NULL; while(1) { while(cin>>s&&s!="*"&&s!="$") { str=str+s;//string这个库函数有合并两个字符串的功能，这里对一个数据集全部合并成一个串。 } len=str.length(); for(i=len-1;i>=0;i--)//注意是倒序 insert(root,str[i]); fir(root); if(s=="$") break; root=NULL;//还原初始值来读入下一个 str.erase(); printf("/n"); } return 0; }

上一篇：求递归的方式求n的阶乘

下一篇：串口2