构建二叉树,层序,移位
#include<iostream> #include<vector> #include<stack> #include<algorithm> using namespace std; class MyNode { public: int val; MyNode* pre; MyNode* left; MyNode* right; int deep; MyNode(int v, MyNode* p, MyNode* l, MyNode* r, int d) :val(v), pre(p), left(l), right(r), deep(d) { //cout << val << "," << deep << ","; //if (pre == NULL)cout << "null" << ","; //else cout << pre->val << ","; //if (left == NULL)cout << "null" << ","; //else cout << left->val << ","; //if (right == NULL)cout << "null" << ","; //else cout << right->val << ","; //cout << endl; } static bool cmp(MyNode* a, MyNode* b) { if (a->deep < b->deep)return true; if (a->deep > b->deep)return false; return a->val < b->val; } }; int main() { int n, k; cin >> n >> k; vector<int> arr(n, 0); for (int i = 0; i<n; ++i) { cin >> arr[i]; } if (n <= 2) { for (int i = 0; i + 1<n; ++i) { cout << arr[i] << " "; } cout << arr.back(); return 0; } MyNode* root = new MyNode(arr[0], NULL,NULL, NULL,1); vector<MyNode*> tree; tree.push_back(root); for (int i = 1; i < n; ++i) { MyNode* cur = root; while (true) { if (arr[i] < cur->val) { if (cur->left == NULL) { MyNode* newn = new MyNode(arr[i], cur, NULL, NULL,cur->deep+1); tree.push_back(newn); cur->left = newn; break; } else { cur = cur->left; } } else if (arr[i] >= cur->val) { if (cur->right == NULL) { MyNode* newn = new MyNode(arr[i], cur, NULL, NULL, cur->deep + 1); tree.push_back(newn); cur->right = newn; break; } else { cur = cur->right; } } } } sort(tree.begin(), tree.end(), MyNode::cmp); vector<int> tmp; int pred = 1; for (int i = 0; i<n; ++i) { if (tree[i]->deep != pred) { for (int j = 0; j < tmp.size(); ++j) { cout << tmp[(j - k + tmp.size()) % tmp.size()] << " "; } tmp.clear(); pred = tree[i]->deep; } tmp.push_back(tree[i]->val); } for (int j = 0; j < tmp.size(); ++j) { cout << tmp[(j - k + tmp.size()) % tmp.size()] << " "; } return 0; }
全部评论
(1) 回帖