Есть бинарное дерево. Узел дерева определяется следующей структурой:

struct TreeNode
{
TreeNode* pParent;
TreeNode* pLeft;
TreeNode* pRight;
int Data;
};

Дан указатель на голову дерева: pHead.
Необходимо написать функцию печатающую данные из дерева уровень за уровнем.
Те сначала должно быть напечатано pHead->Data, потом pHead->pLeft->Data, далее pHead->pRight->Data и т.д.

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

__>Есть бинарное дерево. Узел дерева определяется следующей структурой:

__>struct TreeNode
__>{
__> TreeNode* pParent;
__> TreeNode* pLeft;
__> TreeNode* pRight;
__> int Data;
__>};

__>Дан указатель на голову дерева: pHead.
__>Необходимо написать функцию печатающую данные из дерева уровень за уровнем.
__>Те сначала должно быть напечатано pHead->Data, потом pHead->pLeft->Data, далее pHead->pRight->Data и т.д.

Данный алгоритм носит гордое название "Поиск в ширину"
Иногда его еще называют "Волновой алгоритм"

То, что у нас не обычный граф, а дерево, вроде ничего особо полезного не дает.

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

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

__>>Есть бинарное дерево. Узел дерева определяется следующей структурой:

__>>struct TreeNode
__>>{
__>> TreeNode* pParent;
__>> TreeNode* pLeft;
__>> TreeNode* pRight;
__>> int Data;
__>>};

__>>Дан указатель на голову дерева: pHead.
__>>Необходимо написать функцию печатающую данные из дерева уровень за уровнем.
__>>Те сначала должно быть напечатано pHead->Data, потом pHead->pLeft->Data, далее pHead->pRight->Data и т.д.

T>Данный алгоритм носит гордое название "Поиск в ширину"
T>Иногда его еще называют "Волновой алгоритм"

T>То, что у нас не обычный граф, а дерево, вроде ничего особо полезного не дает.
Но мы ведь не просто ищем элемент. Мы хотим распечатать сначала узлы глубины 0, потом 1 и т.д.
Собственно, програмку можешь написать?

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

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

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

__>>>Есть бинарное дерево. Узел дерева определяется следующей структурой:

__>>>struct TreeNode
__>>>{
__>>> TreeNode* pParent;
__>>> TreeNode* pLeft;
__>>> TreeNode* pRight;
__>>> int Data;
__>>>};

__>>>Дан указатель на голову дерева: pHead.
__>>>Необходимо написать функцию печатающую данные из дерева уровень за уровнем.
__>>>Те сначала должно быть напечатано pHead->Data, потом pHead->pLeft->Data, далее pHead->pRight->Data и т.д.

T>>Данный алгоритм носит гордое название "Поиск в ширину"
T>>Иногда его еще называют "Волновой алгоритм"

T>>То, что у нас не обычный граф, а дерево, вроде ничего особо полезного не дает.
__>Но мы ведь не просто ищем элемент. Мы хотим распечатать сначала узлы глубины 0, потом 1 и т.д.
Для этого достаточно распечатать очередь, а действовать пока очередь не пуста.

__>Собственно, програмку можешь написать?
Псевдокод:

queue<TreeNode*> q;
q.push_back(pRoot);
while (!q.empty())
{
  TreeNode* cur = q.front(); q.pop_front();
  cout << cur.Data << endl;
  if (cur->pLeft)
    q.push_back(cur->pLeft);
  if (cur->pRight)
    q.push_back(cur->pRight);
}

Для определения величины глубины каждой вершины — изменения минимальные.

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

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

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

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

__>>>>Есть бинарное дерево. Узел дерева определяется следующей структурой:

__>>>>struct TreeNode
__>>>>{
__>>>> TreeNode* pParent;
__>>>> TreeNode* pLeft;
__>>>> TreeNode* pRight;
__>>>> int Data;
__>>>>};

__>>>>Дан указатель на голову дерева: pHead.
__>>>>Необходимо написать функцию печатающую данные из дерева уровень за уровнем.
__>>>>Те сначала должно быть напечатано pHead->Data, потом pHead->pLeft->Data, далее pHead->pRight->Data и т.д.

T>>>Данный алгоритм носит гордое название "Поиск в ширину"
T>>>Иногда его еще называют "Волновой алгоритм"

T>>>То, что у нас не обычный граф, а дерево, вроде ничего особо полезного не дает.
__>>Но мы ведь не просто ищем элемент. Мы хотим распечатать сначала узлы глубины 0, потом 1 и т.д.
T>Для этого достаточно распечатать очередь, а действовать пока очередь не пуста.

__>>Собственно, програмку можешь написать?
T>Псевдокод:
T>

T>queue<TreeNode*> q;
T>q.push_back(pRoot);
T>while (!q.empty())
T>{
T>  TreeNode* cur = q.front(); q.pop_front();
T>  cout << cur.Data << endl;
T>  if (cur->pLeft)
T>    q.push_back(cur->pLeft);
T>  if (cur->pRight)
T>    q.push_back(cur->pRight);
T>}
T>

T>Для определения величины глубины каждой вершины — изменения минимальные.

Да, клёва... но нужна доп память O(N). за O(1) не получится реализовать?

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

__>Да, клёва... но нужна доп память O(N). за O(1) не получится реализовать?

Без дополнительной памяти пострадает производительность.
Есть у меня предчуствие, что быстрее O(N^2) не получится, т.к. чтобы вывести уровень мы должны перебрать все вершины предыдущего уровня, а их у нас возможности сохранить нет, т.е. их тоже генерить придется...

Есть возможность уменьшить количество используемой памяти, увеличив время работы (раз уж у нас память так критична). Где у нас тратится больше всего дополнительной памяти? На последнем уровне. А если мы его хранить не будем, а будем выводить по предпоследнему? Памяти потратится в 2 раза меньше. А если мы еще и предпоследний хранить не будем, а будем выводить предпоследний и последний по пред-предпоследнему? Ну и т.д. Все сказанное справедливо для достаточно сбалансированного дерева.

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

__>Необходимо написать функцию печатающую данные из дерева уровень за уровнем.

Алгоритм Танчика — O(N) времени, O(N) памяти (список).

Рекурсивный алгоритм — O(N^2) времени, O(N) памяти (стек).

void print(Tree* node);

bool prints(Tree* node, int depth) // сообщает, есть ли что-то на следующем горизонте
{
  if(!node)
    return false;
  else if(level==0)
  {
    print(node);
    return node->left || node->right;
  }
  else
  {
    bool l = prints(node->left,depth-1);
    bool r = prints(node->right,depth-1);
    return l||r;
  }
}
void printtree(Tree* root)
{
  int depth=0;
  while(prints(root,depth)) ++depth;
}

От рекурсии (и, соответственно, от расхода памяти) можно избавиться.

void prints(Tree* node, int depth, Tree*& restart)
{
  int level=depth-1; // текущий уровень
  restart=NULL; // узел на глубине depth, начиная с которого мы будем выполнять следующий заход

  while(true)
  {
    bool leaf = !node->left && !node->right;
    bool deep = level==depth;

    if(deep)
    {
      print(node);
      if(!leaf && !restart) restart=node;
    }

    if(leaf||deep) // идём вверх-вправо
    {
      while(level>0 && node->parent->right==node)
      {
        node=node->parent;
        --level;
      }
      if(level<0) break; // это был последний элемент
      node = node->right;
      ++level;
    }
    else // идём вниз
    {
      if(node->left)
        node = node->left;
      else // мы же знаем, что это не лист
        node = node->right;
      ++level;
    }
  }
}
void printtree(Tree* node)
{
  if(!node) return;

  print(node);
  int depth=1;
  while(node)
  {
    prints(node,depth,node);
    ++depth;
  }
}

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

К>От рекурсии (и, соответственно, от расхода памяти) можно избавиться.
К>

К>void prints(Tree* node, int depth, Tree*& restart)
К>{
К>  int level=depth-1; // текущий уровень
К>  restart=NULL; // узел на глубине depth, начиная с которого мы будем выполнять следующий заход

К>  while(true)
К>  {
К>    bool leaf = !node->left && !node->right;
К>    bool deep = level==depth;

К>    if(deep)
К>    {
К>      print(node);
К>      if(!leaf && !restart) restart=node;
К>    }

К>    if(leaf||deep) // идём вверх-вправо

// Наверное, здесь имелось в виду "идем вверх-влево до упора, потом вверх-вправо, 
// пока нельзя будет свернуть вниз-вправо"?
// А поэтому надо кое-что подправить...

К>    {
К>      while(level>0 && node->parent->right==node)
К>      {
К>        node=node->parent;
К>        --level;
К>      }
/*
К>      if(level<0) break; // это был последний элемент
*/
        if(level==0) break; // это был последний элемент
        node = node->parent;
        --level;
        while(level>0 && !node->right && node->parent->left==node)
        {
          node=node->parent;
          --level;
        }
        if(!node->right) break;
К>      node = node->right;
К>      ++level;
К>    }
К>    else // идём вниз
К>    {
К>      if(node->left)
К>        node = node->left;
К>      else // мы же знаем, что это не лист
К>        node = node->right;
К>      ++level;
К>    }
К>  }
К>}
К>

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

<>

Ну, в общем-то я думал и писал одновременно, поэтому если где лажанулся, то извините.

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

__>Есть бинарное дерево. Узел дерева определяется следующей структурой:

__>struct TreeNode
__>{
__> TreeNode* pParent;
__> TreeNode* pLeft;
__> TreeNode* pRight;
__> int Data;
__>};

__>Дан указатель на голову дерева: pHead.
__>Необходимо написать функцию печатающую данные из дерева уровень за уровнем.
__>Те сначала должно быть напечатано pHead->Data, потом pHead->pLeft->Data, далее pHead->pRight->Data и т.д.

одно слово: FIFO

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

X>одно слово: FIFO

Это? http://www.rsdn.ru/Forum/?mid=875092

Автор: Tan4ik
Дата: 29.10.04

А ещё варианты, кроме очереди и поуровневых обходов?

__>struct TreeNode
__>{
__> TreeNode* pParent;
__> TreeNode* pLeft;
__> TreeNode* pRight;
__> int Data;
__>};

Итераторы по бинарному дереву рулят.

void PrintTreeLevel2(const TreeNode *root, int depth)
{
    assert(root);
    assert(depth >= 0);

    int level = 0;
    const TreeNode* now = root;
    while ( (level < depth) && now->leftChild)
    {
        now = now->leftChild;
        ++level;
    }

    while (now)
    {
        if (level == depth)
        {
            // printf("{%d}", now->value);
        }

        if ( (level < depth) && now->rightChild )
        {
            now = now->rightChild;
            ++level;
            while ( (level < depth) && now->leftChild )
            {
                now = now->leftChild;
                ++level;
            }
        }
        else
        {
            if (now->parent)
            {
                const TreeNode* parent = now->parent;
                while (parent && (parent->rightChild == now))
                {
                    now = parent;
                    parent = parent->parent;
                    --level;
                }
                now = parent;
                --level;
            }
            else
                now = NULL;
        }
    }

    printf("\n");
}

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

К>Алгоритм Танчика — O(N) времени, O(N) памяти (список).

...

К>От рекурсии (и, соответственно, от расхода памяти) можно избавиться.

К>

К>void prints(Tree* node, int depth, Tree*& restart)
К>...
К>

Здесь засада. int depth позволяет пройти не более чем INT_MAX уровней. Это много, но не бесконечно. Сложность по памяти — O(log N), как ни крути.