1

私はBSTの次の実装を持っています：

struct BstNode
{
    int value;
    BstNode* leftSubnode;
    BstNode* rightSubnode;

    BstNode(int value)
    {
        this->value = value;
        this->leftSubnode = this->rightSubnode = nullptr;
    }
};

struct BstTree
{
    BstNode* root;
};

ご覧のとおり、前任者（現在のノードの親）へのポインターがありません。追加/表示メソッドの実装に問題はありませんが、構造からノードを削除する方法がわかりません。左右のノードへのポインタしかない場合、それを行う可能性はありますか？BstTreeすべてのメソッドは、構造に対してではなく、構造に対して実装する必要があることに注意してくださいBstNode（教師から受け取ったタスクのため）。

4

1 に答える 1

2

このようなものは、特定の要件に適応し、空白を埋めます

void remove(BstTree& tree, int value)
{
   BstNode* parent = nullptr;
   BstNode* node = tree.root;
   while (node)
   {
      if (node->value == value)
      {
         if (parent)
         {
            // remove node using the parent pointer
         }
         else
         {
            // remove the root node
         }
         return;
      }
      if (value < node->value)
      {
         // go down left branch
         parent = node;
         node = node->leftSubNode;
      }
      else
      {
         // go down right branch
         parent = node;
         node = node->rightSubNode;
      }
   }
}
于 2012-10-28T10:24:06.583 に答える