Вывод бинарного дерева на экран в виде "дерева"

@Point_0 · Регистрация: 02.10.2011

Author24 — интернет-сервис помощи студентам

основная задача: подсчет количества листьев.
проблема: при просмотре хочу выводить бин. дерево, в красивом виде, возможно использование псевдографики
интересует алгоритм и идеи
Пы.Сы.: так же интересует любая инфа по теме основного задания.

@Wolkodav · 08.12.2012, 22:49

Могу скинуть функцию распечатывания в консоли дерева. Она только немного будет на 90 градусов в лево перевёрнуто, но наглядно достаточно.

Добавлено через 1 минуту
А подсчёт кол-во листьев, просто обойти все дерево, в глубину или в ширину (как вам больше нравиться), тут лучше в ширину наверное будет, для подсчёта кол-ва.

@Point_0 · 09.12.2012, 00:10 **[ТС]**

конечно давайте, посмотрю

go · 09.12.2012, 00:22

Point_0, вот откопал одну из своих лаб. Писал два года назад, поэтому возможно и коряво.

C++

// лабаДеревья.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <Windows.h>
 
#define FL
 
 
typedef struct link
{
    int key;
    link *left;
    link *right;
} node;
 
 
void GoToXY (short x, short y)
{
    HANDLE StdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD coord = {x, y};
    SetConsoleCursorPosition(StdOut, coord);
}
 
 
node * search (node * tree, int key)
{
    node *buf;
    
    if (tree)
        do
        {
            buf=tree;
            if (tree->key==key)
                return NULL;
            if (key<tree->key)
                tree=tree->left;
            else
                tree=tree->right;
        } while (tree);
 
        return buf;
}
 
int Add (node **tree, int key)
{
    node * buf;
#ifdef FL
    if (!  ( buf = (node *) malloc ( sizeof (node) ) )  )
    {
        printf ("\nNo free memory");
        return -1;
    }
#else
    buf = new node;
#endif
    buf->key=key;
    buf->left=NULL;
    buf->right=NULL;
 
 
    if (!*tree)
    {
        *tree=buf;
        return 1;
    }
 
    if (search(*tree,key))
    {
        if (key<search(*tree,key)->key)
            search(*tree,key)->left=buf;
        else 
            search (*tree,key)->right=buf;
    }
    else 
        return -1;
 
    return 0;
}
 
 
/*void iteration (node * root)
{
    if (root)
    {
        printf ("%5d", root->key);
        iteration (root->left);
        iteration (root->right);
    }
}*/
 
void Free(node *&root)
{
 if (root->left)
    Free(root->left);
 if (root->right)
     Free(root->right);
#ifdef FL
 free ( root );
#else
 delete root;
#endif
 root = NULL;
}
 
void print (node * root, short x, short y, short a, char c)
{
    if (root)
    {
        if (a>0 && c!='k')
        {
            if (c=='l')
                x-=10;
            else
                x+=10;
        }
        else 
            if (c!='k')
                if (c=='l')
                    x-=4;
                else
                    x+=4;
        
        GoToXY (x,y+=2);
 
        a--;
 
        printf ("%5d", root->key);
        print (root->left,x,y,a,'l');
        print (root->right,x,y,a,'r');
    }
}
 
 
void list (node * root, short x, short y, short a, char c)
{
    if (root)
    {
        if (a>0 && c!='k')
        {
            if (c=='l')
                x-=10;
            else
                x+=10;
        }
        else 
            if (c!='k')
                if (c=='l')
                    x-=4;
                else
                    x+=4;
        
        GoToXY (x,y+=2);
 
        a--;
 
        if ( !root->left && !root->right )
            printf ("%5d", root->key);
        list (root->left,x,y,a,'l');
        list (root->right,x,y,a,'r');
    }
}
 
 
void del (node **root, int value)
{
    if (!*root)
    { 
        printf ("No key\n");
        fflush (stdin);
        getch ();
        return ;
    }
    
    if (value < (*root)->key)
        del (&(*root)->right,value);
    else 
        if (value > (*root)->key)
            del (&(*root)->right,value);
        else
        {
            node *buf=(*root)->left;
            node *t =(*root)->right;
            free (*root);
            *root=t;
            
            while (*root)
                root = &(*root)->left;
            
            *root = buf;
        }
}
 
 
size_t Count ( node *root, bool f = true )
{
    static size_t count;
        
    if ( f )
        count = 0;
 
    if ( root )
    {
        if ( ( root->left && ! root->right ) || ( ! root->left && root->right  )  )
            ++count;
 
        Count ( root->left, false );
        Count ( root->right, false );
    }
 
    return count;
}
 
 
 
 
        
 
 
    
 
 
 
 
int main(int argc, char* argv[])
{
    node *tree=NULL;
    int key;
    char a;
    system ("cls");
    //Add (&tree,3); Add (&tree,5); Add (&tree,1); Add (&tree,0); Add (&tree,7); Add (&tree,7); 
    //print (tree,37,5,2,'k'); printf ("\n");
 
 
    do
    {
        printf ("\n 1-Dobavit`; 2-Delete; 3- Print; 4 - list; 5 - Count; 6 - Del_Tree 0-Vuhod");
        fflush (stdin);
        a=getch();
        printf ("\n");
        
        switch (a) 
        {
        case '1' : 
            while (!(fflush (stdin) ) && ! ( printf ("Enter key " ) && scanf ("%d",&key) ) );
            Add (&tree,key);
            break;
        case '2' :
            while (!(fflush (stdin) ) && ! ( printf ("Enter key to delete " ) && scanf ("%d",&key) ) );
            del (&tree, key);
            break;
        case '3' :
            printf ("Tree : ");
            if (!tree)
                printf ("None");
            else
                //iteration (tree);
                print (tree,37,5,2,'k');
            printf ("\n\n\n\n\n\n");
 
            system ("pause");
            break;
        case '4' : 
            printf ("Tree list : ");
            if (!tree)
                printf ("None");
            else
                //iteration (tree);
                list (tree,37,5,2,'k');
            printf ("\n\n\n\n\n\n");
 
            system ("pause");
            break;
        case '5' :
            printf ("\n Count = %d \n", Count (tree) );
            system ("pause");
            break;
        case '6' :
            Free (tree);
            break;
        }
            
 
        system ("cls");
 
    } while (a!='0'); 
 
 
 
    system ("pause");
    return 0;
}

@Wolkodav · 09.12.2012, 12:37

C++

struct Tree
{
    int key;
    Tree* left;
    Tree* right;
};
 
void print_Tree(Tree * p,int level)
{
    if(p)
    {
        print_Tree(p->left,level + 1);
        for(int i = 0;i< level;i++) cout<<"   ";
        cout << p->key << endl;
        print_Tree(p->right,level + 1);
    }
}

@Point_0 · 10.12.2012, 17:17 **[ТС]**

вот переделал под свои нужды, но при тесте иногда выходят ошибки, например при задании теста 1 2 3..10 и тд дерево теряет вид(
как исправить не знаю

C++

// вывод дерева поиска и  листьев
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <Windows.h>
 
typedef struct derevo
{
    int data;
    derevo *left;
    derevo *right;
} node;
 
 
void GoToXY (short x, short y)
{
    HANDLE StdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD coord = {x, y};
    SetConsoleCursorPosition(StdOut, coord);
}
 
 
node * search (node * tree, int data)
{
    node *buf;
 
    if (tree)
        do
        {
            buf=tree;
            if (tree->data==data)
                return NULL;
            if (data<tree->data)
                tree=tree->left;
            else
                tree=tree->right;
        }
        while (tree);
 
    return buf;
}
 
int Add (node **tree, int data)
{
    node * buf;
#ifdef FL   
    if (!  ( buf = (node *) malloc ( sizeof (node) ) )  )
    {
        printf ("\nNo free memory");
        return -1;
    }
#else
    buf = new node;
#endif
    buf->data=data;
    buf->left=NULL;
    buf->right=NULL;
 
 
    if (!*tree)
    {
        *tree=buf;
        return 1;
    }
 
    if (search(*tree,data))
    {
        if (data<search(*tree,data)->data)
            search(*tree,data)->left=buf;
        else
            search (*tree,data)->right=buf;
    }
    else
        return -1;
 
    return 0;
}
 
 
void Free(node *&root)
{
    if (root->left)
        Free(root->left);
    if (root->right)
        Free(root->right);
#ifdef FL                // что это тоже блин
    free ( root );
#else
    delete root;
#endif
    root = NULL;
}
 
 
 
void print (node * root, short x, short y, short a, char c)
{
    if (root)
    {
        if (a>0 && c!='k')
        {
            if (c=='l')
                x-=10;
            else
                x+=10;
        }
        else if (c!='k')
            if (c=='l')
                x-=4;
            else
                x+=4;
 
        GoToXY (x,y+=2);
 
        a--;
 
        printf ("%5d", root->data);
        print (root->left,x,y,a,'l');
        print (root->right,x,y,a,'r');
    }
}
 
 
void list (node * root, short x, short y, short a, char c)
{
    if (root)
    {
        if (a>0 && c!='k')
        {
            if (c=='l')
                x-=10;
            else
                x+=10;
        }
        else if (c!='k')
            if (c=='l')
                x-=4;
            else
                x+=4;
 
        GoToXY (x,y+=2);
 
        a--;
 
        if ( !root->left && !root->right )
            printf ("%5d", root->data);
        list (root->left,x,y,a,'l');
        list (root->right,x,y,a,'r');
    }
}
 
 
int main(int argc, char* argv[])
{
    node *tree=NULL;
    int data;
    char a;
    system ("cls");
 
    do
    {
        printf ("\n 1-Dobavit`;  2- Vuvod; 3 - Listia;  4 - Ocistka 0-Vuhod");
        fflush (stdin);
        a=getch();
        printf ("\n");
 
        switch (a)
        {
        case '1' :
            while (!(fflush (stdin) ) && ! ( printf ("Vvedite chislo " ) && scanf ("%d",&data) ) );
            Add (&tree,data);
            break;
 
        case '2' :
            printf ("Derevo : ");
            if (!tree)
                printf ("Pustoe ");
            else
                
                print (tree,37,5,2,'k');
            printf ("\n\n\n\n\n\n");
 
            system ("pause");
            break;
        case '3' :
            printf ("Listia dereva : ");
            if (!tree)
                printf ("Pustoe Derevo ");
            else
                
                list (tree,37,5,2,'k');
            printf ("\n\n\n\n\n\n");
 
            system ("pause");
            break;
 
        case '4' :
            Free (tree);
            break;
              printf ("Derevo ochisceno ");
        }
 
        system ("cls");
    }
    while (a!='0');
 
    system ("pause");
    return 0;
}

go · 10.12.2012, 19:10

Point_0, никак. Написать самому. Не надо задавать "однобокое" дерево.

@Wolkodav · 10.12.2012, 19:18

Ну как бы когда дерево однобокое, оно вырождается в сисок, как бы ничего этого в этом нету.

go · 10.12.2012, 21:01

Wolkodav, я не спорю. Я скинул прогу для сдачы какой-нибудь лабы, где дерево более-мение. Да, функция печати корявая. Переписывать не буду, т. к. времени нет.

@Point_0 · 12.12.2012, 21:28 **[ТС]**

go, лабу сдал, ваши функции очень помогли, просто не понял, что значит дерево однобокое?

go · 12.12.2012, 21:31

Point_0, это я образно. Что только одна сторона(один бок) есть.

@Programmister · 13.12.2013, 03:38

Point_0, Wolkodav, go, расскажите подробнее о то бинарное дерево деревом что это вообще такое?

@Mirrowel · 15.12.2014, 16:28

C++

size_t Count ( node *root, bool f = true )
{
    static size_t count;
        
    if ( f )
        count = 0;
 
    if ( root )
    {
        if ( ( root->left && ! root->right ) || ( ! root->left && root->right  )  )
            ++count;
 
        Count ( root->left, false );
        Count ( root->right, false );
    }
 
    return count;
}

Что делает этот раздел в коде товарища go?
Что конкретно он считает.

Добавлено через 9 минут
И как можно сделать проверку на сбалансированность дерева(от товарища go например).

@ninelivesfrost · 04.06.2016, 20:01

Assembler

mov ax ax

@SergioO · 04.06.2016, 20:25

Сообщение от Mirrowel

И как можно сделать проверку на сбалансированность дерева

примерно - сбалансированные деревья-деревья нулевые указатели которых находятся на одной глубине.

@ddfddf · 04.04.2017, 10:28

а существует ли реализация удаления узла у вас?

@Point_0 5 / 5 / 2 Регистрация: 02.10.2011 Сообщений: 87
		1
	Вывод бинарного дерева на экран в виде "дерева" 04.12.2012, 15:03. Показов 109511. Ответов 15 Метки нет (Все метки) основная задача: подсчет количества листьев. проблема: при просмотре хочу выводить бин. дерево, в красивом виде, возможно использование псевдографики интересует алгоритм и идеи Пы.Сы.: так же интересует любая инфа по теме основного задания. 0

@Wolkodav 840 / 478 / 58 Регистрация: 18.09.2012 Сообщений: 1,688
	08.12.2012, 22:49	2
	Могу скинуть функцию распечатывания в консоли дерева. Она только немного будет на 90 градусов в лево перевёрнуто, но наглядно достаточно. Добавлено через 1 минуту А подсчёт кол-во листьев, просто обойти все дерево, в глубину или в ширину (как вам больше нравиться), тут лучше в ширину наверное будет, для подсчёта кол-ва. 1

@Point_0 5 / 5 / 2 Регистрация: 02.10.2011 Сообщений: 87
	09.12.2012, 00:10 [ТС]	3
	конечно давайте, посмотрю 1

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	10.12.2012, 19:10	7
	Point_0, никак. Написать самому. Не надо задавать "однобокое" дерево. 2

@Wolkodav 840 / 478 / 58 Регистрация: 18.09.2012 Сообщений: 1,688
	10.12.2012, 19:18	8
	Ну как бы когда дерево однобокое, оно вырождается в сисок, как бы ничего этого в этом нету. 1

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	10.12.2012, 21:01	9
	Wolkodav, я не спорю. Я скинул прогу для сдачы какой-нибудь лабы, где дерево более-мение. Да, функция печати корявая. Переписывать не буду, т. к. времени нет. 1

@Point_0 5 / 5 / 2 Регистрация: 02.10.2011 Сообщений: 87
	12.12.2012, 21:28 [ТС]	10
	go, лабу сдал, ваши функции очень помогли, просто не понял, что значит дерево однобокое? 1

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	12.12.2012, 21:31	11
	Point_0, это я образно. Что только одна сторона(один бок) есть. 1

@Programmister 1 / 1 / 0 Регистрация: 12.12.2013 Сообщений: 8
	13.12.2013, 03:38	12
	Point_0, Wolkodav, go, расскажите подробнее о то бинарное дерево деревом что это вообще такое? 1

@SergioO 260 / 208 / 99 Регистрация: 13.12.2015 Сообщений: 1,098
	04.06.2016, 20:25	15
	Сообщение от Mirrowel И как можно сделать проверку на сбалансированность дерева примерно - сбалансированные деревья-деревья нулевые указатели которых находятся на одной глубине. 0

	04.04.2017, 10:28

@ddfddf 0 / 0 / 1 Регистрация: 01.02.2015 Сообщений: 20
	04.04.2017, 10:28	16
	а существует ли реализация удаления узла у вас? 0

Вывод бинарного дерева на экран в виде "дерева"

Решение