VPF::Печать бинарного древа - Форум программистов

Voldemar2004

Дата 17.4.2007, 23:11 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

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

Есть класс 'бинарное дерево'. Не получается сделать метод печати дерева, чтобы оно выглядело действительно, как дерево с листьями. Получается стоблец. smile

Код

/*------------------------------------------------------------------------------*/

/*------------------------------------------------------------------------------*/
template <class T> class BinaryNode;
template <class T> class BinaryTree;

/*
--------------------------------------------------------------------------------
                Класс массива
--------------------------------------------------------------------------------*/

#ifndef __BSTree_cpp 
#define __BSTree_cpp

/*
--------------------------------------------------------------------------------
                 Класс обычного узла дерева двоичного поиска 
--------------------------------------------------------------------------------*/ 
template <class T> class BinaryNode
{ 
friend class BinaryTree<T>; 
private: 
       BinaryNode<T> *Parent; 
       BinaryNode<T> *Left; 
       BinaryNode<T> *Right; 
       T              Data; 
public: 
       BinaryNode (void):Parent(0),Left(0),Right(0){}; 
      ~BinaryNode (void); 
       T GetData  (void) { return Data; }
};

/*
-------------------------------------------------------------------------------- 
                 Класс дерева [хранитель корня и операций на деревом] 
--------------------------------------------------------------------------------*/

template <class T> class BinaryTree
{ 
public: 
       BinaryNode<T> * Root; 

       void Insert (T); 
       void Remove (T); 
       int  Depth  (void); 
       int  Depth  (BinaryNode<T>*);
       void Clear  (BinaryNode<T>*);
       void Clear  (void) { while (Root) Remove(Root->Data); } 
       BinaryNode<T>* Find (T); 
       BinaryTree (void):Root(0){}
      ~BinaryTree (void) {Clear();}
};

/*
--------------------------------------------------------------------------------
           Реализация методов класса BinaryTree 
--------------------------------------------------------------------------------*/

template <class T> BinaryNode<T> :: ~BinaryNode (void) { 
     if (Parent) 
         if (Parent->Left==this) Parent->Left  = 0; 
         else                    Parent->Right = 0; 
}

/*--------------------------------------------------------------------------------*/
template <class T> void BinaryTree<T> :: Insert (T tmp) { 
     BinaryNode<T> * current = Root; 
     BinaryNode<T> * parent  = 0; 
     BinaryNode<T> * x; 
     while (current) { 
          if (tmp==current->Data) return; 
          parent = current; 
          current = tmp>current->Data?current->Right:current->Left; 
     } 
     x = new BinaryNode<T>(); 
     if (!x)    return; 
     x->Data   = tmp; 
     x->Parent = parent; 
     x->Left   = 0; 
     x->Right  = 0; 

     if (parent) 
         if (tmp<parent->Data) parent->Left = x; 
         else parent->Right = x; 
     else Root = x; 
}

/*--------------------------------------------------------------------------------*/
template <class T> void BinaryTree<T> :: Remove (T tmp) { 
    BinaryNode <T> *y,*x,*in=0; 

    in = Find (tmp);
    if (in==0) return; 

    if (in->Left==0 || in->Right==0) y=in; 
    else { 
        y = in->Right; 
        while (y->Left!=0) y=y->Left; 
    } 
    if (y->Left!=0)  x = y->Left; 
    else             x = y->Right; 

    if (x) x->Parent = y->Parent; 
    if (y->Parent) 
        if (y == y->Parent->Left) 
            y->Parent->Left = x; 
        else 
            y->Parent->Right = x; 
    else 
        Root = x; 
    if (y != in) in->Data = y->Data; 
    delete y; 
}

/*--------------------------------------------------------------------------------*/
template <class T> BinaryNode<T>* BinaryTree<T> :: Find (T tmp) {
    BinaryNode <T> * ptr = Root;
    while (ptr) {
         if (tmp == ptr->Data) return ptr;
         ptr = ptr->Data > tmp ? ptr->Left : ptr->Right;
    }
    return 0;
}

/*--------------------------------------------------------------------------------*/
template <class T> void BinaryTree<T> :: Clear (BinaryNode<T>*rrr) { 
    if (rrr->Left)    Clear (rrr->Left); 
    if (rrr->Right)   Clear (rrr->Right); 
    delete rrr; 
}

/*--------------------------------------------------------------------------------*/
template <class T> int BinaryTree<T> :: Depth (BinaryNode<T>*tmp) {
    if (!tmp) return 0;
    int left  = 1+Depth(tmp->Left);
    int right = 1+Depth(tmp->Right);
    return left>right?left:right;
}

/*--------------------------------------------------------------------------------*/
template <class T> int BinaryTree<T> :: Depth (void) {
    return Depth(Root);
}

/*--------------------------------------------------------------------------------*/

#endif

Нужно вот так:

                 56 (родитель)

      44 (левое поддерево)

                                  66 (правое поддерево)
6         55
                                             87

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

i_i
(';')
(V)

user posted image

nickless

Дата 18.4.2007, 00:04 (ссылка)

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

Загрузка ...

Гентозавр

Профиль
Группа: Участник Клуба
Сообщений: 2976
Регистрация: 29.8.2005
Где: Germany

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

Принцип печати такой:
1. вычисляем максимальную ширину дерева, если бинарное, можно просто взять ширина=(1<<высота)*<макс. ширина узла при выводе>
2. печатаем, тут имхо только 2 способа:

или передаём в метод позицию и ширину, печатаем узел сразу в нужном месте экрана, а потом просто рекурсивно вызываем метод с половиной ширины и нужным сдвигом у детей, но так сложнее печатать например в файл
или проходим по дереву по слоям (level-order traversal) и печатаем всё по очереди сверху вниз слева направо уменьшая ширину вдвое на каждой строчке, но тут нужно хранить в узлах дополнительно или ссылку на соседа справа или хотя бы в каком слое находится каждый узел

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

Real men don't use backups, they post their stuff on a public ftp server and let the rest of the world make copies
- Linus Torvalds

KelTron

Дата 18.4.2007, 04:55 (ссылка)

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

Загрузка ...

Опытный

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

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

Если отображать дерево немного не так, а повернутое на 90градусов против часовой:
         88
     66
56
          55
     44
          6
то вывод делается проще, например:

Код


void showTree(Tree* root, int lvl = 0)
{
    if(root->right != 0)    showTree(root->right, lvl+1);
    for (int i = 0; i < lvl; ++i)
        cout << "    ";
    cout << root->data << endl;
    if(root->left != 0)    showTree(root->left, lvl+1);
}

потом используем:

Код


void show()
{
    showTree(root);
}

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

Тысячами незримых нитей обвивает тебя Закон. Разрубишь одну - преступник. Десять - смертник. Все - Бог.
Эвенгар Салладорский, основатель Школы Тьмы.

Voldemar2004

Дата 18.4.2007, 14:55 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

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

KelTron, этот метод из Павловской Т.А. smile

Он мне не подходит. smile

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

i_i
(';')
(V)

user posted image

KelTron

Дата 18.4.2007, 16:41 (ссылка)

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

Загрузка ...

Опытный

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

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

Первый раз слышу про

Цитата(Voldemar2004 @ 18.4.2007, 14:55

)

Павловской Т.А.

Цитата(Voldemar2004 @ 18.4.2007, 14:55

)

Он мне не подходит

ну на нет и суда нет

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

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