Обход в бинарном дереве поиска - PullRequest
Новая
       0

Обход в бинарном дереве поиска

0 голосов
/ 26 октября 2019

У меня есть функция, которая должна удалить вершину из дерева двоичного поиска. В конечном счете, фактическое удаление выполняется во 2-й функции (называемой удалением), но моя функция deleteVertex, приведенная ниже, должна добраться до правильной вершины, которую нужно удалить, прежде чем передавать затем позиции в функцию удаления. Есть несколько ситуаций для рассмотрения, но у меня есть некоторые ошибки компилятора в случае 2 ниже. Случай 2 для случая, когда дерево имеет только 2 вершины. В этом случае есть несколько вспомогательных сценариев:

  • Вершина, которую нужно удалить, является корнем - я позаботился о

  • Вершина, которую нужно удалить, являетсяchild

    • В этом сценарии я должен сначала определить, находится ли дочерняя вершина слева или справа от Root. Затем я перехожу к вершине перед вызовом удаления. Visual Studio выдает мне ошибку неинициализированной локальной переменной C4700 для V и Parent в строках кода: 

      Root = V;
remove(V, Parent);

Любая помощь приветствуется. Вот полная функция ... 

// PURPOSE: Deletes a vertex that has E as its element.
// PARAM: element E to be removed
// ALGORITHM: First we must find the vertex then call Remove 
void BST::DeleteVertex(elem_t E)
{
    cout << "Trying to delete " << E << endl;

    Vertex* V;       // the current vertex
    Vertex* Parent;  // Parent will always point to V's parent

    // case 1: Lonely Root  --------------------
    if ((E == Root->Elem) && (Root->Left == NULL) && (Root->Right == NULL))
    {
        cout << "...deleting the lonely root" << endl;
        delete Root;
        Root = NULL;
        return;
    }  // only the Root was there and deleted it

    // case 2:  One Subtree Root ----------------
    if ((Root->Left == NULL && Root->Right != NULL) || (Root->Right == NULL && Root->Left != NULL)) {       //if what you want to delete is the root
        cout << "... deleting the root with just one child" << endl;
        if (E == Root->Elem) {                                                                              //Need to delete the root
            Root = V;
            remove(V, Parent);
        }
        else {                                                                                              //If need to delete the child
            if (Root->Right == NULL) {                                                                      //If our child is on the left side
                Parent = V;
                V = V->Left;
                remove(V, Parent);
            }
            else if (Root->Left == NULL) {                                                                  //If our child is on the right side
                Parent = V;
                V = V->Right;
                remove(V, Parent);
            }
        }

    }

    // Case 3: ---- Otherwise deleting something else  --------------
    else {
        V = Root;  // start with the root to look for E
        Parent = NULL;  // above the V so does not point to anything yet

        // going down the tree looking for E
        while (V != NULL)
        {
            if (E == V->Elem)   // found it
            {
                cout << "...removing " << V->Elem << endl;
                remove(V, Parent);
                return;
            }
            else
                if (E < V->Elem)
                {
                    cout << "...going to the left" << endl;
                    Parent = V;
                    V = V->Left;
                }
                else
                {
                    cout << "...going to the right" << endl;
                    Parent = V;
                    V = V->Right;
                }

        }// end of while

        // reached NULL  -- did not find it
        cout << "Did not find the key in the tree." << endl;

    }   //end of Case 3
} // end of DeleteVertex
...