Drzewo BST i działania na nim

Question

Witam, ostatnio na studiach dostałem zadanie żeby stworzyć drzewo BST które będzie posiadać dodawanie elementów, usuwanie danego elementu, wyszukiwanie elementu w drzewie(TAK/NIE-jeśli się znajduje), liczenie ilości wystąpień danego elementu w drzewie, zaimplementować inorder, preorder, postorder oraz możliwość wypisania wszystkich elementów tworzących i ich średnią na każdym poziomie drzewa i w każdym jego możliwym poddrzewie. Z pomocą internetu stworzyłem poniższy kod, ale nie zrealizowałem w pełni zadania które miałem wykonać dlatego proszę kogoś o pomoc w dokończeniu programu ponieważ jestem początkującym programistą i nie potrafię sobie z tym poradzić. Dziękuję za każdą pomoc.

#include <iostream>
#include <cstdlib>

using namespace std;

// definicja typu danych reprezentuj¹cego wêze³ drzewa BST
//--------------------------------------------------------

struct BSTNode
{
  BSTNode * p, * left, * right; //p-rodzic, left-lewy potomek, right-prawy potomek
  int key;  //klucz
};

// Definicja klasy obs³uguj¹cej drzewo BST
//----------------------------------------

class BST
{
  public:
    BSTNode * root;  // korzeñ drzewa
    int count;       // liczba wêz³ów

    BST();
    ~BST();
    bool      insert(BSTNode * n);
    BSTNode * search(int key);
    int       maxKey(BSTNode * x);
    int       minKey(BSTNode * x);
    BSTNode * maxNode(BSTNode * x);
    BSTNode * minNode(BSTNode * x);
    BSTNode * pred(BSTNode * x);
    BSTNode * succ(BSTNode * x);
    BSTNode * remove(BSTNode * x);
    void      preorder(BSTNode * x);
    void      inorder(BSTNode * x);
    void      postorder(BSTNode * x);
    void      walk(BSTNode * x);
    void      coutBSTcount();
};

// **********************************************
// *** Definicje funkcji sk³adowych klasy BST ***
// **********************************************

// Konstruktor klasy BST
//----------------------

BST::BST()
{
  root = NULL;
  count = 0;
}

// Destruktor klasy BST
//---------------------

BST::~BST()
{
  while(root) delete(remove(root));
}

// Wstawia element do struktury BST
//---------------------------------

bool BST::insert(BSTNode * n)
{
  BSTNode * y, * x = root;

  y = n->left = n->right = NULL;

  while(x)
  {
    if(n->key == x->key)
    {
      delete n;
      return false;
    }
    y = x;
    x = (n->key < x->key) ? x->left : x->right;
  }

  n->p = y;

  if(!y) root = n;
  else if(n->key < y->key) y->left  = n;
  else                     y->right = n;

  count++;
  return true;
}

// Wyszukuje element wg wartoœci klucza
//-------------------------------------

BSTNode * BST::search(int key)
{
  BSTNode * x = root;

  while((x) && (x->key != key))
    x = (key < x->key) ? x->left : x->right;

  return x;
}

// Zwraca masymaln¹ wartoœæ klucza
//--------------------------------

int BST::minKey(BSTNode * x)
{
  while(x->left) x = x->left;
  return x->key;
}


// Zwraca minimaln¹ wartoœæ klucza
//--------------------------------

int BST::maxKey(BSTNode * x)
{
  while(x->right) x = x->right;
  return x->key;
}


// Zwraca wêze³ z maksymalnym kluczem
//-----------------------------------

BSTNode * BST::minNode(BSTNode * x)
{
  while(x->left) x = x->left;
  return x;
}


// Zwraca wêze³ z minimalnym kluczem
//----------------------------------

BSTNode * BST::maxNode(BSTNode * x)
{
  while(x->right) x = x->right;
  return x;
}


// Zwraca wêze³ poprzednika
//-------------------------

BSTNode * BST::pred(BSTNode * x)
{
  if(x->left) return maxNode(x->left);

  BSTNode * y;

  do
  {
    y = x;
    x = x->p;
  } while(x && (x->right != y));

  return x;
}


// Zwraca wêze³ nastêpnika
//------------------------

BSTNode * BST::succ(BSTNode * x)
{
  if(x->right) return minNode(x->right);

  BSTNode * y;

  do
  {
    y = x;
    x = x->p;
  } while(x && (x->left != y));

  return x;
}


// Usuwa element x ze struktury BST. Zwraca usuniêty wêze³
//--------------------------------------------------------

BSTNode * BST::remove(BSTNode * x)
{
  BSTNode * y = x->p, * z;

  if((x->left) && (x->right))
  {
    z = (rand() % 2) ? remove(pred(x)) : remove(succ(x));
    z->left = x->left;   if(z->left)  z->left->p  = z;
    z->right = x->right; if(z->right) z->right->p = z;
    count++;
  }
  else z = (x->left) ? x->left : x->right;

  if(z) z->p = y;

  if(!y) root = z;
  else if(y->left == x) y->left = z; else y->right = z;

  count--;
  return x;
}


// Przechodzi przez BST metod¹ preorder
//-------------------------------------

void BST::preorder(BSTNode * x)
{
  if(x)
  {
    cout << x->key << endl;  // tutaj przetwarzamy bie¿¹cy wêze³
    preorder(x->left);
    preorder(x->right);
  }
}

// Przechodzi przez BST metod¹ inorder
//------------------------------------

void BST::inorder(BSTNode * x)
{
  if(x)
  {
    inorder(x->left);
    cout << x->key << endl;  // tutaj przetwarzamy bie¿¹cy wêze³
    inorder(x->right);
  }
}

// Przechodzi przez BST metod¹ postorder
//--------------------------------------

void BST::postorder(BSTNode * x)
{
  if(x)
  {
    postorder(x->left);
    postorder(x->right);
    cout << x->key << endl;  // tutaj przetwarzamy bie¿¹cy wêze³
  }
}

// Przechodzi przez drzewo wypisuj¹c zawartoœæ wêz³ów
//---------------------------------------------------

void BST::walk(BSTNode * x)
{
  cout << x->key << " : Left-> ";
  if(x->left) cout << x->left->key;
  else        cout << "BRAK";
  cout << ", Right-> ";
  if(x->right) cout << x->right->key;
  else         cout << "BRAK";
  cout << endl;
  if(x->left)  walk(x->left);
  if(x->right) walk(x->right);
}


// Wypisuje do cout liczbê wêz³ów drzewa BST
//------------------------------------------

void BST::coutBSTcount()
{
  cout << "\nLiczba wezlow drzewa BST : " << count << endl << endl;
}

// **********************************
// *** Funkcje obs³ugi opcji menu ***
// **********************************


// Dodaje nowe wêz³y do drzewa BST
//--------------------------------

void add(BST * T)
{
  cout << "Dodawanie nowych wezlow do drzewa BST\n"
          "-------------------------------------\n\n";
  T->coutBSTcount();
  cout << "Podaj liczbe wezlow do utworzenia, a nastepnie wprowadz odpowiednia\n"
          "liczbe kluczy nowych wezlow.\n\n";

  int i,n;

  BSTNode * x;

  cin >> n;
  for(i = 0; i < n; i++)
  {
    x = new BSTNode;
    cin >> x->key;
    T->insert(x);
  }

  cout << endl;
  T->walk(T->root);
  T->coutBSTcount();
}

// Usuwa wêze³ o zadanym kluczu
//-----------------------------

void del(BST * T)
{
  cout << "Usuwanie wezla drzewa BST o zadanym kluczu\n"
          "------------------------------------------\n\n";
  T->coutBSTcount();

  BSTNode * x;
  int key;

  cout << "Podaj klucz usuwanego wezla : "; cin >> key;

  x = T->search(key);

  if(x)
  {
    delete T->remove(x);
    cout << endl;
    if(T->root) T->walk(T->root);
    T->coutBSTcount();
  }
  else cout << "\nBrak wezla o takim kluczu\n";
}

// Sprawdza, czy drzewo zawiera wêze³ o zadanym kluczu
//----------------------------------------------------

void check(BST * T)
{
  cout << "Sprawdzenie obecnosci wezla o danym kluczu w drzewie BST\n"
          "--------------------------------------------------------\n\n"
          "Podaj klucz wezla : ";

  int key;

  cin >> key;

  cout << endl;

  if(T->search(key)) cout << "Wezel znaleziony.\n";
  else               cout << "W drzewie BST brak wezla o podanym kluczu\n";
}

// Znajduje minimalny i maksymalny klucz
//--------------------------------------

void minmax(BST * T)
{
  cout << "Znajdowanie minimalnego i maksymalnego klucza w drzewie BST\n"
          "-----------------------------------------------------------\n\n"
          "Klucz minimalny  : " << T->minKey(T->root) << endl <<
          "Klucz maksymalny : " << T->maxKey(T->root) << endl;
}


// Znajduje poprzednik wêz³a o zadanym kluczu
//-------------------------------------------

void pred(BST * T)
{
  cout << "Znajdowanie poprzednika w drzewie BST\n"
          "-------------------------------------\n\n"
          "Podaj klucz wezla : ";
  int key;
  BSTNode * x;

  cin >> key;
  cout << endl;

  x = T->search(key);

  if(x)
  {
    x = T->pred(x);
    if(x) cout << "Poprzednikiem [" << key << "] jest " << x->key << endl;
    else  cout << "Wezel [" << key << "] nie posiada poprzednika\n";
  }
  else cout << "Wezel o podanym kluczu nie istnieje w drzewie BST\n";
}


// Znajduje nastêpnik wêz³a o zadanym kluczu
//------------------------------------------

void succ(BST * T)
{
  cout << "Znajdowanie nastepnika w drzewie BST\n"
          "------------------------------------\n\n"
          "Podaj klucz wezla : ";
  int key;
  BSTNode * x;

  cin >> key;
  cout << endl;

  x = T->search(key);

  if(x)
  {
    x = T->succ(x);
    if(x) cout << "Nastepnikiem [" << key << "] jest " << x->key << endl;
    else  cout << "Wezel [" << key << "] nie posiada nastepnika\n";
  }
  else cout << "Wezel o podanym kluczu nie istnieje w drzewie BST\n";
}


// Przechodzi przez drzewo algorytmem preorder
//--------------------------------------------

void preorder(BST * T)
{
  cout << "Przechodzenie drzewa BST algorytmem preorder\n"
          "--------------------------------------------\n\n";
  T->preorder(T->root);
}

// Przechodzi przez drzewo algorytmem inorder
//--------------------------------------------

void inorder(BST * T)
{
  cout << "Przechodzenie drzewa BST algorytmem inorder\n"
          "-------------------------------------------\n\n";
  T->inorder(T->root);
}

// Przechodzi przez drzewo algorytmem postorder
//--------------------------------------------

void postorder(BST * T)
{
  cout << "Przechodzenie drzewa BST algorytmem postorder\n"
          "---------------------------------------------\n\n";
  T->postorder(T->root);
}

// **********************
// *** Program g³ówny ***
// **********************

main()
{
  BST * T = new BST();
  int choice;

  do
  {
    system("cls"); // w Linuxie wstaw clear
    cout << "Test funkcji obslugi drzew poszukiwan binarnych\n"
            "===============================================\n\n"
            "Wybor Funkcja\n"
            "-------------\n"
            " [0]  Koniec\n"
            " [1]  Dodaj wezly\n"
            " [2]  Usun wezel\n"
            " [3]  Sprawdz obecnosc wezla\n"
            " [4]  Wezel min i max\n"
            " [5]  Poprzednik\n"
            " [6]  Nastepnik\n"
            " [7]  Preorder\n"
            " [8]  Inorder\n"
            " [9]  Postorder\n"
            "--------------\n"
            "Twoj wybor : ";
    cin >> choice;
    system("cls");
    switch(choice)
    {
      case 1 : add(T);       break;
      case 2 : del(T);       break;
      case 3 : check(T);     break;
      case 4 : minmax(T);    break;
      case 5 : pred(T);      break;
      case 6 : succ(T);      break;
      case 7 : preorder(T);  break;
      case 8 : inorder(T);   break;
      case 9 : postorder(T); break;
    }
    if((choice >= 1) && (choice <= 9))
    {
      cout << endl;
      system("pause");
    }
  } while(choice);

  delete T;
}

 

Comments

Czego konkretnie nie zrealizowałeś?

---

brakuje liczenia ilości wystąpień danego elementu oraz wypisywania wszystkich elementów tworzących i ich średniej na każdym poziomie drzewa i w każdym możliwym poddrzewie. Mógłbyś spróbować dodać te funkcje?