tree

# 目次

# 木の表現

struct Node {
int key;
Node *parent, *left, *right;
}

Node *root, *NIL;


# ノードの追加

void insert(int key) {
Node *x = root;
Node *y = NIL;
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;
}
}

if (y == NIL) {
root = z;
return;
}

z->parent = y;
if (key < y->key) {
y->left =z;
} else {
y->right = z;
}
}


# 走査

void preorder(Node *node) {
if (node == NIL) return;
cout << " " << node->key;
preorder(node->left);
preorder(node->right);
}


# 検索

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 tDelete(Node *z) {
Node *y, *x;

if (z->left == NIL || z->right == NIL) y = z;
else y = tSuccessor(z);

if (y->left != NIL) {
x = y->left;
} else {
x = y->right;
}

if (x != NIL) {
x->parent = y->parent;
}

if (y->parent == NIL) {
root = x;

} else {
if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
}

if (y != z) {
z->key = y->key;
}

free(y);
}


リモートフリーランス。ウェブサービス、スマホアプリエンジニア。

お仕事のご依頼・お問い合わせはこちら