American Heritage
Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear `tree in-order’ and `tree pre-order’ notations.
Your job is to create the `tree post-order’ notation of a cow’s heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.
Here is a graphical representation of the tree used in the sample input and output:
C
/
/
B G
/ /
A D H
/
E F
The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.
The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.
The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.
PROGRAM NAME: heritage
INPUT FORMAT
Line 1: |
The in-order representation of a tree. |
Line 2: |
The pre-order representation of that same tree. |
SAMPLE INPUT (file heritage.in)
ABEDFCHG
CBADEFGH
OUTPUT FORMAT
A single line with the post-order representation of the tree.
SAMPLE OUTPUT (file heritage.out)
AEFDBHGC
思路:一、已知二叉树的前序序列和中序序列,求解树。
1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
2、求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树,重复1、2、3步,直到所有的节点完成定位。
/*
ID:nealgav1
LANG:C++
PROG:heritage
*/
#include
#include
using namespace std;
const int mm=55;
ifstream cin("heritage.in");
ofstream cout("heritage.out");
class node
{
public:char v;
node*l,*r;
node(){l=r=NULL;}
}*pn;
char pre[mm],mid[mm],post[mm];
///i为在pre中的位置,j为在mid的开始端,len为长度
void creattree(node*&p,int i,int j,int len)
{ if(lenv=pre[i];
int m=strchr(mid,pre[i])-mid;
creattree(p->l,i+1,j,m-j);
creattree(p->r,i+m-j+1,m+1,len-(m-j)-1);
}
void postvisit(node*p)
{
if(p!=NULL)
{
postvisit(p->l);
postvisit(p->r);
coutv;
}
}
int main()
{
while(cin>>mid>>pre)
{ pn=NULL;
creattree(pn,0,0,strlen(mid));
postvisit(pn);
cout
USER: Neal Gavin Gavin [nealgav1]
TASK: heritage
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3364 KB]
Test 2: TEST OK [0.000 secs, 3364 KB]
Test 3: TEST OK [0.000 secs, 3364 KB]
Test 4: TEST OK [0.000 secs, 3364 KB]
Test 5: TEST OK [0.000 secs, 3364 KB]
Test 6: TEST OK [0.000 secs, 3364 KB]
Test 7: TEST OK [0.000 secs, 3364 KB]
Test 8: TEST OK [0.000 secs, 3364 KB]
Test 9: TEST OK [0.000 secs, 3364 KB]
All tests OK.
YOUR PROGRAM (‘heritage’) WORKED FIRST TIME! That’s fantastic
— and a rare thing. Please accept these special automated
congratulations.
Here are the test data inputs:
------- test 1 ----
ABEDFCHG
CBADEFGH
------- test 2 ----
F
F
------- test 3 ----
BCAD
ABCD
------- test 4 ----
GOLEAFS
SFAELOG
------- test 5 ----
GSHBAQTPM
ABGHSPQTM
------- test 6 ----
AUBYCVDZEWFXGTH
ZYUABVCDXWEFTGH
------- test 7 ----
ABDCJHKILMNPOQFEGRS
ABCDEFHJIKLMNOPQGRS
------- test 8 ----
GFDIHKLJMBNESRTPOQAUCWVZYX
ABDFGHIJKLMENOPRSTQCUVWXYZ
------- test 9 ----
EHGDIFJLKMBNCOQSPRAWUXZYTV
ABDEGHFIJKLMCNOPQSRTUWXYZV
Keep up the good work!
Thanks for your submission!
American Heritage
Russ Cox
Here’s one way: We use a recursive procedure to generate the actual binary tree. Once we have the tree, we execute a postorder traversal to print the node values.
#include
#include
#include
#include
FILE *fout;
typedef struct Tree Tree;
struct Tree {
int c;
Tree *left;
Tree *right;
};
Tree*
mktree(int c, Tree *left, Tree *right)
{
Tree *t;
t = (Tree*)malloc(sizeof *t);
assert(t);
t->c = c;
t->left = left;
t->right = right;
return t;
}
/*
* Pre and in point at strings of length len
* that describe the same tree, in pre-order
* and in-order traversals. Return a
* corresponding binary tree.
*/
Tree*
prein2tree(char *pre, char *in, int len)
{
char *p;
int llen, rlen;
assert(strlen(pre)>=len && strlen(in)>=len);
if(len == 0)
return NULL;
/*
* The first character of the preorder traversal is the root.
* If we find the root in the inorder traversal, then everything
* to its left is on the left side, and everything to its right on the
* right side. Recur on both sides.
*/
p = strchr(in, pre[0]);
assert(p != NULL);
assert(p-in left);
postorder(t->right);
fprintf(fout, "%c", t->c);
}
void
main(void)
{
FILE *fin;
char pre[50], in[50];
fin = fopen("heritage.in", "r");
fout = fopen("heritage.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%s %s", in, pre);
postorder(prein2tree(pre, in, strlen(pre)));
fprintf(fout, "n");
exit(0);
}
From Greg Price:
We don't need to reconstruct the original tree explicitly for this
problem. Instead, we use a recursive function that plucks the root from
the start of the preorder traversal, uses it to divide the inorder
traversal, calls itself recursively on the left and right subtrees, and
outputs the root.
#include
#include
ifstream fin("heritage.in");
ofstream fout("heritage.out");
const short maxn = 26 + 2;
short len;
char in[maxn], pre[maxn];
void
makepost(short ina, short inb, short prea, short preb)
{
char root;
short rt_in;
short lsize, rsize;
if (ina == inb) // Null tree
return;
root = pre[prea];
// Find root in inorder
for (rt_in = ina; rt_in value] otherwise element e is in rightsubtree.Now inserting: O(1) in O(N) recursive call - worth case = O(N).All algorithm is O(N^2) and before was O(N^3) - worth case. And O(Nlog N) now, before O(N^2) - average case; N = number of cowsMy implementation (I'm using index into the array instead of pointer):/*
LANG: C++
PROG: heritage
*/
#include
#include
FILE *in,*out;
char ino[200], preo[200];
int place[255];
struct NODE{
int left, right;
char name;
};
NODE node[200];
int count = 1;
//return true if who is before the value of node[n] in inorder; O(1)
bool isBefore(char who, int n){
return place[who]
#include
using namespace std;
ofstream out ("heritage.out");
void
recursex (string sin, string spre) {
int i;
if (sin.length() > sin >> spre;
recursex (sin, spre);
out
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 目前可用的ChatGPT网站
chatgpt.qdymys.cn
gpttalk
chatgpt-cn.co
bing.com
总结本文意在整理可用gpt-3.5、gpt-4.0等网站。 本文主要是方便自己翻阅,如对您也有所帮助,不胜荣幸~ 文章目录 chatgpt.qdymys.cn gpttalk chatgpt-cn.co bing.com 总结 chatgpt.qdymys.cn …