Обход БСТ в итерационных симметричного


Обход бинарного дерева поиска в итеративном порядке.

Обратите внимание, что ниже итерационные методы содержат мясо код; остальные код включен для полноты картины.

// tree node
struct node 
{
    int elem;

    node *left, *right;

    // Statically create a node, given an element

    static node* create(int elem)
    {
        node *newnode = new node;
        newnode->elem = elem;
        newnode->left = newnode->right = NULL;
        return newnode;
    }   

    // Statically destroy a node

    static void destroy (node *& mynode)
    {
        delete mynode;
        mynode->left = mynode->right = NULL;
    }
};

typedef stack<const node*> nodestack;
typedef vector<const node*> nodevect;


// tree class

class tree
{
    private:
    node *root;
    nodestack mystack;

    public:
    // initialize tree
    tree(int elem) 
    {
        root = node::create(elem);
    }

    /* --------- INSERTION METHODS BEGIN --------- */
    // Insert a new element into a subtree whose root node is given
    bool insert(node *travnode, int elem)
    {
        node *newnode = node::create(elem);
        // Insert to left subtree
        if(elem < travnode->elem)
        {
            if(travnode->left == NULL) 
            {
                travnode->left = newnode;
                return true;
            }
            else  return insert(travnode->left,elem);   
        }
        else
        if(elem == travnode->elem)
        {
            delete newnode;
            return false;
        }
        // Insert to right subtree
        else // if(elem > travnode->elem)
        {
            if(travnode->right == NULL) 
            {
                travnode->right = newnode;
                return true;
            }
            else return insert(travnode->right,elem);   
        }
    }

    // Insert directly into the tree; this method is used externally  
    bool insert(int elem)
    {
        return insert(root,elem);   
    }       

    /* --------- INSERTION METHODS END --------- */

    /* ------- RECURSIVE METHODS BEGIN -----------*/
    // Recursive methods below are used for checking the iterative version
    // Recursive inorder traversal of a node ; dump nodes traversed into a  vector
    void recursive_inorder(const node *mynode, vector<int> &myvect) const 
    {
        if(mynode != NULL)
        {
            recursive_inorder(mynode->left,myvect);
            myvect.push_back(mynode->elem);
            recursive_inorder(mynode->right,myvect);
        }
    }


    // Recursive traversal of the whole tree
    vector<int> recursive_inorder() const
    {
        vector<int> myvect; 
        recursive_inorder(root,myvect);
        return myvect;
    }
    /* -------- RECURSIVE METHODS END -------*/



    /* -------- ITERATIVE METHODS BEGIN ---*/
    //  Go to the leftmost node, stacking nodes along the path 
    void findLeftMostAndStack(const node *mynode) 
    {
        const node *travnode = mynode;
        while(travnode != NULL)
        {
            mystack.push(travnode);
            travnode = travnode->left;  
        }   
    } 

    // Return the stack created thus far
    nodestack getStack() const {return mystack;}

    // Get the first element in inorder traversal, stacking all nodes on the way from the root
    const node* findFirstElement() 
    {
        while(!mystack.empty()) 
            mystack.pop();

        findLeftMostAndStack(root);
        const node *firstNode = mystack.top();
        mystack.pop();

        return firstNode;
    }



    // Given any node, use the stack to find the successor
    const node* findSuccessorOf(const node *mynode)
    {
        // We're at the last node in traversal; there is no successor
        if(mystack.empty() && mynode->right == NULL)
            return NULL;

        // If there is a right child, stack the nodes along the first node in the right subtree  
        if(mynode->right != NULL) 
            findLeftMostAndStack(mynode->right);

        // To find the successor,  
        const node *successor = mystack.top();          
        mystack.pop();
        return successor;
    }


    // Use all the methods above to traverse the tree iteratively inorder
    vector<int> iterative_inorder()
    {
        vector<int> myvect;
        // Get first element
        const node* nextnode = findFirstElement();
        while(nextnode != NULL) // go on till last element is reached
        {
            myvect.push_back(nextnode->elem); 
            // keep finding successors
            nextnode = findSuccessorOf(nextnode);   
        }

        return myvect;
    }

    /* --------------- ITERATIVE METHODS END *--------------*/

    // Friend functions
    friend tree* makeTree(const vector<int> &); // create tree using a vector
    // compare recursive & iterative traversals 
    friend bool compareRecIter(tree &T);


    // Destroy subtree
    void destroy (node *& mynode) 
    { 
        if(mynode == NULL) return;
        destroy(mynode->left); 
        destroy(mynode->right); 
        delete(mynode);
        mynode->left = mynode->right = NULL;
        mynode =  NULL;     
    }

    // Destroy tree
    void destroy() { this->destroy(root);
}; // tree class

/* Auxiliary functions */
// Create a tree from  a vector of elements
tree* makeTree(const vector<int> &v)    
{
    assert(v.size());
    tree *T = new tree(v[0]);
    for(size_t i = 1; i != v.size(); ++i)
        T->insert(v[i]);
    return T;
}  


// Compare recursive & iterative traversals of the tree
// If equal, return true; else false
bool compareRecIter(tree &T)
{
    // Get the 2 vectors, returned by recursive & iterative traversals
    vector<int> v = T.recursive_inorder();
    vector<int> v2 = T.iterative_inorder();
    for(int i=0;i!=v.size();++i) cout<<v[i] <<",";
    cout<<endl;

    for(int i=0;i!=v2.size();++i) cout<<v2[i] <<",";
    cout<<endl;
    // Return true if they are identical
    return (v == v2);   
}

Тестовый код:

int main()
{
    int leftLeaning[5] = {5,4,3,2,1};
    tree *T = makeTree(vector<int>(leftLeaning, leftLeaning + 5));

    assert(compareRecIter(*T)); 
    T->destroy();
    delete T;
    T = NULL;

    cout<<"\n";
    int rightLeaning[5] = {1,2,3,4,5};

    tree* T2 = makeTree(vector<int>(rightLeaning, rightLeaning + 5));
    assert(compareRecIter(*T2));
}


2476
4
задан 15 мая 2011 в 07:05 Источник Поделиться
Комментарии
1 ответ

Ваша программа выглядит хорошо и, вероятно, будет работать без каких-либо заметных ошибок. Однако есть несколько проблемных зон, и липкий очков вам следует обратиться. Я начну с самого важного первого:


  • Доступ к членам данных структуры после удаления:


    static void node::destroy( node *& mynode )
    {
    delete mynode;
    mynode->left = mynode->right = NULL;
    mynode = NULL;
    }

    void tree::destroy( node *& mynode )
    {
    if( mynode == NULL ) return;
    destroy( mynode->left );
    destroy( mynode->right );
    delete( mynode );
    mynode->left = mynode->right = NULL;
    mynode = NULL;
    }


Выше два метода содержат сбросить поведения, потому что вы пытаетесь присвоить слева и справа после mynode были удалены.


  • Дырявый заключения; методы, которые должны быть частными не являются. Например, первый перегруженный вставка() метод должен быть частным, а ваши комментарии тут подсказывают:


// Insert a new element into a subtree whose root node is given
bool insert( node *&travnode, int elem )
//...

// Insert directly into the tree; this method is used externally
bool insert( int elem )
//...

А также несколько других методов, которые за пределами код, используя это дерево не знать. Вспомогательные функции и методы, как уничтожить(), перегруженные recursive_inorder() и найти() используется дерево итерации приходит на ум. Они принадлежат в разделе частная дерево. В идеале, код, использующий ваш класс дерево не должно подвергаться то, что узлы используются.


  • РАИИ должен быть использован для динамического выделения узла. Дерево вашего класса должен отвечать за уборку собственные узлы в деструкторе, а не заставляя клиента код для вызова уничтожить(). Для защиты от преждевременной утечки есть функции, которые возвращают динамически выделенную память, как makeTree(), использовать смарт-указатель, как auto_ptr.

  • Применение дерево::уничтожить() не orthagonal с узел::создать(). На самом деле, узел::уничтожить() не используется вообще. Это также выглядит как узел::уничтожить() ожидает того, кто использует его для обработки нижней ветви этого узла. Не то, что это обязательно неправильно, но то, как это должно прокомментировал так понятно, какие допущения делаются. Например, если класс дерево не обрабатывать левого и правого дочерних узлов родительского узла, который был удален, то, что всю нижнюю ветку просто разъединили.

  • Неудобно инициализации в конструкторе дерево. Если вы измените конструктор, чтобы принять ряд представлен двумя итераторами, а не один инт, он будет делать класс, что значительно облегчает работу с. Он будет также избавиться от необходимости в отдельном makeTree() функция.

  • логическое дерево::вставить( узел *&travnode, инт Элем ) может быть переработан с меньше кода. Вы можете сделать это, нажав на нуль проверить вниз к основанию корпуса и меняется узел *travnode в ссылочный указатель. Это также устраняет потенциальную утечку памяти скрывается в вашем первоначальном варианте.


    bool insert( node *&travnode, int elem )
    {
    if( travnode == NULL )
    {
    travnode = node::create( elem );
    return true;
    }

    if(travnode->elem == elem ) return false;

    node *&correct_branch = elem elem ? travnode->left : travnode->right;
    return insert( correct_branch, elem );
    }


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

2
ответ дан 16 мая 2011 в 11:05 Источник Поделиться