兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

9.2 二分探索木:挿入

問題に書いてあった解説どおりの実装です。delete を呼んでないのが気持ち悪いですが、まあ良いでしょう。良くないか。

#include <iostream>
#include <cstdio>
#include <memory>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

struct Tree {
  Node* root;  
  
  Tree() : root(nullptr) {};
};

static void insert(Tree& tree, int v) {
  Node* z = new Node(v);
  Node* x(tree.root);
  Node* y(nullptr);
  while (x != nullptr) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if (y == nullptr) {
    tree.root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

void preorderWalk(const Node* node) {
  if (node->key == -1) {
    return;
  }
  cout << " " << node->key;
  if (node->left != nullptr) {
    preorderWalk(node->left);
  }
  if (node->right != nullptr) {
    preorderWalk(node->right); 
  }
}

void inorderWalk(const Node* node) {
  if (node->key == -1) {
    return;
  }
  if (node->left != nullptr) {
    inorderWalk(node->left);
  }
  cout << " " << node->key;

  if (node->right != nullptr) {
    inorderWalk(node->right); 
  }
}

static Tree TREE;

int main() {
  int n;
  cin >> n;

  string command;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(TREE, v);
    } else {
      inorderWalk(TREE.root);
      cout << endl;
      preorderWalk(TREE.root);
      cout << endl;
    }
  }

  return 0;
}