Бинарное дерево

Уровень сложности:

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

К сожалению, решения данной задачи пока нет. Если Вы решили эту задачу, сообщите нам, и мы выложим её на сайте.

E-mail : admin@cppstudio.com

 

Следующие статьи помогут вам в решении данной задачи:

Функции в С++

Обсудить на форуме
Автор: admin
Дата: 12.09.2012
Поделиться:

Комментарии

  1. Артём Вильчук

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



#include <iostream>
using namespace std;

struct Derevo
{
	int x;
	Derevo *left = NULL;
	Derevo *right = NULL;
};

void add_new_element_in_derevo(Derevo* koren, Derevo* new_element)//функция вставляет в нужное место в деревке мой новый элемент
{
	if (koren->x > new_element->x  && koren->left != NULL)//шагаем
		add_new_element_in_derevo(koren->left, new_element);
	if (koren->x < new_element->x  && koren->right != NULL)//шагаем
		add_new_element_in_derevo(koren->right, new_element);

	if (koren->x > new_element->x  && koren->left == NULL)//добавляем
		koren->left = new_element;
	if (koren->x < new_element->x  && koren->right == NULL)//добавляем
		koren->right = new_element;

}
void input_element(Derevo* koren, bool &t)//функция ввода значения нового элемента(и в ней функция добавления этого элемента в деревко)
{
	cout << "\n_______________________________________\nЕсли ввести \"999\", то ввод прекратится! \n_______________________________________\n";
	cout << "Введите значение нового элемента : ";
	Derevo *a1 = new Derevo;
	cin >> a1->x;
	if (a1->x == 999)
	{
		t = false;
		return;
	}
	add_new_element_in_derevo(koren, a1);
}

void LEVEL(Derevo *koren_d, int &i, int &max_level)//считает количество уровней в деревке моём :)(нужно для вывода деревка,чтобы знать на сколько уровней погружаться рекурсией)
{
	if (koren_d->left != NULL)
	{
		i++;
		if (max_level < i)
			max_level = i;
		LEVEL(koren_d->left, i, max_level);
		i--;
	}
	if (koren_d->right != NULL)
	{
		i++;
		if (max_level < i)
			max_level = i;
		LEVEL(koren_d->right, i, max_level);
		i--;
	}
}

void display_level(Derevo *koren_d, int &i, int level)//выводит уровень № level у деревка :)
{
	if (i == level)
		cout << koren_d->x << " ";
	if (koren_d->left != NULL)
	{
		i++;
		display_level(koren_d->left, i, level);
		i--;
	}
	if (koren_d->right != NULL)
	{
		i++;
		display_level(koren_d->right, i, level);
		i--;
	}
}

void display_all(Derevo *koren)
{
	int i = 0;//нужна для сквозной нумерации уровня в рекурсиях.(по крайней мере моя башка не придумала ничего лучше этого костыля)
	int max_level = 0;
	LEVEL(koren, i, max_level); //---узнаю максимальный уровень дерева
	cout << "max level = " << max_level << endl;
	for (int level = 0; level <= max_level; level++) //--цикл поочереди выводит каждый уровень девера, начиная с корняж
	{
		if (level == 0)
			cout << "[ koren ] : ";
		else
			cout << "[" << level << " lvl] : ";
		display_level(koren, i, level);//--функция вывода 1 уровня  дерева   
		cout << endl;
	}
}




void main()
{
	setlocale(LC_ALL, "Russian");
	Derevo *koren = NULL;

	Derevo *a0 = new Derevo;
	cout << "Введите значение корня : ";
	cin >> a0->x;
	koren = a0;
	/////////////////////////////////////////

	bool t = true;//нужна для выхода из цикла(когда введу 999 - поменяетс на false и цикл добавления прекратится)
	while (t)
	{
		display_all(koren);//---вывожу всё дерево(существующее на данный момент)
		input_element(koren, t);//добавляю новый элемент в деревко
		system("cls");

	}

}

  2. Артём Вильчук

    эмм,вот:

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

    ___________________________________________

    #include <iostream>
    using namespace std;

    struct Derevo
    {
    int x;
    Derevo *left = NULL;
    Derevo *right = NULL;
    };

    void add_new_element_in_derevo(Derevo* koren, Derevo* new_element)//функция вставляет в нужное место в деревке мой новый элемент
    {
    if (koren->x > new_element->x && koren->left != NULL)//шагаем
    add_new_element_in_derevo(koren->left, new_element);
    if (koren->x < new_element->x && koren->right != NULL)//шагаем
    add_new_element_in_derevo(koren->right, new_element);

    if (koren->x > new_element->x && koren->left == NULL)//добавляем
    koren->left = new_element;
    if (koren->x < new_element->x && koren->right == NULL)//добавляем
    koren->right = new_element;

    }
    void input_element(Derevo* koren,bool &t)//функция ввода значения нового элемента(и в ней функция добавления этого элемента в деревко)
    {
    cout << «\n_______________________________________\nЕсли ввести \»999\», то ввод прекратится! \n_______________________________________\n»;
    cout << «Введите значение нового элемента : «;
    Derevo *a1 = new Derevo;
    cin>>a1->x;
    if (a1->x == 999)
    {
    t = false;
    return;
    }
    add_new_element_in_derevo(koren,a1);
    }

    void LEVEL(Derevo *koren_d,int &i,int &max_level)//считает количество уровней в деревке моём :)(нужно для вывода деревка,чтобы знать на сколько уровней погружаться рекурсией)
    {
    if (koren_d->left != NULL)
    {
    i++;
    if (max_level < i)
    max_level = i;
    LEVEL(koren_d->left, i, max_level);
    i—;
    }
    if (koren_d->right != NULL)
    {
    i++;
    if (max_level < i)
    max_level = i;
    LEVEL(koren_d->right, i, max_level);
    i—;
    }
    }

    void display_level(Derevo *koren_d, int &i, int level)//выводит уровень № level у деревка :)
    {
    if (i == level)
    cout <<koren_d->x <<» «;
    if (koren_d->left != NULL)
    {
    i++;
    display_level(koren_d->left, i, level);
    i—;
    }
    if (koren_d->right != NULL)
    {
    i++;
    display_level(koren_d->right, i, level);
    i—;
    }
    }

    void display_all(Derevo *koren)
    {
    int i = 0;//нужна для сквозной нумерации уровня в рекурсиях.(по крайней мере моя башка не придумала ничего лучше этого костыля)
    int max_level = 0;
    LEVEL(koren, i, max_level); //—узнаю максимальный уровень дерева
    cout << «max level = » << max_level << endl;
    for (int level = 0; level <= max_level; level++) //—цикл поочереди выводит каждый уровень девера, начиная с корняж
    {
    if (level == 0)
    cout << «[ koren ] : «;
    else
    cout << «[» << level << » lvl] : «;
    display_level(koren, i, level);//—функция вывода 1 уровня дерева
    cout << endl;
    }
    }
    void main()
    {
    setlocale(LC_ALL, «Russian»);
    Derevo *koren = NULL;

    Derevo *a0 = new Derevo;
    cout << «Введите значение корня : «;
    cin >> a0->x;
    koren = a0;
    /////////////////////////////////////////

    bool t = true;//нужна для выхода из цикла(когда введу 999 — поменяетс на false и цикл добавления прекратится)
    while (t)
    {
    display_all(koren);//—вывожу всё дерево(существующее на данный момент)
    input_element(koren,t);//добавляю новый элемент в деревко
    system(«cls»);

    }

    }

  3. Mechanic

    Mechanic

    Мой вариант решения:

    #include <cstdlib>
#include <iostream>
#include <cstring>

using namespace std;

class Node{
    private:
        char *str;
        Node *left, *right;
        
        int compare(char *nodeStr, char *newStr){//функция сравнивает 2 строки: возвращает 1, если 2я > 1й, 0 если 2=1, -1 если 2<1
            int i = 0;
            if (strlen(newStr) > strlen(nodeStr)){
                return 1;
            } else if (strlen(newStr) < strlen(nodeStr)){
                return -1;
            } else {
                while(i<strlen(newStr)){
                    if(newStr[i] > nodeStr[i]){
                        return 1;
                    } else if (newStr[i] < nodeStr[i]){
                        return -1;
                    }
                    i++;
                }
            }
            return 0;
        }
        
        int counter(int level, int step, int count){//подсчитывает количество ветвей на уровне level
            if (step <= level){
                if(step == level){
                    count++;
                }
                if(right != NULL){
                    count = right->counter(level, step+1, count);
                }
                if(left != NULL){
                    count = left->counter(level, step+1, count);
                }
            }
            return count;
        }
        
    public:
        Node(char *newStr) {
            str = newStr;
            left = right = NULL;
        }
        
        
        void add(char *newStr){
            int branch;
            branch = compare(str, newStr);
            if(branch == 1){
                if(right != NULL){
                    right->add(newStr);
                } else {
                    right = new Node(newStr);
                }
            } else if (branch == -1){
                if(left != NULL){
                    left->add(newStr);
                    
                } else {
                    left = new Node(newStr);
                }
            }
        }
        
        void search(char *newStr){
            int branch;
            branch = compare(str, newStr);
            if(branch == 1){
                if(right != NULL){
                    right->search(newStr);
                } else {
                    cout << "can't find!" << endl;
                }
            } else if (branch == -1){
                if(left != NULL){
                    left->search(newStr);
                } else {
                    cout << "can't find!" << endl;
                }
            } else if (branch == 0){
                cout << "Found!" << endl;
            }
        }
        
        void printAll(){        
            if(right!=NULL){
                right->printAll();
            }
            cout << str << endl;
            if(left!=NULL){
                left->printAll();
            }
        }
        
        void counter(int level){
        int count = 0;
        count = counter (level, 1, 0);
        cout << "count = " << count << endl;
        }
};

Node *root = NULL;

int printMenu(){
    int select;
    cout << "select:\n"
            "1) add new element\n"
            "2) search element\n"
            "3) print tree\n"
            "4) calculate at level\n"
            "5) exit\n";
    cin >> select;
    return select;
}

bool menuSelect(){
    int select = printMenu();
    int level;
    char buff[64];
    char* string;
    
    switch(select){
        case 1:
            cout << "enter string: ";
            cin >> buff;
            string = new char [strlen(buff)];
            strcpy(string, buff);
            if (root != NULL){
                    root->add(string);
                } else {
                    root = new Node(string);
                }
            break;
        case 2:
            cout << "enter string: ";
            cin >> buff;
            string = new char [strlen(buff)];
            strcpy(string, buff);
            root->search(string);
            break;
        case 3:
            cout << "tree: ";
            root->printAll();
            break;
        case 4:
            cout << "level: ";
            cin >> level;
            root->counter(level);
            break;
        case 5:
            return true;
            break;
        default:
            cout << "uncorrect input! please try again\n";
            menuSelect();
            break;
    }
}
/*
 * 
 */
int main(int argc, char** argv) {
    
    bool exit = false;
    do {
        exit = menuSelect();
    } while(!exit);
    
    return 0;
}
  4. curunir

    curunir

    Жалко что тут нельзя удалять :с

    Вот готовый вариант, а там поспешил и не всё сделал.

    #include <iostream>
#define N 15
class Node;
int CountBranches(Node*, int);

class Node
{
  char str[N];
  Node* left, *right;
  
  public:
  Node(char* STR)
  {
    int i;
    for(i = 0; i < N; i++)
      str[i] = STR[i];
    left = right = NULL;
  }
  
  void Add(char* STR)
  {
    int i;
    for(i = 0; i < N; i++)
      if(str[i] != STR[i])
      {
        if(str[i] < STR[i])
        {
          if(right != NULL)
            right->Add(STR);
          else
            right = new Node(STR);
        }
        else
        {
          if(left != NULL)
            left->Add(STR);
          else
            left = new Node(STR);
        }
        return;
      }
  }
  
  void Show()
  {
    std::cout << str << ' ';
    if(left != NULL)
      left->Show();
    if(right != NULL)
      right->Show(); 
  }
  
  void BranchCount(int currentLvl, int &counter, int &request)
  {
     if(++currentLvl == request)
       counter++;
     if(left != NULL)
       left->BranchCount(currentLvl, counter, request);
     if(right != NULL)
       right->BranchCount(currentLvl, counter, request);
  }
};

main()
{
  Node *Root = NULL;
  char option, inputStr[N];
  int lvl;
  
  do
  {
    system("cls");
    std::cout << "1 - Add\n2 - Show\n3 - Count branches of level\n4 - Exit\nMy choice: ";
    
    std::cin >> option;
    switch(option)
    {
      case '1':
      {
        std::cout << "Input value: ";
        std::cin >> inputStr;
        if(Root != NULL)
          Root->Add(inputStr);
        else
          Root = new Node(inputStr);
      }break;
      
      case '2':
      {
        std::cout << "Current tree (straight bypass): ";
        if(Root != NULL)
          Root->Show();
        std::cout << std::endl;
        system("PAUSE");
      }break;
      
      case '3':
      {
        std::cout << "Input level: ";
        std::cin >> lvl;
        std::cout << "Branches of lvl " << lvl << " is " << CountBranches(Root, lvl) << std::endl;
        system("PAUSE"); 
      }break;
    }
  }
  while(option != '4');  
}

int CountBranches(Node* Root, int lvl)
{
  int i = 0;
  Root->BranchCount(-1, i, lvl);
  return i;
}

Оставить комментарий

Вы должны войти, чтобы оставить комментарий.