С++ Дерево

2075 / C++ / Дерево

З однією структурою

#include <iostream>

using namespace std;

struct Tree {
  int a;
  Tree* left = nullptr;
  Tree* right = nullptr;
};

void ShowTree(Tree* tmp) {
  if (tmp != nullptr)
  {
    ShowTree(tmp->left);
    cout << tmp->a << endl;
    ShowTree(tmp->right);
  }
}

int main()
{

  Tree t1;
  t1.a = 25;

  Tree t2;
  t2.a = 15;

  Tree t3;
  t3.a = 50;

  Tree t4;
  t4.a = 3;

  Tree t5;
  t5.a = 20;

  Tree t6;
  t6.a = 60;

  t1.left = &t2;
  t1.right = &t3;

  t2.left = &t4;
  t2.right = &t5;

  t3.right = &t6;

  ShowTree(&t1);

  system("pause");
  return 0;
}

З класом і структурою

#include<iostream>

using namespace std;

class BST
{
  struct node
  {
    int data;
    node* left;
    node* right;
  };

  node* root;

  node* makeEmpty(node* t)
  {
    if (t == nullptr)
      return nullptr;     {
      makeEmpty(t->left);
      makeEmpty(t->right);
      delete t;
    }
    return nullptr;
  }

  node* insert(int x, node* t)
  {
    if (t == nullptr)
    {
      t = new node;
      t->data = x;
      t->left = t->right = nullptr;
    }
    else if (x < t->data)
      t->left = insert(x, t->left);
    else if (x > t->data)
      t->right = insert(x, t->right);
    return t;
  }

  node* findMin(node* t)
  {
    if (t == nullptr)
      return nullptr;
    else if (t->left == nullptr)
      return t;
    else
      return findMin(t->left);
  }

  node* findMax(node* t)
  {
    if (t == nullptr)
      return nullptr;
    else if (t->right == nullptr)
      return t;
    else
      return findMax(t->right);
  }

  node* remove(int x, node* t)
  {
    node* temp;
    if (t == nullptr)
      return nullptr;
    else if (x < t->data)
      t->left = remove(x, t->left);
    else if (x > t->data)
      t->right = remove(x, t->right);
    else if (t->left && t->right)
    {
      temp = findMin(t->right);
      t->data = temp->data;
      t->right = remove(t->data, t->right);
    }
    else
    {
      temp = t;
      if (t->left == nullptr)
        t = t->right;
      else if (t->right == nullptr)
        t = t->left;
      delete temp;
    }

    return t;
  }

  void inorder(node* t)
  {
    if (t == nullptr)
      return;
    inorder(t->left);
    cout << t->data << " ";
    inorder(t->right);
  }

  node* find(node* t, int x)
  {
    if (t == nullptr)
      return nullptr;
    else if (x < t->data)
      return find(t->left, x);
    else if (x > t->data)
      return find(t->right, x);
    else
      return t;
  }

 public:
  BST()
  {
    root = nullptr;
  }

  ~BST()
  {
    root = makeEmpty(root);
  }

  void insert(int x)
  {
    root = insert(x, root);
  }

  void remove(int x)
  {
    root = remove(x, root);
  }

  void display()
  {
    inorder(root);
    cout << endl;
  }

  void search(int x)
  {
    root = find(root, x);
  }
};

 

int main()
{
  BST t;
  t.insert(5);
  t.insert(2);
  t.insert(3);
  t.insert(1);
  t.insert(7);
  t.display();

  t.remove(5);
  t.display();

  t.remove(5);
  t.display();

  t.remove(7);
  t.display();

  system("pause");
  return 0;
}