Привет All!
может ли кто то подсказать алгорит(или можна код на С), как распечатать данные бинарного дерева по горизонтали(т.е. по уровням)

Буду очень благодарен!
Заранее большое всем спасибо

Здравствуйте, Аноним, Вы писали:

А>Привет All!
А>может ли кто то подсказать алгорит(или можна код на С), как распечатать данные бинарного дерева по горизонтали(т.е. по уровням)

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

Здравствуйте, Аноним, Вы писали:

А>Привет All!
А>может ли кто то подсказать алгорит(или можна код на С), как распечатать данные бинарного дерева по горизонтали(т.е. по уровням)

А>Буду очень благодарен!
А>Заранее большое всем спасибо

Обход в ширину:

process_node(node_t * n, queue_t * q)
{
print_node(n);
enqueue_children(n, q);
while((n = dequeue_node(q)) != 0) {
process_node(n, q);
}
}

По-моему, так...

Здравствуйте, vnp, Вы писали:

Извиняюсь. Рекурсию написал машинально, не подумавши. И теги забыл.

print_tree(node_t * root)
{
    queue_t * q = create_queue();
    enqueue(q, root);
    while((root = dequeue(q)) != 0) {
        print_node(root);
        enqueue_children(q, n);
    }
}

Здравствуйте, vnp, Вы писали:

vnp>Здравствуйте, vnp, Вы писали:

vnp>Извиняюсь. Рекурсию написал машинально, не подумавши. И теги забыл.

vnp>

vnp>print_tree(node_t * root)
vnp>{
vnp>    queue_t * q = create_queue();
vnp>    enqueue(q, root);
vnp>    while((root = dequeue(q)) != 0) {
vnp>        print_node(root);
vnp>        enqueue_children(q, n);
vnp>    }
vnp>}
vnp>

я конечно извиняюсь, я не очень силен в С, я только учусь , но хотелось бы узнать что такое queue_t, create_queue();, enqueue, dequeue, enqueue_children и как они реализованны?
если конечно не сложно, можна получить их код?
Большое спасибо!

Здравствуйте, Red_Baron, Вы писали:

R_B>я конечно извиняюсь, я не очень силен в С, я только учусь :) , но хотелось бы узнать что такое queue_t, create_queue();, enqueue, dequeue, enqueue_children и как они реализованны? :shuffle:

Если на С++ — то берём #include <queue> и изучаем хелп по std::queue

А на Си — всё ручками, однако!
Самая простая очередь — на односвязном списке.

enqueue — запихать в очередь.
dequeue — вытащить из очереди
create_queue — очевидно, создать объект "очередь"
(поскольку ты учишься, я думаю, тебе стоит решить эту задачку самостоятельно; она не сложная).

enqueue_children — запихать в очередь все дочерние узлы текущего узла дерева.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Red_Baron, Вы писали:

R_B>>я конечно извиняюсь, я не очень силен в С, я только учусь , но хотелось бы узнать что такое queue_t, create_queue();, enqueue, dequeue, enqueue_children и как они реализованны?

К>Если на С++ — то берём #include <queue> и изучаем хелп по std::queue

К>А на Си — всё ручками, однако!
К>Самая простая очередь — на односвязном списке.

К>enqueue — запихать в очередь.
К>dequeue — вытащить из очереди
К>create_queue — очевидно, создать объект "очередь"
К>(поскольку ты учишься, я думаю, тебе стоит решить эту задачку самостоятельно; она не сложная).

К>enqueue_children — запихать в очередь все дочерние узлы текущего узла дерева.

а можна ли решить эту задачу без использования дополнительной памяти? и если да, то как?

Здравствуйте, Red_Baron, Вы писали:

R_B>а можна ли решить эту задачу без использования дополнительной памяти? и если да, то как?

Можно, но дольше. За квадратичное время, что ли.
Многократный поперечный обход.

Если у дерева нет восходящих связей (от дочерних узлов к родительским), то с помощью рекурсии.
Если есть — то можно обойтись и без неё.

К>Можно, но дольше. За квадратичное время, что ли.
К>Многократный поперечный обход.

К>Если у дерева нет восходящих связей (от дочерних узлов к родительским), то с помощью рекурсии.
К>Если есть — то можно обойтись и без неё.

Поясню мысль.
На каждом этапе мы осуществляем обход вглубь, проваливаясь строго до определённого уровня.

struct node
{
  node *left, *right; // дочерние узлы
  int data;
};

void print_layers(node *root)
{
  int n = 0;
  while(print_layer(root, n)) ++n;
}

bool print_layer(node *root, int n) // возвращает true если были найдены узлы ниже исследуемого уровня
{
  if(!root) return false;
  if(n==0)
  {
    printf("%d ",root->data);
    return root->left || root->right;
  }
  else
  {
    // здесь мы должны обеспечить строго заданный порядок выполнения обоих функций
    // поэтому print_layer(left)|print_layer(right) не пройдёт из-за неспецифицированного порядка
    // (компилятор может переставить на своё усмотрение)
    // а print_layer(left)||print_layer(right) не пройдёт, т.к. успех первого блокирует выполнение второго
    bool l = print_layer(root->left, n-1);
    bool r = print_layer(root->right, n-1);
    return l || r;
  }
}

У этой функции есть очевидные недостатки. В первую очередь, она всё-таки расходует память (стек). И, если дерево вырождено до списка, мы получим линейную рекурсию — можем исчерпать стек.
Для борьбы с этим есть нехитрый приём: замена рекурсии на итерации.

bool print_layer(node *root, int n)
{
  while(true) // будем крутить безусловный (но не бесконечный :) ) цикл
  {
    if(!root) return false;
    if(n==0)
    {
      printf("%d ",root->data);
      return root->left || root->right;
    }

    if(!root->right)
      { root = root->left;  --n; continue; }
    if(!root->left)
      { root = root->right; --n; continue; }

    bool l = print_layer(root->left, n-1);
    bool r = print_layer(root->right, n-1);
    return l || r;
  }
}

Если есть восходящие связи, то можно обойтись без рекурсии. Итератор дерева состоит из указателя на узел дерева и глубиномера.

Итератор с глубиномером работает точно так же, как и обычный итератор поперечного обхода, с той лишь разницей, что игнорирует узлы, лежащие ниже заданной глубины.

struct node
{
  node *up, *lt, *rt;
  int data;
};

struct iter
{
  node *p;
  int d;
};
void start(node *root, int n, iter* it) // установка итератора в стартовую позицию
{
  // локальные переменные - чтобы меньше основной писанины было
  node *p = root;
  int d = 0;

  // идём как можно левее
  while(d<n && p->left) { ++d; p=p->left; }

  it->p = p;
  it->d = d;
}
void next(int n, iter* it)
{
  /* иллюстрация к алгоритму: фрагмент дерева
             ...
             /
            E
     ______/
    D
     \
     ...
       \
        B
       / \
      A   C
  */

  node *p = it->p;
  int d = it->d;

  do // чтобы выйти по break вместо кудрявых if-else
  {
    // от левого вверх: A->B
    if(p->up && p->up->left==p) { --d; p=p->up; break; }

    // от родителя вправо: B->C
    if(d<n && p->right) { ++d; p=p->right; break; }

    // от правого - вверх по правой ветке C->...->D и затем вверх ->E
    while(!p->up || p->up->right==p) { --d; p=p->up; }
    if(!p) break; // вылетели из дерева, это значит, мы были крайне правым узлом
    --d; p=p->up;
  }
  while(false);

  it->p = p;
  it->d = d;
}
bool end(iter *it)
{
  return !it->p; // признак конца - вылет из дерева
}

bool print_layer(node *root, int n)
{
  bool contd = false; // to be continued на следующем уровне
  iter it;

  for(start(root,n,it); !end(it); next(n,it))
  {
    if(d==n)
    {
      printf("%d ", p->data);
      contd = contd||p->left||p->right;
    }
  }
}

Здравствуйте, Кодт, Вы писали:

К>Если есть восходящие связи, то можно обойтись без рекурсии. Итератор дерева состоит из указателя на узел дерева и глубиномера.

К>Итератор с глубиномером работает точно так же, как и обычный итератор поперечного обхода, с той лишь разницей, что игнорирует узлы, лежащие ниже заданной глубины.
К>

К>struct node
К>{
К>  node *up, *lt, *rt;
К>  int data;
К>};

К>struct iter
К>{
К>  node *p;
К>  int d;
К>};
К>void start(node *root, int n, iter* it) // установка итератора в стартовую позицию
К>{
К>  // локальные переменные - чтобы меньше основной писанины было
К>  node *p = root;
К>  int d = 0;

К>  // идём как можно левее
К>  while(d<n && p->left) { ++d; p=p->left; }

  it->>p = p;
  it->>d = d;
К>}
К>void next(int n, iter* it)
К>{
К>  /* иллюстрация к алгоритму: фрагмент дерева
К>             ...
К>             /
К>            E
К>     ______/
К>    D
К>     \
К>     ...
К>       \
К>        B
К>       / \
К>      A   C
К>  */

К>  node *p = it->p;
К>  int d = it->d;

К>  do // чтобы выйти по break вместо кудрявых if-else
К>  {
К>    // от левого вверх: A->B
К>    if(p->up && p->up->left==p) { --d; p=p->up; break; }

К>    // от родителя вправо: B->C
К>    if(d<n && p->right) { ++d; p=p->right; break; }

К>    // от правого - вверх по правой ветке C->...->D и затем вверх ->E
К>    while(!p->up || p->up->right==p) { --d; p=p->up; }
К>    if(!p) break; // вылетели из дерева, это значит, мы были крайне правым узлом
К>    --d; p=p->up;
К>  }
К>  while(false);

  it->>p = p;
  it->>d = d;
К>}
К>bool end(iter *it)
К>{
К>  return !it->p; // признак конца - вылет из дерева
К>}

К>bool print_layer(node *root, int n)
К>{
К>  bool contd = false; // to be continued на следующем уровне
К>  iter it;

К>  for(start(root,n,it); !end(it); next(n,it))
К>  {
К>    if(d==n)
К>    {
К>      printf("%d ", p->data);
К>      contd = contd||p->left||p->right;
К>    }
К>  }
К>}
К>

большое спасибо, ты мне очень помог!

Здравствуйте, Red_Baron, Вы писали:

(а вот оверквотинг — это лишнее)

R_B>большое спасибо, ты мне очень помог!

Попробуй догадаться, как можно улучшить этот алгоритм Так сказать, в качестве бонус-трека к твоей исходной задаче.

---

И ещё. Можно реализовать очередь (список) обхода прямо в узлах дерева.

struct node
{
  node *up; // обратная связь - по желанию
  node *left, *right; // связи с дочерними узлами, естественно, нужны

  Some data;

  node *next; // следующий узел в порядке обхода в ширину (инициализируется в процессе обхода)
  int depth; // измерение глубины - по желанию (вдруг интересно окажется)
};

node *enqueue(node *q, node *n) // возвращает обновлённый указатель очереди
{
  q->next = n;
  return n;
}
node *enqueue_children(node *q, node *n)
{
  if(n->left ) { q = enqueue(q, n->left ); n->left ->depth = n->depth + 1; }
  if(n->right) { q = enqueue(q, n->right); n->right->depth = n->depth + 1; }
  return q;
}

После того, как обход в ширину выполнен первый раз, можно многократно оббегать дерево по существующим значениям next.
Естественно, после модификации дерева нужно освежить их.

Здравствуйте, Кодт, Вы писали:

К>Если есть восходящие связи, то можно обойтись без рекурсии. Итератор дерева состоит из указателя на узел дерева и глубиномера.

Ой как полезно возвращаться к старым тредам. До меня только сейчас дошло, что дерево-то двоичное. Поэтому узлы на слое k кодируются k-битным числом, от 0 до 2^k — 1, в порядке обхода. Очередной бит 0 — шаг влево, 1 — шаг вправо. Чтобы обойти k-й слой полного дерева, нужно сделать 2^k спусков с вершины по k шагов каждый. Для обхода всего дерева глубины N потребуется
summa[k = 0..N] k * 2^k, что есть O(N * 2^N) или O(M * log M), где M — количество вершин. Сложность по памяти — O(log M) (адрес узла задается 2^N-битным числом).

К>Итератор с глубиномером работает точно так же, как и обычный итератор поперечного обхода, с той лишь разницей, что игнорирует узлы, лежащие ниже заданной глубины.

Здесь (временная) сложность такая же, хотя получается немножко по-другому: для обхода очередного слоя нужно пройти каждое ребро (причем дважды — вниз и вверх). Всего ребер дерева глубины N — O(2^N), что опять-таки надо суммировать по глубинам слоев. Однако, поскольку в каждом узле надо хранить ссылку наверх, сложность по памяти — O(M).

Я нигде не наврал?

Здравствуйте, Аноним, Вы писали:

А>Привет All!
А>может ли кто то подсказать алгорит(или можна код на С), как распечатать данные бинарного дерева по горизонтали(т.е. по уровням)

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