简单的搜索二叉树插入和寻找。以后再说删除。另外给几个输入数据。
10 insert 30 insert 88 insert 12 insert 1 insert 20 find 12 insert 17 insert 25 find 16 print
下面是源代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> using namespace std; struct Node { int key; Node *right, *left, *parent; }; Node *root, *NIL; void inssert(int k) { Node *y = NIL; Node *x = root; Node *z; z = (Node *)malloc(sizeof(Node)); z->key = k; z->left = NIL; z->right = NIL; while (x != NIL) { y = x; if (z->key < x->key) { x = x->left; } else { x = x->right; } } z->parent = y; if (y == NIL) { root = z; } else { if (z->key < y->key) { y->left = z; } else { y->right = z; } } } void inorder(Node *u) { if (u == NIL) return; inorder(u->left); printf(" %d", u->key); inorder(u->right); } void perorder(Node *u) { if (u == NIL) return; printf(" %d", u->key); perorder(u->left); perorder(u->right); } Node *find(Node *u, int k) { while (u != NIL&&k != u->key) { if (k < u->key) u = u->left; else u = u->right; } return u; } int main() { int n, i, x; string com; scanf("%d", &n); for (i = 0; i < n; i++) { cin >> com; if (com[0] == 'f') { scanf("%d", &x); Node *t = find(root, x); if (t != NIL) printf("yes\n"); else printf("no\n"); } else if (com == "insert") { scanf("%d", &x); inssert(x); } else if (com == "print") { inorder(root); printf("\n"); perorder(root); printf("\n"); } } system("pause"); return 0; }
