Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.05.2013, 21:40   #1
tzaf
Пользователь
 
Регистрация: 14.04.2013
Сообщений: 12
По умолчанию двоичное дерево

как пронумеровать вершины бинарного дерева? Думаю надо сделать обход в ширину.
Код:
// бинарное дерево.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct Node {
int d;
Node *left;
Node *right;
int f;
};
Node * first(int d);
Node * search_insert(Node *root, int d);
void print_tree(Node *root, int l);
void num_tree(Node *root, int f);
int _tmain(int argc, _TCHAR* argv[])
{
int b[] = {10,25,20,6,21,8,1,30,35};
Node *root = first(b[0]);
for (int i=1; i<9; i++) search_insert (root, b[i]);
print_tree(root, 0);
num_tree(root, 0);
getchar();getchar(); 
return 0; 
}
//Формирование первого элемента в дееве
Node *first (int d) {
Node *pv = new Node;
pv->d = d;
pv->left = 0;
pv->right = 0;
return pv;
}

//поиск с включением
Node * search_insert(Node *root,int d){
Node *pv = root, *prev;
bool found = false;
while (pv && !found){
prev = pv;
if (d == pv->d) found = true;
else if (d < pv->d) pv = pv-> left;
else pv= pv->right;
}
if (found) return pv;
//Создание нового узла
Node *pnew = new Node;
pnew->d = d;
pnew->left = 0;
pnew->right = 0;
if (d < prev->d)
//Присоединение к левому поддереву предка;
prev->left = pnew;
else prev->right = pnew; //Присоединение к правому поддереву предка;
return pnew;
}

//Обход дерева
void print_tree(Node *p, int level)
{
if (p){
print_tree(p->left, level + 1);
for (int i=0; i<level; i++) cout <<" ";
cout << p->d << endl;
print_tree(p->right, level + 1);

}
}
// нумерация вершин
void num_tree(Node *p, int f)
{
f++;
if (p){
num_tree(p->left, f); 
cout << f <<p->d << endl;
f++;
num_tree(p->right, f); 
}
}

Последний раз редактировалось Stilet; 21.05.2013 в 08:31.
tzaf вне форума Ответить с цитированием
Старый 20.05.2013, 23:20   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Используйте тег CODE для оформления кода:
Код:
// нумерация вершин
void num_tree(Node *p, int f)
{
  f++;
  if (p){
    num_tree(p->left, f);
    cout << f <<p->d << endl;
    f++;
    num_tree(p->right, f);
  }
}
Обратите внимание: f передаётся в функцию по значению, а значит, после вызова num_tree(p->left, f); значение этой переменной не изменится. Однако, если мы добавим в левое поддерево ещё элемент, номер текущего элемента должен измениться. Противоречие.
Один из способов его устранения - сделать так, чтобы num_tree возвращала последний присвоенный номер в обойдённом дереве. Тогда:
Код:
// нумерация вершин
//начинается с f+1, возвращается последний присвоенный номер
int num_tree(Node *p, int f)
{
  if (p){
    f = num_tree(p->left, f) + 1; //Следующий номер
    cout << f <<p->d << endl; //присваиваем корню
    f = num_tree(p->right, f); //и от f+1 нумеруем правое поддерево
  }
  return f;
}
Abstraction вне форума Ответить с цитированием
Старый 21.05.2013, 13:51   #3
tzaf
Пользователь
 
Регистрация: 14.04.2013
Сообщений: 12
По умолчанию

Исправил код, все нумерует. Но мне бы хотелось, чтобы корень нумеровался 1, потом на следующем уровне 2,3, затем 4,5,6,7 и т.д. В общем пронумеровать по горизонтали. Потому что мне нужно еще поменять вершины: четного отца с четным сыном.
tzaf вне форума Ответить с цитированием
Старый 21.05.2013, 14:00   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Но мне бы хотелось, чтобы корень нумеровался 1, потом на следующем уровне 2,3, затем 4,5,6,7 и т.д.
О. Тогда я как-то вообще не вижу изящного решения. То есть, это нужно вводить функцию "пронумеровать k-ый 'этаж' начиная с номера n+1 и вернуть последний присвоенный номер" и в результате получается достаточно коряво. Можете покопать в этом направлении.
Abstraction вне форума Ответить с цитированием
Старый 21.05.2013, 14:06   #5
tzaf
Пользователь
 
Регистрация: 14.04.2013
Сообщений: 12
По умолчанию

Спасибо. Попробую.
tzaf вне форума Ответить с цитированием
Старый 21.05.2013, 14:25   #6
tzaf
Пользователь
 
Регистрация: 14.04.2013
Сообщений: 12
По умолчанию

Можете, пожайлуста, поправить код.
#include "stdafx.h"
#include <iostream>
using namespace std;
struct Node {
int d;
Node *left;
Node *right;
int f;
};
Node * first(int d);
Node * search_insert(Node *root, int d);
void print_tree(Node *root, int l);
int num_tree(Node *root, int l, int f);
int _tmain(int argc, _TCHAR* argv[])
{
int b[] = {10,25,20,6,21,8,1,30,35};
Node *root = first(b[0]);
for (int i=1; i<9; i++) search_insert (root, b[i]);
print_tree(root, 0);
num_tree(root, 0, 0);
getchar();getchar();
return 0;
}
//Формирование первого элемента в дееве
Node *first (int d) {
Node *pv = new Node;
pv->d = d;
pv->left = 0;
pv->right = 0;
return pv;
}

//поиск с включением
Node * search_insert(Node *root,int d){
Node *pv = root, *prev;
bool found = false;
while (pv && !found){
prev = pv;
if (d == pv->d) found = true;
else if (d < pv->d) pv = pv-> left;
else pv= pv->right;
}
if (found) return pv;
//Создание нового узла
Node *pnew = new Node;
pnew->d = d;
pnew->left = 0;
pnew->right = 0;
if (d < prev->d)
//Присоединение к левому поддереву предка;
prev->left = pnew;
else prev->right = pnew; //Присоединение к правому поддереву предка;
return pnew;
}

//Обход дерева
void print_tree(Node *p, int level)
{
if (p){
print_tree(p->left, level + 1);
for (int i=0; i<level; i++) cout <<" ";
cout << p->d << endl;
print_tree(p->right, level + 1);

}
}

// нумерация вершинвозвращается
//начинается с f+1, последний присвоенный номер
int num_tree(Node *p,int l, int f)
{
if (p){
f++;
num_tree(p->left,l+1, f) + 1;
for (int i=0; i<l+1; i++) cout <<" ";
cout << f++ << ","<<p->d << endl; //присваиваем корню
num_tree(p->right, l+1,f);
}
return f;
}
tzaf вне форума Ответить с цитированием
Старый 21.05.2013, 14:50   #7
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

0) Пожалуйста, оформляйте код тегом CODE.
1) Почему Вы считаете, что код должен быть "поправлен"?
Abstraction вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
двоичное дерево apostol584 Помощь студентам 0 29.11.2012 09:19
Двоичное дерево Бендер Паскаль, Turbo Pascal, PascalABC.NET 3 21.12.2010 20:48
Двоичное дерево (С++) Dead Romantic Помощь студентам 0 30.05.2010 23:52
Двоичное дерево Jasper92 Общие вопросы C/C++ 1 18.04.2010 13:27
Двоичное дерево на си++ fesked Помощь студентам 0 22.10.2009 23:44