aoj

# ALDS1_8_B Tree - Binary Search Tree 2

ALDS1_8_B Tree - Binary Search Tree 2
Feb. 2, 2020, 1:52 p.m.

## 解答

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 struct Node { int key; Node *parent, *left, *right; }; Node *root, *NIL; void insert(int key) { Node *y = NIL; Node *x = root; Node *z = (Node *)malloc(sizeof(Node)); z->key = key; z->left = NIL; z->right = NIL; while (x != NIL) { y = x; if (key < x->key) { x = x->left; } else { x = x->right; } }; z->parent = y; if (y == NIL) { root = z; return; } if (key <= y->key) { y->left = z; } else { y->right = z; } }; bool find(Node *node, int key) { Node* cur = node; while (cur != NIL && cur->key != key) { if (key < cur->key) { cur = cur->left; } else { cur = cur->right; } } return cur != NIL; }; void preorder(Node *node) { if (node == NIL) return; cout << " " << node->key; preorder(node->left); preorder(node->right); } void inorder(Node *node) { if (node == NIL) return; inorder(node->left); cout << " " << node->key; inorder(node->right); } int main() { int n, x; string op; cin >> n; for (int i=0; i> op; if (op == "insert") { cin >> x; insert(x); continue; } else { inorder(root); cout << endl; preorder(root); cout << endl; continue; } } return 0; }