Как отслеживать количество узлов в поддереве каждый раз при вставке узла - PullRequest
Новая
       3

Как отслеживать количество узлов в поддереве каждый раз при вставке узла

0 голосов
/ 07 апреля 2020

У меня есть следующий код, который подсчитывает количество поддеревьев для каждого узла 

int count(struct bstnode *root) {
  if(root == NULL) {
    return 0;
  }
  else {
    return 1 + count(root->left) + count(root->right);
  }
}

Я также написал код для вставки узла, и он работает правильно, но я не знаю, как обновить и отслеживать счет каждый раз? 

  void bst_insert(int i, struct bst *tree) {
  assert(tree);
  struct bstnode *node = tree->root;
  struct bstnode *parent = NULL;
  while (node) {
    if (node->item == i) {
      return;
    }
    parent = node;
    if (i < node->item) {
      node = node->left;
    } else {
      node = node->right;
    }
  }
  if (parent == NULL) {  // tree was empty
    tree->root = new_leaf(i);
  } else if (i < parent->item) {
    parent->left = new_leaf(i);
    parent->left->count++; //= count(parent);
  } else {
    parent->right = new_leaf(i);
    parent->right->count++; //= count(parent);
  }
}
...