Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- struct tree
- {
- int key;
- tree *right, *left, *parent;
- int countLeft, countRight;
- tree()
- {
- countLeft = countRight = 0;
- parent = right = left = NULL;
- }
- };
- tree* tStart = NULL, *tFin = NULL;
- bool flag = false;
- tree *v = NULL;
- int MAX = -2147483647;
- bool addElem(tree* &t, int &n)
- {
- if (t != NULL)
- {
- if (n < t->key)
- {
- t->countLeft++;
- if (t->left)
- return addElem(t->left, n);
- else
- {
- t->left = new tree;
- t->left->key = n;
- t->left->parent = t;
- }
- }
- else if (n > t->key)
- {
- t->countRight++;
- if (t->right)
- return addElem(t->right, n);
- else
- {
- t->right = new tree;
- t->right->key = n;
- t->right->parent = t;
- }
- }
- else return false;
- }
- else
- {
- t = new tree();
- t->key = n;
- }
- return true;
- }
- bool checkStruct(tree* tr1, tree* tr2)
- {
- if (tr1==NULL && tr2==NULL)
- return true;
- else if ((tr1 == NULL && tr2 != NULL) || (tr1 != NULL && tr2 == NULL))
- return false;
- else return checkStruct(tr1->left, tr2->left)*checkStruct(tr1->right, tr2->right);
- }
- void findV(tree *tr1, tree *tr2, tree* &v)
- {
- if (tr1->countLeft != tr2->countLeft && tr1->countRight == tr2->countRight)
- {
- if (!checkStruct(tr1->right, tr2->right))
- return;
- if (tr1->left == NULL && tr2->left != NULL)
- {
- v = tr2->left;
- }
- else findV(tr1->left, tr2->left, v);
- }
- else if (tr1->countLeft == tr2->countLeft && tr1->countRight != tr2->countRight)
- {
- if (!checkStruct(tr1->left, tr2->left))
- return;
- if (tr1->right == NULL && tr2->right != NULL)
- {
- v = tr2->right;
- }
- else findV(tr1->right, tr2->right, v);
- }
- else if (checkStruct(tr2->left, tr1) || checkStruct(tr2->right, tr1))
- {
- v = tr2;
- }
- }
- bool leftDel(tree* v)
- {
- while (v = v->parent)
- {
- if (v->parent)
- {
- if (v->parent->left == v)
- {
- if (v->parent->right)
- MAX = v->parent->key;
- return true;
- }
- }
- else return false;
- }
- return false;
- }
- bool isLeft(tree* t)
- {
- while (t = t->right)
- {
- if (t->left)
- return true;
- }
- return false;
- }
- int main()
- {
- ifstream in("tst.in");
- char str[10];
- int k=0;
- int col1=0, col2=0;
- bool flag = false;
- while (true)
- {
- in >> str;
- if (!in)
- break;
- if (!strcmp(str, "*"))
- {
- flag = true;
- continue;
- }
- k = atoi(str);
- if (flag)
- {
- if (addElem(tFin, k))
- col2++;
- }
- else
- {
- if (addElem(tStart, k))
- col1++;
- }
- }
- in.close();
- ofstream out("tst.out");
- if ((abs(col1 - col2) != 1) || (!(tStart&&tFin)))
- {
- out << "NO";
- out.close();
- return 0;
- }
- if (col1 > col2)
- {
- tree* tmp = tStart;
- tStart = tFin;
- tFin = tmp;
- }
- findV(tStart, tFin, v);
- if (!v)
- {
- out << "NO";
- out.close();
- return 0;
- }
- else out << "YES\n";
- MAX = v->key;
- if (v == tFin)
- {
- MAX = v->key;
- }
- else if (v->parent->right == v)
- {
- if (v->right)
- {
- if (!isLeft(v))
- {
- leftDel(v);
- }
- }
- else leftDel(v);
- }
- else if (v->parent->left == v)
- {
- if (v->parent->right)
- {
- if (!isLeft(v))
- {
- MAX = v->parent->key;
- }
- }
- else if (isLeft(v))
- {
- }
- else
- {
- while (v = v->parent)
- {
- MAX = v->key;
- if (v->right || !v->parent)
- break;
- if (v->parent->right == v)
- {
- if (v->right == NULL)
- leftDel(v);
- break;
- }
- }
- }
- }
- out << MAX << endl;
- out.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement