VPF::конструктор и деструктор бинарного дерева

lenarano

Дата 13.5.2015, 13:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Ребята, помогите с конструктором и деструктором для моего дерева.
Значения для дерева ключ и строка берутся из файла. Я так понимаю, что мне нужно просто сделать так, что бы в начальных значениях был не "мусор".
Тут в заголовочном файле вроде все правильно

Код


//TreeNode.h
#pragma once
#ifndef __TREENODE_H__
#define __TREENODE_H__
#include <iomanip>
#include <string>


class TreeNode 
{  private:
    int key; 
    std::string polinom;
    TreeNode *leftPtr,*rightPtr;
    public:
   TreeNode();
   ~TreeNode(); 
   void show(TreeNode *&Tree);
   void add_node(int x,std::string p,TreeNode *&MyTree);
   bool is_palindrome(const std::string &word);
};
#endif

А вот тут нужна помощь, как правильно написать конструктор и деструктор

Код


//TreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


TreeNode::TreeNode() : key(0),leftPtr(0),rightPtr(0),polinom(" ") {} //конструктор
TreeNode::~TreeNode() 
{
    delete ;//???
} 


void TreeNode::show(TreeNode *&Tree) //Функция обхода
{    if (Tree!=NULL) 
{
    show(Tree->leftPtr);
    std::cout<<Tree->key; 
    std::cout<<" ";
    std::cout<<Tree->polinom;
    std::cout<<"\n"; 
    show(Tree->rightPtr); 
}
}
void TreeNode::add_node(int x,std::string p,TreeNode *&MyTree) //Функция добавления звена в дерево
{...//...}

Добавлено через 13 минут и 26 секунд
Я в интернете нашла только такие варианты

Код


Node(int v_usel):usel(v_usel),pr(0),pl(0){}

Но я так понимаю, что мне они не подходят , из-за того, что я добавляю все из файлов. Нашла, что в таких случаях можно обойтись без конструктора. Главное, что бы значения указателей и полей были проинициализированы 0. Но я знаю, что преподаватель будет их требовать(((

lenarano

Дата 13.5.2015, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Вот на всяких случай, что я делаю в main

Код


//KodTreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"


int main()
{  
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    TreeNode *Tree=NULL;  
    TreeNode Derevo();
    std::ifstream imput_fail_key;
    std::ifstream imput_fail_stroki;
    imput_fail_key.open("key.txt", std::ios::in);
    imput_fail_stroki.open("stroki.txt", std::ios::in);
    if (!imput_fail_key.is_open()||!imput_fail_stroki.is_open()) // если файл не открыт
        std::cout << "Файл не может быть открыт!\n"; // сообщить об этом
    std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
    while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
    {  
        int k;
        std::string line;
        imput_fail_key>> k; // считали число из файла
        getline(imput_fail_stroki, line);// считали строку из файла
        std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
        Derevo.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0
    }
    std::cout << std::endl;
    std::cout << "Исходное дерево:\n";
    imput_fail_key.close();
    imput_fail_stroki.close();
    Derevo.show(Tree); 
    std::cout << "Реализуем функцию, которая оставит в дереве только полиндромы:\n";
    /*(до тех пор пока встречаются строки в TreeNode.polinom)
    if(is_palindrome.polinom возвращает 1)
    оставляем в дереве
    else (удаляем)
    Вывод дерева.*/

    std::cin.get();
    return 0;
}

При том как у меня сейчас написан конструктор, ругается на эти строчки
Derevo.show(Tree); //Derevo().show(Tree); ?
Derevo.add_node(k, line.substr(0, 20), Tree);

Еще хотела спросить, насколько нужна вот эта строчка в main.
TreeNode *Tree=NULL;

lenarano

Дата 13.5.2015, 14:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Вот эта функция работает, как деструктор-удаляет все. Может ее просто втавить в сам деструктор?

Код


 void cleanup (TreeNode *Tree) // Удаление всех узлов дерева в обходе с отложенной выборкой
  { if(!Tree) return;
     if(Tree->leftPtr)
             { cleanup(Tree->leftPtr);
       Tree->leftPtr = 0;
    }
    if(Tree->rightPtr != 0 )
    { cleanup(Tree->rightPtr);
       Tree->rightPtr = 0;
    }
    delete Tree;
  }

lenarano

Дата 13.5.2015, 14:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Нет, наверное, эта функция не подойдет. Оно ведь обходить все дерево и удаляет все узлы. А нам нужен конструктор и деструктор для 1 узла... Не понимаю.

feodorv

Дата 13.5.2015, 16:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

У Вас есть два разных типа объектов - само дерево и узел этого дерева. При наивном программировании, конечно, можно объединить эти два объекта в один гибридный, но тогда и возникают разные проблемы, в том числе и с конструктором/деструктором.

Для объекта типа дерево определяется указатель на корень дерева и методы по добавлению/удалению узла:

Код


class Tree
{
  private:
    Node *root;
    void cleanup( Node *node );
  public:
    Tree() : root(0) {}
    ~Tree() { cleanup( root ); }
    void add( Node *node );
};

А для объекта типа узел - данные узла (которые должны быть разрушены в деструкторе) и указатели на левого и правого потомка:

Код


class Node
{
  private:
    Node *left, *right;
  public:
    int key; 
    std::string polinom;
    Node() : key(0), left(0), right(0) {}
    Node( int k, const std::string &p) : key(k), polinom(p), left(0), right(0) {}
    ~Node() { left = right = 0; }
}

Так потихоньку можно будет и к шаблонам перейти...

Это сообщение отредактировал(а) feodorv - 13.5.2015, 16:33

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 00:32 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Начала делать и у меня полезли такие ошибки(( В основном в //TreeNode.cpp. Мое дерево, объявленное дружественным не видит элементы узла. Уверена, что перепутала параметры в функциях. Сама буду разбираться долго Может укажете на ошибки?

/

Код


/TreeNode.h
#pragma once
#ifndef __TREENODE_H__
#define __TREENODE_H__
#include <iomanip>
#include <string>

class Tree //Дерево
{
private:
    Node *root;
    void cleanup( Node *node );
    public:
    Tree(){};
    ~Tree() {};
    void add( Node *node );
    void show(Tree *&MyTree);
    void add_node(int x,std::string p,Tree *&MyTree);
    friend bool is_palindrome(const std::string &stroka);
};

class Node//Узел
{
private:
    Node *leftPtr, *rightPtr;
public:
    int key; 
    std::string polinom;
    Node(){};
    Node( int k, const std::string &p){};
    ~Node(){};
    friend class Tree;
};


#endif

Код


//TreeNode.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


  Tree::Tree() : root(0) {}
  Tree::~Tree() { cleanup( root );}
  Node::Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node::Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  Node::~Node() { leftPtr = rightPtr = 0; }


void Tree::show(Tree *&MyTree) //Функция обхода
{    if (MyTree!=NULL) 
{
    show(MyTree->leftPtr);
    std::cout<<MyTree->key; 
    std::cout<<" ";
    std::cout<<MyTree->polinom;
    std::cout<<"\n"; 
    show(MyTree->rightPtr); 
}
}
void Tree::add_node(int x,std::string p,Tree *&MyTree) //Функция добавления звена в дерево
{static int count=1;
if(count<=10)
{if (NULL==MyTree)  //если дерево пустое
{
    MyTree=new Tree(); 
    MyTree->key=x;
    MyTree->polinom=p;
    MyTree->leftPtr=MyTree->rightPtr=NULL;
    count++;
}
if (x<MyTree->key)   
{    if (MyTree->leftPtr!=NULL) add_node(x,p,MyTree->leftPtr); 
else 
{
    MyTree->leftPtr=new Tree;  
    MyTree->leftPtr->leftPtr=MyTree->leftPtr->rightPtr=NULL; 
    MyTree->leftPtr->key=x;
    MyTree->leftPtr->polinom=p;
    count++;
}
}
if (x>MyTree->key)   
{
    if (MyTree->rightPtr!=NULL) add_node(x,p,MyTree->rightPtr); 
    else 
    {
        MyTree->rightPtr=new Tree;  
        MyTree->rightPtr->leftPtr=MyTree->rightPtr->rightPtr=NULL; 
        MyTree->rightPtr->key=x; 
        MyTree->rightPtr->polinom=p; 
        count++;
    }
}
if (MyTree->key == key) // если ключ повторяется
{ 
    MyTree->key = key;
    MyTree->polinom = p;
}
}
}
bool is_palindrome(const std::string &stroka)
{
    for (size_t i = 0; i < stroka.length()/2; ++i)
    {
        if (tolower(stroka[i]) != tolower(stroka[stroka.length() - i - 1]))
            return false;
    }
    return true;
}


  void Tree::cleanup (Node *node) // Удаление всех узлов дерева в обходе с отложенной выборкой
  { if(!node) return;
     if(node->leftPtr)
             { cleanup(node->leftPtr);
       node->leftPtr = 0;
    }
    if(node->rightPtr != 0 )
    { cleanup(node->rightPtr);
       node->rightPtr = 0;
    }
    delete node;
  }

feodorv

Дата 14.5.2015, 02:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 00:32

)

Сама буду разбираться долго

Я бы сделал так:

Код


#include <Windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <cctype>

class Node
{
private:
  Node *leftPtr, *rightPtr;

public:
  Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  ~Node() { leftPtr = rightPtr = 0; }

  int key;
  std::string polinom;

  bool is_palindrome();
  void show();

  friend class Tree;
};

void Node::show()
{
  std::cout << key << " " << polinom << " " << is_palindrome() << std::endl;
}

bool Node::is_palindrome()
{
  size_t length = polinom.length();

  if( length == 0 ) return false;

  for( size_t i = 0; i < length/2; ++i)
    if( tolower(polinom[i]) != tolower(polinom[length-i-1]) )
      return false;

  return true;
}

class Tree
{
private:
  Node *root;
  int count;

  void cleanup( Node *node );
  void show_recursive( Node *node );

public:
  Tree() : root(0), count(0) {}
  ~Tree() { cleanup( root ); root = 0; count =0; }

  bool add( Node *node );
  void show();
};

void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

void Tree::show_recursive( Node *node )
{
  if( node != NULL )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;

  Node *parent = 0, *current = root;

  while( current != NULL )
  {
    parent = current;
    if( node->key == current->key ) return false;

    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }

  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;

  count++;
  return true;
}

int main( void )
{
  const int keys[20] = { 1, 11, 121, 56765, 2773, 297792, 1220, 5250525,
    10901901, 1092801, 9080, 8778, 70707, 7867, 55555, 1010101, 98, 89, 0, 23 };

  Tree tree;

  for( int i = 0; i < 20; ++i)
  {
    char buf[128];
    sprintf( buf, "%d", keys[i]);

    std::string p( buf );
    Node *node = new Node( keys[i], p);

    if( !tree.add( node ) ) delete node;
  }

  tree.show();
}

Это сообщение отредактировал(а) feodorv - 14.5.2015, 02:14

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 03:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Спасибо большое, стало понятней. Вот как получилось.

Код


//Tree.h
#pragma once
#ifndef __TREE_H__
#define __TREE_H__
#include <iomanip>
#include <string>


class Node//Узел
{
private:
    Node *leftPtr, *rightPtr;
public:
    Node();//конструктор
    Node( int k, const std::string &p);//конструктор с параментами
    ~Node(); //деструктор

    int key; 
    std::string polinom;

    bool is_palindrome();
    void show();

    friend class Tree;
};

class Tree //Дерево
{
private:
    Node *root;
    int count;

    void cleanup( Node *node );
    void show_recursive( Node *node );
public:
    Tree();
    ~Tree();

    bool add( Node *node );
    void show();

};


#endif

Код


//Tree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


  Node::Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node::Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  Node::~Node() { leftPtr = rightPtr = 0; }
  Tree::Tree() : root(0), count(0) {}
  Tree::~Tree() { cleanup( root ); root = 0; count =0; }


 void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

 void Node::show()
{
  std::cout << key << " " << polinom << " " << is_palindrome() << std::endl;
}


void Tree::show_recursive( Node *node )
{
  if( node != NULL )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;
  Node *parent = 0, *current = root;
  while( current != NULL )
  {
    parent = current;
    if( node->key == current->key ) return false;
    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }
  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;
  count++;
  return true;
}

bool Node::is_palindrome()
{
  size_t length = polinom.length();
  if( length == 0 ) return false;
  for( size_t i = 0; i < length/2; ++i)
    if( tolower(polinom[i]) != tolower(polinom[length-i-1]) )
      return false;
  return true;
}

У меня вопрос по main. По заданию я должна открыть 2 файла. Один с числами(которые будут как ключи) и один со строками(часть из них будут полиндромами). Ввести эти данные в дерево причем строка была не более 20 символов. Делала я это с помощью этой функции.

Код


Derevo.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0

А теперь как?

Код


//KodTree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"


int main()
{  
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    
    Tree Wood();
    std::ifstream imput_fail_key;
    std::ifstream imput_fail_stroki;
    imput_fail_key.open("key.txt", std::ios::in);
    imput_fail_stroki.open("stroki.txt", std::ios::in);
    
    std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
    while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
    {  
        int k;
        std::string line;
        imput_fail_key>> k; // считали число из файла
        getline(imput_fail_stroki, line);// считали строку из файла
        std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
        Wood.add_node(k, line.substr(0, 20), Tree);//возвращает 20 символов строки line начиная с позиции 0
    }
    std::cout << std::endl;
    std::cout << "Исходное дерево:\n";
    imput_fail_key.close();
    imput_fail_stroki.close();
    Wood.show(); 
    std::cout << "Реализуем функцию, которая оставит в дереве только полиндромы:\n";
    /*(до тех пор пока встречаются строки в Tree)
    if(is_palindrome возвращает 1)
    оставляем в дереве
    else (удаляем)
    */
    Wood.show(); 
    std::cin.get();
    return 0;
}

feodorv

Дата 14.5.2015, 05:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 03:31

)

Tree Wood();

Это у Вас объявление функции (без параметров, возвращающую экземпляр класса Tree), а не переменной. Наверное, Вы хотели сказать:

Код


Tree Wood;

Цитата(lenarano @ 14.5.2015, 03:31

)

А теперь как?

В моём коде в main все есть. Только для подстроки можно написать так:

Код


std::string p = line.substr(0, 20);
Node *node = new Node( k, p);
if( !tree.add( node ) ) delete node;

Конечно, цикл по добавлению в дерево можно было бы и прервать при достижении 10 добавленных узлов. Чего зря данными раскидываться. Но это как уж Вам будет виднее...

Цитата(lenarano @ 14.5.2015, 03:31

)

else (удаляем)

Ох. Нас ещё ждёт развлечение по удалению узлов дерева smile

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 12:51 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Добавила функцию удаление узла. Вроде правильно.

Код


//Tree.h
#pragma once
#ifndef __TREE_H__
#define __TREE_H__
#include <iomanip>
#include <string>


class Node//Узел
{
private:
    Node *leftPtr, *rightPtr;
public:
    Node();//конструктор
    Node( int k, const std::string &p);//конструктор с параментами
    ~Node(); //деструктор

    int key; 
    std::string polinom;

    bool is_leaf() const;
    Node* destroy(Node *node );
    bool is_palindrome();
    void show();

    friend class Tree;
};

class Tree //Дерево
{
private:
    Node *root;
    int count;

    void cleanup( Node *node );
    void show_recursive( Node *node );
public:
    Tree();
    ~Tree();

    bool add( Node *node );
    void show();
    void add_node(int x,std::string p,Node *node);

};


#endif

Код


//Tree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include <cctype>
#include "TreeNode.h"


  Node::Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node::Node( int k, const std::string &p) : key(k), polinom(p), leftPtr(0), rightPtr(0) {}
  Node::~Node() { leftPtr = rightPtr = 0; }
  Tree::Tree() : root(0), count(0) {}
  Tree::~Tree() { cleanup( root ); root = 0; count =0; }


 void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

 void Node::show()
{
  std::cout << key << " " << polinom << " " << is_palindrome() << std::endl;
}


void Tree::show_recursive( Node *node )
{
  if( node != NULL )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;
  Node *parent = 0, *current = root;
  while( current != NULL )
  {
    parent = current;
    if( node->key == current->key ) return false;
    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }
  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;
  count++;
  return true;
}

bool Node::is_palindrome()
{
  size_t length = polinom.length();
  if( length == 0 ) return false;
  for( size_t i = 0; i < length/2; ++i)
    if( tolower(polinom[i]) != tolower(polinom[length-i-1]) )
      return false;
  return true;
}

bool Node::is_leaf() const
    {
        return (leftPtr == rightPtr) && (leftPtr == NULL);
    }

Node* Node::destroy(Node *node )
{
    if( node ->is_leaf() )//    дерево состоит из одной вершины
    {
        delete node; 
        return 0;
    }
    else
    if( node->leftPtr == 0 )//    левое поддерево пусто
    {
        Node* r = node->rightPtr;//    сохраняем указатель на правое поддерево
        *node = *r;//    копируем состояние узла находящегося справа
        r->leftPtr = 0;//    удаляем узел
        r->rightPtr = 0;
        delete r;
    } 
    else//    левое поддерево не пусто
    {    //    ищем узел являющийся самым правым в левом поддереве
        Node *c = node->leftPtr;//    самый правый узел
        Node *p = node->leftPtr;//    родитель самого правого узла 
        while( c->rightPtr )//    двигаемся по правой ветви левого поддерева
        {
            p = c;
            c = c->rightPtr;
        }
        p->rightPtr = c->leftPtr;//    левое поддерево самого правого узла становиться правым поддеревом родителя
        c->leftPtr = NULL;//    рвем отношение
        node->key = c->key;//    переносим ключ
        node->polinom = c->polinom;//    переносим ключ
        delete c;//    удаляем самый правый узел
    }
    return node;
}

Код


//KodTree.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <Windows.h>
#include <iomanip>
#include "TreeNode.h"


int main()
{  
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    
    Tree Wood;
    std::ifstream imput_fail_key;
    std::ifstream imput_fail_stroki;
    imput_fail_key.open("key.txt", std::ios::in);
    imput_fail_stroki.open("stroki.txt", std::ios::in);
    
    std::cout << "Вывод содержимого файла key.txt и файла stroki.txt. \n";
    while(!imput_fail_key.eof()&&!imput_fail_stroki.eof())
    {   int k;
        std::string line;
        imput_fail_key>> k; // считали число из файла
        getline(imput_fail_stroki, line);// считали строку из файла
        std::cout << k << " " <<line<< std::endl;// напечатали это число и слово
        std::string p = line.substr(0, 20);
        Node *node = new Node( k, p);
        if( !Wood.add( node ) ) delete node;
    }
    std::cout << std::endl;
    std::cout << "Исходное дерево и проверка на полиндромность:\n";
    imput_fail_key.close();
    imput_fail_stroki.close();
    Wood.show(); 
    std::cout << std::endl;
    std::cout << "Реализуем функцию, которая оставит в дереве только полиндромы:\n";
    /*(до тех пор пока встречаются строки в Tree)
    if(is_palindrome возвращает 1)
    оставляем в дереве
    else (удаляем)
    */
    Wood.show(); 
    std::cin.get();
    return 0;
}

Я правильно понимаю, что сейчас нужно реализовать еще одну функцию типа обхода дерева, но добавить в неё, что если не полиндром, но удаляем этот узел?

lenarano

Дата 14.5.2015, 13:50 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Еще хотела спросить. У нас сейчас есть функция bool Node::is_palindrome(), которая читает только слова, т.е. если есть фраза-перевертыш с пробелами, то она возвращает 0. Я создала функцию, которая убирает пробелы из фраз.

Код


void Node::remove_spaces()
{
  size_t length = polinom.length();
  for(int i = 0; i < length; i++)
  {
    if(polinom[i] == ' ') polinom.erase(i,1);
  }
}

А как ее сейчас совместить с нашей bool Node::is_palindrome(), или нужно было просто добавить как-то этот кусок кода в bool Node::is_palindrome().

feodorv

Дата 14.5.2015, 14:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 12:51

)

Добавила функцию удаление узла. Вроде правильно.

Опять же, для наивного программирования за основу взять можно. Но.

Вы удаляете узел из дерева. Не из узла. Почему Node::destroy(Node *node )? Зачем возвращаемое значение? Что Вы потом с ним делать будете?
Родительский узел тоже претерпевает изменения при удалении дочернего узла (у него меняется или rightPtr, или leftPtr). Где эти изменения в коде?
А если удаляемый узел есть root, Вам не кажется, что член класса Tree::root надо подправить?
Вы хотите удалить именно узел node. Почему вместо него из дерева удаляется другой узел в случае leftPtr != 0 && rightPtr != 0?

Что означает это сравнение?

Цитата(lenarano @ 14.5.2015, 12:51

)

return (leftPtr == rightPtr) && (leftPtr == NULL);

Зачем эта функция?

Цитата(lenarano @ 14.5.2015, 12:51

)

void add_node(int x,std::string p,Node *node);

???

Цитата(lenarano @ 14.5.2015, 12:51

)

Да!

Цитата(lenarano @ 14.5.2015, 13:50

)

Так вы невозвратимо испортите изначальную строку. Можно поменять алгоритм определения палиндрома, а можно в функции is_palindrome() создать локальную переменную типа std::string, в неё скопировать первоначальный polinom, в ней же удалить пробелы, и для неё же применить уже имеющийся алгоритм. Тогда никаких remove_spaces() (да ещё и сделанных с ошибками) не понадобиться...

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 14.5.2015, 15:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Цитата

Что означает это сравнение?
Цитата(lenarano @ 14.5.2015, 12:51 Найти цитируемый пост)
return (leftPtr == rightPtr) && (leftPtr == NULL);

я этот алгоритм нашла в нете, просто пробовала адаптировать к моему куску кода. Переделала:
void Tree::destroy(Node *node ). А можно ваш вариант этой функции, но закоментированный, чтобы я могла понять алгоритм удаления узла.

Цитата

А если менять просто алгоритм, то что нужно добавить?Те варианты, которые я использовала влияли на саму строку.

lenarano

Дата 14.5.2015, 15:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Решила поменять алгоритм нахождения полинома. Для того, чтобы не испортить строчку написала так const std::string& stroka. В принципе работает, но считает полиндромом только тогда, когда написано так "а луна канула" и не работает, когда так "А луна канула". Хотя вроде функцию tolower использую. Можно было бы конечно все фразы в файле переписать на строковые буквы. Но все же почему ошибка?

Код


bool Node::is_palindrome(const std::string& stroka)
{
    for(int i=0, j=stroka.size()-1; i < j;)
    {
        if(stroka[i] == ' ')
        {
            ++i;
            continue;
        }
        if(stroka[j] == ' ')
        {
            --j;
            continue;
        }
        if( tolower(stroka[i]) != tolower(stroka[j]) )
        return false;
        ++i;
        --j;
    }
    return true;
}

feodorv

Дата 14.5.2015, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 14.5.2015, 15:57

)

Решила поменять алгоритм нахождения полинома.

Цитата(lenarano @ 14.5.2015, 15:57

)

Хотя вроде функцию tolower использую.

Эх, в виндах все с этим не просто. tolower не отрабатывает на русских буквах, так как не выставлена локальная кодировка. Теоретически, setlocale должна помочь, но как она сочетается с SetConsole*() - без понятия.

Цитата(lenarano @ 14.5.2015, 15:05

)

А можно ваш вариант этой функции, но закоментированный

Я же говорил, что готовится развлечение smile

А как-нибудь более самостоятельно попробовать справиться с заданием?

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 15.5.2015, 01:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Вот, что получилось у меня:

Код


#include <Windows.h>
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <cctype>

class Node
{
private:
  Node *leftPtr, *rightPtr;

public:
  Node() : key(0), leftPtr(0), rightPtr(0) {}
  Node( int k, const std::string &p) : key(k), stroka(p), leftPtr(0), rightPtr(0) {}
  ~Node() { leftPtr = rightPtr = 0; }

  int key;
  std::string stroka;

  bool is_palindrome();
  void show();

  friend class Tree;
};

void Node::show()
{
  std::cout << key << " " << stroka << " " << is_palindrome() << std::endl;
}

char myToLower( char c )
{
  if( c >= 'A' && c <= 'Z' ) return c - 'A' + 'a';

  switch( c )
  {
    case 'А': return 'а';
    case 'Б': return 'б';
    case 'В': return 'в';
    case 'Г': return 'г';
    case 'Д': return 'д';
    case 'Е': return 'е';
    case 'Ж': return 'ж';
    case 'З': return 'з';
    case 'И': return 'и';
    case 'Й': return 'й';
    case 'К': return 'к';
    case 'Л': return 'л';
    case 'М': return 'м';
    case 'Н': return 'н';
    case 'О': return 'о';
    case 'П': return 'п';
    case 'Р': return 'р';
    case 'С': return 'с';
    case 'Т': return 'т';
    case 'У': return 'у';
    case 'Ф': return 'ф';
    case 'Х': return 'х';
    case 'Ц': return 'ц';
    case 'Ч': return 'ч';
    case 'Ш': return 'ш';
    case 'Щ': return 'щ';
    case 'Ъ': return 'ъ';
    case 'Ы': return 'ы';
    case 'Ь': return 'ь';
    case 'Э': return 'э';
    case 'Ю': return 'ю';
    case 'Я': return 'я';
  }

  return c;
}

bool Node::is_palindrome()
{
  size_t length = stroka.length();
  if( length == 0 ) return false;

  for( size_t i = 0, j = length-1; i < j; )
    if( stroka[i] == ' ' )
      ++i;
    else if( stroka[j] == ' ' )
      --j;
    else if( myToLower(stroka[i]) != myToLower(stroka[j]) )
      return false;
    else
      ++i, --j;

  return true;
}

class Tree
{
private:
  Node *root;
  int count;

  void cleanup( Node *node );
  void show_recursive( Node *node );
  void remove( Node *node, Node *parent);
  void remove_non_palindroms_recursive( Node *node, Node *parent);

public:
  Tree() : root(0), count(0) {}
  ~Tree() { cleanup( root ); }

  bool add( Node *node );
  void show();
  void remove_non_palindroms();
};

void Tree::cleanup( Node *node )
{
  if( node != 0 )
  {
    cleanup( node->leftPtr );
    cleanup( node->rightPtr );
    delete node;
  }
}

void Tree::show_recursive( Node *node )
{
  if( node != 0 )
  {
    show_recursive( node->leftPtr );
    node->show();
    show_recursive( node->rightPtr );
  }
}

void Tree::show()
{
  show_recursive( root );
  std::cout << std::endl;
}

bool Tree::add( Node *node )
{
  if( count >= 10 ) return false;

  Node *parent = 0, *current = root;

  while( current != 0 )
  {
    parent = current;
    if( node->key == current->key ) return false;

    if( node->key < current->key )
      current = current->leftPtr;
    else
      current = current->rightPtr;
  }

  if( parent == 0 )
    root = node;
  else if( node->key < parent->key )
    parent->leftPtr = node;
  else
    parent->rightPtr = node;

  count++;
  return true;
}

void Tree::remove( Node *node, Node *parent)
{
  if( node->rightPtr == 0 && node->leftPtr == 0 )
  {
    if( parent == 0 )
      root = 0;
    else if( parent->leftPtr == node )
      parent->leftPtr = 0;
    else
      parent->rightPtr = 0;
  }
  else if( node->rightPtr == 0 )
  {
    if( parent == 0 )
      root = node->leftPtr;
    else if( parent->leftPtr == node )
      parent->leftPtr = node->leftPtr;
    else
      parent->rightPtr = node->leftPtr;
  }
  else if( node->leftPtr == 0 )
  {
    if( parent == 0 )
      root = node->rightPtr;
    else if( parent->leftPtr == node )
      parent->leftPtr = node->rightPtr;
    else
      parent->rightPtr = node->rightPtr;
  }
  else
  {
    Node *c, *p = node;
    for( c = node->rightPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;
    if( p != node )
    {
      p->leftPtr = c->rightPtr;
      c->rightPtr = node->rightPtr;
    }
    c->leftPtr = node->leftPtr;
    if( parent == 0 )
      root = c;
    else if( parent->leftPtr == node )
      parent->leftPtr = c;
    else
      parent->rightPtr = c;
  }

  delete node;
}

void Tree::remove_non_palindroms_recursive( Node *node, Node *parent)
{
  if( node == 0 ) return;

  if( node == parent->leftPtr )
  {
    while( parent->leftPtr != 0 && !parent->leftPtr->is_palindrome() )
      remove( parent->leftPtr, parent);

    if( (node = parent->leftPtr) != 0 )
    {
      remove_non_palindroms_recursive( node->leftPtr, node);
      remove_non_palindroms_recursive( node->rightPtr, node);
    }
  }
  else
  {
    while( parent->rightPtr != 0 && !parent->rightPtr->is_palindrome() )
      remove( parent->rightPtr, parent);

    if( (node = parent->rightPtr) != 0 )
    {
      remove_non_palindroms_recursive( node->leftPtr, node);
      remove_non_palindroms_recursive( node->rightPtr, node);
    }
  }
}

void Tree::remove_non_palindroms()
{
  while( root != 0 && !root->is_palindrome() ) remove( root, 0);

  if( root != 0 )
  {
    remove_non_palindroms_recursive( root->leftPtr, root);
    remove_non_palindroms_recursive( root->rightPtr, root);
  }
}

struct key_value
{
  int key;
  const char *value;
};

struct key_value kvTable[] =
{
  { 0,  "не палиндром" },
  { -10, "нет" },
  { -20, "тоже нет" },
  { 20, "А луна канула" },
  { 30, "а луна канула" },
  { -25, "Вол около колоколов" },
  { 25, "А роза упала на лапу Азора" },
  { -15, "ротор" },
  { 5, "Аргентина манит негра" },
  { 3, "Россия не манит негра" },
  { 0, NULL }
};

int main( void )
{
  Tree tree;

  for( struct key_value *kv = kvTable; kv->value != NULL; kv++)
  {
    std::string p = kv->value;
    Node *node = new Node( kv->key, p);
    if( !tree.add( node ) ) delete node;
  }

  tree.show();

  tree.remove_non_palindroms();
  tree.show();
}

PS Функцию myToLower() блондинка писала, что для данного задания даже в плюс)))

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 15.5.2015, 02:16 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

решила проработать, алгоритм не из форума, взяла отсюда http://www.studfiles.ru/preview/1644497/

Код


void Tree::destroy(Node *node, void Tree::destroy(Node *node, Node *parent )
{
    if (!node) return; //    дерево пустое
    if (!node->leftPtr && !node->rightPtr)
    { 
        delete node;// если удаляемый узел не имеет потомков, допустимо просто убрать его из дерева
        if (parent) parent = 0;//эту строчку не поняла
    }
    else if (!node->leftPtr && node->rightPtr)//если есть только правый узел
    {
        if (parent) parent = node->rightPtr;//эту строчку не поняла
        delete node;
    }
    else if (node->leftPtr && !node->rightPtr)//если есть только левый узел
    {
        if (parent) parent = node->leftPtr;
        delete node;
    }
    else //у узла оба потомка
{//заменить удаленный узел крайним правым узлом дерева из левой ветви.
    Node * temp = node->rightPtr;
while (temp->leftPtr)
temp = temp->leftPtr;
temp->leftPtr = node->leftPtr; 
temp = node;
node = node->rightPtr;
parent = node;
delete temp;
}
}    parent )
{
    if (!node) return; //    дерево пустое
    if (!node->leftPtr && !node->rightPtr)
    { 
        delete node;// если удаляемый узел не имеет потомков, допустимо просто убрать его из дерева
        if (parent) parent = 0;//эту строчку не поняла
    }
    else if (!node->leftPtr && node->rightPtr)//если есть только правый узел
    {
        if (parent) parent = node->rightPtr;//эту строчку не поняла
        delete node;
    }
    else if (node->leftPtr && !node->rightPtr)//если есть только левый узел
    {
        if (parent) parent = node->leftPtr;
        delete node;
    }
    else //у узла оба потомка
{//заменить удаленный узел крайним правым узлом дерева из левой ветви.
    Node * temp = node->rightPtr;
while (temp->leftPtr)
temp = temp->leftPtr;
temp->leftPtr = node->leftPtr; 
temp = node;
node = node->rightPtr;
parent = node;
delete temp;
}
}

Хоть ты тресни не понимаю правильно ли я выбрала параметры у функции и по какому принципу их нужно выбирать. Решила что void Tree::destroy(Node *node, Node *parent ), потому что наша другая функция по удалению не полинома должна передавать именно узел, который нужно удалить. Не понимаю зачем в этом алгоритме 2 параметра.

Вот эти строчки в коде мне не понятны

Код


if (parent) parent = 0;//эту строчку не поняла

Код


if (parent) parent = node->rightPtr;//эту строчку не поняла

Ну и ,конечно,по узлу с 2 потомками завал. Можно прокомментировать каждую строчку?

lenarano

Дата 15.5.2015, 02:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Ой, не увидела, что свою написали. Я тогда вашу посмотрю и если что-то не пойму- спрошу.

feodorv

Дата 15.5.2015, 04:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 15.5.2015, 02:16

)

решила проработать, алгоритм не из форума, взяла отсюда

Гм. Смысл выполнения поставленной перед Вами задачи - не взять готовое и как-то приладить под свои нужды, а всё-таки разобраться с тем, что и как должно происходить. Меня удручает Ваша склонность брать чей-то неизвестно как работающий и с какими ошибками код и тупо его добавлять в свой. И на первый взгляд, код с ошибками. Как Вы их будете исправлять, ничего не понимая в коде, остаётся только догадываться.

Но картинки по ссылке годные, как раз под мой право-левый вариант кода. И хотя картинка, демонстрирующая самый сложный случай
user posted image

описывается как

Цитата

Чтобы решить эту проблему, вы должны заменить удаленный узел крайним правым узлом дерева из левой ветви. Другими словами, двигайтесь вниз от удаленного узла по левой ветви. Затем двигайтесь вниз по правым ветвям до тех пор, пока не найдете узел без правой ветви. Это и есть нужный узел (см. Рисунок 10).

на самом деле на рисунке всё происходит зеркально: удаляемый узел заменяется крайним левым узлом дерева из правой ветви и т.д. Выбор право-левого подхода или лево-правого подхода есть дело вкуса (иначе нужно вводить какой-то критерий выбора, например, можно оценить глубины левой и правой ветви поддерева). Но когда текст расходится с картинкой, лично у меня начинается когнитивный диссонанс. Уверен, что и в коде по ссылке есть недоработки. Стоит ли им безоглядно пользоваться?

Цитата(lenarano @ 15.5.2015, 02:16

)

if (parent) parent = 0;//эту строчку не поняла

Я тоже не понимаю смысла этой строчки. Но учитывая, что функция удаления в коде определена как

Цитата

void Delet1(TREE* node, TREE*& parent)

а не как у Вас (без ссылки на указатель)

Цитата(lenarano @ 15.5.2015, 02:16

)

void Tree::destroy(Node *node, Node *parent )

то какой-то смысл должен быть.

Цитата(lenarano @ 15.5.2015, 02:16

)

Ну и ,конечно,по узлу с 2 потомками завал. Можно прокомментировать каждую строчку?

Каждую строчку - это сума сойти можно. Оно Вам точно нужно?

Цитата(lenarano @ 15.5.2015, 02:46

)

Я тогда вашу посмотрю и если что-то не пойму- спрошу.

Давайте лучше по моему коду. Спрашивайте smile

Добавлено через 10 минут и 38 секунд

Цитата(lenarano @ 15.5.2015, 02:16

)

Не понимаю зачем в этом алгоритме 2 параметра.

Потому что при удалении узла нужно поправить предка этого узла, который на него указывает (либо через leftPtr, либо через rightPtr). Если этого не сделать, то все дерево посыпется - в нём будут присутствовать нерелевантные указатели (то есть указывающие куда-то, но неизвестно куда).

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 15.5.2015, 11:56 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Разобрала удаление узла. Код закомментировала.

Код


void Tree::remove( Node *node, Node *parent)//удаление узла
{
    if( node->rightPtr == 0 && node->leftPtr == 0 )//если это лист
    {
        if( parent == 0 )//если он единственный в дереве
            root = 0;//дерево пустое
        else if( parent->leftPtr == node )//иначе если родитель есть и наш узел стоит слева от родителя
            parent->leftPtr = 0;//мы его выкидываем
        else
            parent->rightPtr = 0;//если был справа тоже выкидываем
    }
    else if( node->rightPtr == 0 )//если наш узел имеет только потомка слева
    {
        if( parent == 0 )//если это корень дерева
            root = node->leftPtr;//потомок слева становится корнем
        else if( parent->leftPtr == node )//иначе если наш узел расположен слева у своего родителя
            parent->leftPtr = node->leftPtr;//потомок узла становится на его место
        else
            parent->rightPtr = node->leftPtr;//значит узел находится справа у родителя, удаляем его
    }
    else if( node->leftPtr == 0 )//аналогично
    {
        if( parent == 0 )
            root = node->rightPtr;
        else if( parent->leftPtr == node )
            parent->leftPtr = node->rightPtr;
        else
            parent->rightPtr = node->rightPtr;
    }
    else //у него есть 2 потомка
    {
        Node *c, *p = node;//2 указателя на удаляемый узел
        for( c = node->rightPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;//ищем в правой ветви крайний левый узел
        if( p != node )
        {
            p->leftPtr = c->rightPtr;
            c->rightPtr = node->rightPtr;
        }
        c->leftPtr = node->leftPtr;
        if( parent == 0 )//если это случай, когда узел -это корень
            root = c;//просто крайний левый ставим в корень
        else if( parent->leftPtr == node )//если есть родитель, то теперь родитель указывает слева на крайний левый узел
            parent->leftPtr = c;
        else
            parent->rightPtr = c;//аналогично
    }
    delete node;//до этого расставляли верно указатели, что бы не разрушить структуру дерева, а сейчас удаляем узел.
}

Вот этот кусочек кода не поняла

Код


if( p != node )
        {
            p->leftPtr = c->rightPtr;
            c->rightPtr = node->rightPtr;
        }
        c->leftPtr = node->leftPtr;

lenarano

Дата 15.5.2015, 12:22 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

само условие ставит в тупик

Код


if( p != node )//теперь оба указателя и p и с указавают на крайний левый узел в правой ветке
        {//рассматривается самый тяжелый случай, т.е.это не просто "веточка с 2 вишенкам"
            p->leftPtr = c->rightPtr;
            c->rightPtr = node->rightPtr;
        }
        c->leftPtr = node->leftPtr;

по моей логике условие должно было бы примерно таким(parent->p !== node) Ведь p указывает на крайний левый узел, за ним ноль. Он не может быть нашим узлом с 2 потомками.

Посмотрела void Tree::remove_non_palindroms(). Так как корень нельзя обработать рекурсивно мы его выделяем отдельно.

Посмотрела

Код


void Tree::remove_non_palindroms_recursive( Node *node, Node *parent)
{
    if( node == 0 ) return;//если узел на каком-то этапе рекрусии становится пустой
    if( node == parent->leftPtr )//если наш узел находится слева от корня
    {
        while( parent->leftPtr != 0 && !parent->leftPtr->is_palindrome() )//узел есть,он не полиндром 1&&0=0 while(0)
            remove( parent->leftPtr, parent);//удаляем этот узел
        if( (node = parent->leftPtr) != 0 )//узел есть, он полиндром
        {
            remove_non_palindroms_recursive( node->leftPtr, node);//пускаем рекурсию
            remove_non_palindroms_recursive( node->rightPtr, node);
        }
    }
    else//узел находится справа от корня
    {
        while( parent->rightPtr != 0 && !parent->rightPtr->is_palindrome() )//аналогично
            remove( parent->rightPtr, parent);
        if( (node = parent->rightPtr) != 0 )
        {
            remove_non_palindroms_recursive( node->leftPtr, node);
            remove_non_palindroms_recursive( node->rightPtr, node);
        }
    }
}

Вот эта срока не понятна, почему так?
node = parent->rightPtr
node = parent->leftPtr

Еще в функции добавление узла. Вначале вроде поняла. Вот мы нашли место в дереве, где надо поставить узел. current хранит этот адрес. Потом про него нигде не упоминается. Мы начинаем опять с корня, проверяя значения ключа, и устаналиваем его в нужное место.Можно об этом поподробнее.

Код


bool Tree::add( Node *node )//функция добавления узла
{
    if( count >= 20 ) return false;
    Node *parent = 0, *current = root;
    while( current != 0 )//если дерево не пустое
    {
        parent = current;// теперь он указывает на корень
        if( node->key == current->key ) return false;//если значения ключа повторяются
        if( node->key < current->key )//находем место в дереве нашему узлу, исходя из значения в ключе
            current = current->leftPtr; 
        else
            current = current->rightPtr;
    }
    if( parent == 0 )//если дерево пустое
        root = node;
    else if( node->key < parent->key )//устанавливаем узел на нужное место
        parent->leftPtr = node;
    else
        parent->rightPtr = node;
    count++;
    return true;
}

Это сообщение отредактировал(а) lenarano - 15.5.2015, 14:34

feodorv

Дата 15.5.2015, 16:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Спасибо за вопросы! Давайте по порядку...

Цитата(lenarano @ 15.5.2015, 11:56

)

Разобрала удаление узла. Код закомментировала.

Очень хорошо! Позволю себе внести правки.

Замечательно, что Вы поняли необходимость правки соответствующего указателя у предка (если он есть; если нет, то правим root) при удалении узла. Такая правка в коде удаления делается аж четыре раза, что намекает на выделение повторяющегося кода в отдельную функцию (лучше даже в inline-функцию):

Код


// Вспомогательная функция замены одного из потомков у предка parent (то есть parent->leftPtr или parent->rightPtr, 
// что ещё нужно определить), чей указатель совпадает с oldNode, на newNode
//
// parent может быть равен нулю только для одного узла дерева - root, поэтому если parent == 0, то на самом деле
// мы меняем сам root с oldNode на newNode (можно в этом случае даже проверить, что oldNode == root)

void Tree::parentFixup( Node *parent, Node *oldNode, Node *newNode)
{ 
// если заменяется сам root; можно проверить, что oldNode == root
  if( parent == 0 )
    root = newNode;

// если же заменяемый узел стоит слева от родителя
  else if( parent->leftPtr == oldNode )
    parent->leftPtr = newNode;

// иначе заменяемый узел стоит справа от родителя; можно проверить, что parent->rightPtr == oldNode
  else
    parent->rightPtr = newNode;
}

Все эти "можно проверить" легко реализуются через assert().

В результате введения в дело parentFixup() функция удаления приобретает такой вид:

Код


// Функция удаления узла из дерева, зная его предка. 
// Если предок есть 0, то удаляется корневой узел дерева

void Tree::remove( Node *node, Node *parent)
{
  if( node->rightPtr == 0 && node->leftPtr == 0 ) // у node нет потомков
    parentFixup( parent, node, 0); // меняем у предка node на 0
  else if( node->rightPtr == 0 ) // у node нет правого потомка
    parentFixup( parent, node, node->leftPtr); // меняем у предка node на node->leftPtr
  else if( node->leftPtr == 0 ) // у node нет левого потомка
    parentFixup( parent, node, node->rightPtr); // меняем у предка node на node->rightPtr
  else // у node есть и левый, и правый потомки; тяжёлый случай
  {
    Node *c, *p = node;
    for( c = node->rightPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;
    if( p != node )
    {
      p->leftPtr = c->rightPtr;
      c->rightPtr = node->rightPtr;
    }
    c->leftPtr = node->leftPtr;
    parentFixup( parent, node, c); // меняем у предка node на найденный узел c
  }
  delete node;
}

Внешний вид у функции улучшился значительно. Вполне возможно, что и улучшилось понимание происходящего. Да, осталось разобрать самый тяжёлый случай с двумя потомками и его непонятками.

Цитата(lenarano @ 15.5.2015, 12:22

)

по моей логике условие должно было бы примерно таким(parent->p !== node)

Простите, parent->что?

Это сообщение отредактировал(а) feodorv - 15.5.2015, 18:03

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 15.5.2015, 18:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Что же делать в самом тяжелом случае удаления узла из бинарного дерева, когда у этого самого узла есть оба потомка?

Идея состоит в том, чтобы подменить удаляемый узел каким-то другим узлом из дерева, желательно без потомков. Абы каким первым попавшимся узлом мы удаляемый узел заменить не можем, дерево всё же отсортировано. Поэтому мы должны действовать строго в согласии с сортировкой - заменяющий узел должен быть или предыдущим, или следующим в последовательности сортировки узлов. В коде ищется следующий за удаляемым в последовательности узел - то есть самый левый в правом поддереве удаляемого узла (см. картинку). И, ура, поскольку между удаляемым узлом и следующим никаких других узлов быть не может - на то он и следующий), то у следующего узла отсутствует левый потомок (это вне зависимости от алгоритма поиска следующего узла; по алгоритму - это очевидно).

Однако даже найдя этот самый следующий узел с отсутствующим левым потомком, мы должны понимать, что этот узел принадлежит его предку. При выдёргивании следующего узла со своего места в дереве мы обязаны соответствующим образом поправить указатель левого потомка у предка этого следующего узла. Поскольку у следующего узла есть только правое поддерево, то оно и становится на место следующего узла, здесь всё просто:

Цитата(feodorv @ 15.5.2015, 16:52

)

p->leftPtr = c->rightPtr;

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

Цитата(feodorv @ 15.5.2015, 16:52

)

parentFixup( parent, node, c); // меняем у предка node на найденный узел c

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

Цитата(feodorv @ 15.5.2015, 16:52

)

c->rightPtr = node->rightPtr;

Цитата(feodorv @ 15.5.2015, 16:52

)

c->leftPtr = node->leftPtr;

Осталось собственно найти следующий элемент по отношению к удаляемому, не забывая про необходимость помнить предка этого следующего элемента:

Код


    Node *c; // следующий элемент, который мы будем искать в правом поддереве узла node
                  // сокращение от c-urrent
    Node *p; // предок узла c; сокращение от p-arent

    // Начальные значения для узлов с и p:
    c = node->rightPtr; // ищем в правом поддереве
    p = node; // предок узла c (ведь у узла node->right предком является node)

    // Цикл поиска следующего узла. 
    // На каждом шаге цикла мы смотрим левого потомка от текущего узла c, 
    // сохраняя узел p предком c при изменении значения c
    while( c->leftPtr != 0 )
    {
       p = c;
       c = c->leftPtr;
    }

    // Теперь мы имеем следующий по отношению к node узел c 
    // (у него c->leftPtr равен 0) и его предка p

Весь выше приведённый код легко записывается в компактную двустрочную форму:

Цитата(feodorv @ 15.5.2015, 16:52

)

Node *c, *p = node;
for( c = node->rightPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;

Осталось поправить указатели:

Код

    p->leftPtr = c->rightPtr;
    c->rightPtr = node->rightPtr;
    c->leftPtr = node->leftPtr;

и предка удаляемого узла:

Код

parentFixup( parent, node, c);

В теории всё просто. На практике Вы рано или поздно столкнётесь со случаем, когда p совпадает с node (то есть когда у node->rightPtr отсутствует левый потомок: node->rightPtr->leftPtr есть 0). Тогда вносимые в указатели правки приведут к хаосу, так как их планирование осуществлялось в предположении, что p != node (то есть что предок следующего узла не есть удаляемый узел). А что собственно меняется в коде в случае p == node? В этом случае мы должны внести всего одну правку в указатели:

p->leftPtr править бесполезно, так как Вы правите значение у удаляемого узла (это значение канет в Лету вместе с удаляемым узлом). Более того, поправив p->leftPtr, Вы безвозвратно испортите node->leftPtr, необходимое при правке c->leftPtr.
c->rightPtr править на node->rightPtr вообще нельзя, так как node->rightPtr есть собственно узел c. Более того, в таком случае при замене в дереве узла node на узел c значение c->rightPtr вообще править не нужно: оно какое было, таким и остаётся.
c->leftPtr (который есть 0), нужно заменить на node->rightPtr.

Вот отсюда и код

Цитата(lenarano @ 15.5.2015, 11:56

)

Вот этот кусочек кода не поняла

if( p != node )
        {
            p->leftPtr = c->rightPtr;
            c->rightPtr = node->rightPtr;
        }
        c->leftPtr = node->leftPtr;

Здесь мы правим значения p->leftPtr и c->rightPtr только в том случае, если p не есть node.

Это сообщение отредактировал(а) feodorv - 15.5.2015, 23:23

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 15.5.2015, 18:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

В принципе, вариант, когда p совпадает с node, можно выделить в особый случай среди наших if-else (так как поиск следующего элемента в дереве не нужен - этот элемент уже известен):

Код


void Tree::remove( Node *node, Node *parent)
{
  if( node->rightPtr == 0 && node->leftPtr == 0 ) // у node нет потомков
    parentFixup( parent, node, 0); // меняем у предка node на 0
  else if( node->rightPtr == 0 ) // у node нет правого потомка
    parentFixup( parent, node, node->leftPtr); // меняем у предка node на node->leftPtr
  else if( node->leftPtr == 0 ) // у node нет левого потомка
    parentFixup( parent, node, node->rightPtr); // меняем у предка node на node->rightPtr
  else if( node->rightPtr->leftPtr == 0 )
  {
     node->rightPtr->leftPtr = node->leftPtr;
     parentFixup( parent, node, node->rightPtr);
  }
  else
  {
    Node *c, *p = node->rightPtr;
    for( c = p->leftPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;
    p->leftPtr = c->rightPtr;
    c->rightPtr = node->rightPtr;
    c->leftPtr = node->leftPtr;
    parentFixup( parent, node, c); // меняем у предка node на найденный узел c
  }
  delete node;
}

Можно повыпендриваться дальше и проверить ещё и node->leftPtr->rightPtr (как будто мы смотрим предыдущий узел по отношению к node, а не следующий):

Код


void Tree::remove( Node *node, Node *parent)
{
  if( node->rightPtr == 0 && node->leftPtr == 0 ) // у node нет потомков
    parentFixup( parent, node, 0); // меняем у предка node на 0
  else if( node->rightPtr == 0 ) // у node нет правого потомка
    parentFixup( parent, node, node->leftPtr); // меняем у предка node на node->leftPtr
  else if( node->leftPtr == 0 ) // у node нет левого потомка
    parentFixup( parent, node, node->rightPtr); // меняем у предка node на node->rightPtr
  else if( node->rightPtr->leftPtr == 0 )
  {
     node->rightPtr->leftPtr = node->leftPtr;
     parentFixup( parent, node, node->rightPtr);
  }
  else if( node->leftPtr->rightPtr == 0 )
  {
     node->leftPtr->rightPtr = node->rightPtr;
     parentFixup( parent, node, node->leftPtr);
  }
  else
  {
    Node *c, *p = node->rightPtr; // точно знаем, что node->rightPtr->leftPtr не 0
    for( c = p->leftPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;
    p->leftPtr = c->rightPtr;
    c->rightPtr = node->rightPtr;
    c->leftPtr = node->leftPtr;
    parentFixup( parent, node, c); // меняем у предка node на найденный узел c
  }
  delete node;
}

PS Этот код не проверял, так что если что, не обессудьте)))

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 15.5.2015, 19:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 15.5.2015, 12:22

)

Еще в функции добавление узла. Вначале вроде поняла. Вот мы нашли место в дереве, где надо поставить узел. current хранит этот адрес. Потом про него нигде не упоминается. Мы начинаем опять с корня, проверяя значения ключа, и устаналиваем его в нужное место.Можно об этом поподробнее.

Место-то в дереве мы нашли. Но оно пустое, оно не занято ни каким другим узлом. Соответственно, current становится нулём. Посмотрите внимательно на цикл:

Цитата(lenarano @ 15.5.2015, 12:22

)

    while( current != 0 )//если место для вставки ещё не найдено
    {
        if( node->key == current->key ) return false; // если значения ключа повторяются

        parent = current; // углубляемся в дерево ещё на один уровень
        if( node->key < current->key ) // выбираем ветку (левую или правую), исходя из значения ключа
            current = current->leftPtr;
        else
            current = current->rightPtr;
    }

По его окончании current просто-напросто равен 0. Как его можно дальше использовать?

В чем же смысл этого цикла? В поиске узла (предка), в который мы будем осуществлять вставку нового узла. Смысл - в поиске parent, а не current; current здесь вспомогательная переменная. Но даже найдя этот узел, мы снова вынуждены определять ветку, в которую будем вставлять новый узел, либо в leftPtr, либо в rightPtr:

Цитата(lenarano @ 15.5.2015, 12:22

)

    if( parent == 0 )//если дерево пустое
        root = node;
    else if( node->key < parent->key )//устанавливаем узел на нужное место
        parent->leftPtr = node;
    else
        parent->rightPtr = node;

В принципе, особыми усилиями можно обойтись и без повторного определения ветки, но в данном случае это не принципиально.

Цитата(lenarano @ 15.5.2015, 12:22

)

Посмотрела void Tree::remove_non_palindroms(). Так как корень нельзя обработать рекурсивно мы его выделяем отдельно.

А нельзя его обрабатывать рекурсивно, потому что у него нет предка. Мы для него не можем писать:

Код


while( parent->leftPtr != NULL ...) ...

А вот почему мы проверяем значение root в цикле:

Цитата(feodorv @ 15.5.2015, 01:12

)

while( root != 0 && !root->is_palindrome() ) remove( root, 0);

Во-первых, изначально дерево может быть пустым, и казалось бы это легко проверяется через if( root != 0 ). Но ведь в процессе удаления узлов дерево действительно может стать пустым (когда в нём изначально нет ни одного палиндрома). Поэтому проверку на 0 нужно делать постоянно.
Во-вторых, само значение root меняется при удалении корня дерева. При изменении корня на его место может встать узел, опять-таки не являющийся палиндромным, и его тоже нужно удалить. И так далее, пока дерево не опустеет, либо корнем не станет палиндромный узел. Поэтому и проверку на палиндромность нужно делать всё время. В результате получается очень компактный while.

Аналогично и в функции remove_non_palindroms_recursive(). В ней узел node, на самом деле, служит лишь для определения ветки (правой или левой) предка, в которой он находится. Мы бы могли с тем же успехом использовать функцию вида:

Код


void Tree::remove_non_palindroms_recursive( bool isLeft, Node *parent)
{
  ...
}

вообще не передавая указатель на node (а зачем, если мы его легко найдём согласно значению isLeft). Предок нам существенно необходим (не только как аргумент функции удаления), так как в процессе удаления его непалиндромных потомков изменяются его leftPtr и/или rightPtr. А их (как и root'а) нужно будет повторно проверять на палиндромность:

Код


void Tree::remove_non_palindroms_recursive( bool isLeft, Node *parent)
{
...
  if( isLeft )
  {
    // удаляем узел parent->leftPtr до тех пор пока его не станет, либо он не окажется палиндромным
    // совершенно аналогично root, только через parent->leftPtr
    while( parent->leftPtr != 0 && !parent->leftPtr->is_palindrome() )
      remove( parent->leftPtr, parent);

    if( parent->leftPtr != 0 ) // рекурсия
    {
      remove_non_palindroms_recursive( true /* parent->leftPtr->leftPtr */, parent->leftPtr);
      remove_non_palindroms_recursive( false /* parent->leftPtr->rightPtr */, parent->leftPtr);
    }
  }
  else
  {
    // аналогично с правым потомком узла parent
    ...
  }
}

Как видите, узел node в таком варианте кода даже не понадобился.

Для упрощения бесконечных -> можно ввести дополнительную переменную:

Код


void Tree::remove_non_palindroms_recursive( Node *node, Node *parent)
{
...
  if( parent->leftPtr == node )
  {
    // удаляем узел parent->leftPtr до тех пор пока его не станет, либо он не окажется палиндромным
    // совершенно аналогично root, только через parent->leftPtr
    while( parent->leftPtr != 0 && !parent->leftPtr->is_palindrome() )
      remove( parent->leftPtr, parent);

    Node *temp;
    if( (temp = parent->leftPtr) != 0 ) // рекурсия
    {
      remove_non_palindroms_recursive( temp->leftPtr, temp);
      remove_non_palindroms_recursive( temp->rightPtr, temp);
    }
  }
  else
  {
    // аналогично с правым потомком узла parent
    ...
  }
}

В ранее приведённом коде вместо temp использовалась переменная node, и только для упрощения кода, поэтому я надеюсь, что ответил на Ваш вопрос:

Цитата(lenarano @ 15.5.2015, 12:22

)

Вот эта срока не понятна, почему так?
node = parent->rightPtr
node = parent->leftPtr

Это сообщение отредактировал(а) feodorv - 16.5.2015, 04:27

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 16.5.2015, 00:53 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Спасибо огроменное. smile

По добавлению узла вопросов не осталось.
По удалению узла вот эти 2 строчки не понятны в случае, если узел и p не совпадают:

Код


p->leftPtr = c->rightPtr;
c->rightPtr = node->rightPtr;

Например, как на картинке из интернета, когда p=6, а с=4.
Предположим у нашего с (ключ4) есть справа потомок, а не ноль как на картинке. Разве у нас не теряются данные при этом? Вроде все при деле и 6 и 1, пристроены))) Если есть хвостик справа от 4, то всунули его в 4. А данные из 4 куда делись, разве при этом мы не теряем ключ и строку?

Это сообщение отредактировал(а) lenarano - 16.5.2015, 02:22

feodorv

Дата 16.5.2015, 02:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 16.5.2015, 00:53

)

Например, как на картинке из интернета, когда p=6, а с=4.

На картинке не нарисовано, но Вы представьте себе, что у 4-ки есть правое поддерево с ключом 5 (левого нет по условию нахождения самого левого узла). Что делать с 5-ой? Бросить на произвол судьбы? Нет, конечно. Перед тем, как править c->leftPtr и c->rightPtr, нужно бережно сохранить поддерево c->rightPtr, которое встаёт на место самого узла c:

Код


p->leftPtr = c->rightPtr;

Если поддерева нет (то есть c->rightPtr есть 0, то Вы просто правильно присвоите 0 левому потомку узла p).

Вот Вам другая картинка, правда, с ошибкой (интересно, найдёте ли Вы её):
user posted image

Здесь в последнем случае удаляется узел 5 (node), на место которого встаёт узел 6 ( c ), а у него есть правый потомок 7 (c->rightPtr). Что делать с 7-ой?

Далее. Вы на место узла 5 (node) вставляете узел 6 ( c ), при этом Вы должны сохранить все старые связи удаляемого узла 5. То есть теперь parent должен иметь своим потомком узел c вместо узла node, а потомками узла c (как бы новым node) должны стать соответствующие потомки удаляемого узла node:

Код


    c->rightPtr = node->rightPtr;
    c->leftPtr = node->leftPtr;

В условных единицах этой картинки:

Отсоединяем замещающий узел 6 от дерева:
Цитата
10->leftPtr = 7;
Правим предка удаляемого узла:
Цитата
15->leftPtr = 6;
Правим потомков замещающего узла:
Цитата
6->leftPtr = 5->leftPtr;
6->rightPtr = 5->rightPtr;

Всё, дерево свободно от узла 5, сохранив отсортированность своих узлов. Можно делать delete 5.

Я Вам специально выделил случай, когда p == node, чтобы подчеркнуть связность всех этих операций:

Цитата(feodorv @ 15.5.2015, 18:21

)

  else if( node->rightPtr->leftPtr == 0 ) // p == node
  {
     node->rightPtr->leftPtr = node->leftPtr;
     parentFixup( parent, node, node->rightPtr);
  }
  else
  {
    Node *c, *p = node->rightPtr; // точно знаем, что node->rightPtr->leftPtr не 0
    for( c = p->leftPtr; c->leftPtr != NULL; c = c->leftPtr) p = c;
    p->leftPtr = c->rightPtr;
    c->rightPtr = node->rightPtr;
    c->leftPtr = node->leftPtr;
    parentFixup( parent, node, c); // меняем у предка node на найденный узел c
  }

Но Вы упорно выделяете только правки p->leftPtr и c->rightPtr, которые не нужно совершать в случае p == node. Почему?

Это сообщение отредактировал(а) feodorv - 16.5.2015, 04:39

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

lenarano

Дата 16.5.2015, 02:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 62
Регистрация: 17.4.2014

Репутация: нет
Всего: нет

Ошибку нашла-художник оставил в итоге 5 на месте в (в). Я пристроила 7))) Я решила, что p->leftPtr это и есть с и боялась, что потеряем данные, а на этой картинке все поняла.

feodorv

Дата 16.5.2015, 04:02 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(lenarano @ 16.5.2015, 02:45

)

Ошибку нашла-художник оставил в итоге 5 на месте в (в).

Цитата(lenarano @ 16.5.2015, 02:45

)

Я решила, что p->leftPtr это и есть с

До выдёргивания узла c так и было. После - уже не должно быть)))

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

feodorv

Дата 18.5.2015, 00:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45

Цитата(feodorv @ 15.5.2015, 19:39

)

В результате получается очень компактный while.

Мне тут в голову пришла простая, по сути, мысль: если сначала удалить непалиндромные узлы из потомков узла, а лишь потом проверять сам узел на непалиндромность, то while не нужен. Да и уменьшится количество операций (то есть быстрее работать будет) smile

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »