Обход бинарных деревьев алгоритмы


Недавно я начал изучать бинарное дерево. Ниже приведен код для типичного узел для дерева (без комментарий код требуется для этого):

typedef unsigned int uint;

template<typename T>
class BinaryNode
{
  T t_Data;
  BinaryNode *pt_Left, *pt_Right;

public:
  BinaryNode (const T &data) : t_Data(data), pt_Left(0), pt_Right(0) {}

  void Insert (const T &data)
  {
    if(this->t_Data == data)
      return;

    BinaryNode<T> *&pNode = (data < this->t_Data)? this->pt_Left : this->pt_Right;
    if(pNode == 0)  pNode = new BinaryNode<T>(data);
    else  pNode->Insert(data);
  }

  template<uint SIZE>
  static
  BinaryNode<T>* GenerateTree (const T (&arr)[SIZE])
  {
    return GenerateTree(arr, SIZE);
  }
  static
  BinaryNode<T>* GenerateTree (const T *arr, const uint SIZE)
  {
    BinaryNode<T> *pHead = new BinaryNode<T>(arr[0]);
    for(uint i = 0; i < SIZE; i++)
      pHead->Insert(arr[i]);
    return pHead;
  }

  operator const T& () const { return t_Data; }
  BinaryNode* const getLeft () const { return pt_Left; }
  BinaryNode* const getRight () const { return pt_Right; }
};

Например, чтобы заполнить это дерево с Чара узлов, нужно вызвать генерировать функции,

const char letters[] = {'F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'I', 'H'};
BinaryNode<char> *pHead = BinaryNode<char>::GenerateTree(letters);

Вопрос: Я хотел реализовать, его предварительного заказа, в порядке, после того, обходы в рекурсивные как итерационный характер. Проходим пересечение вектора<> vTraversal ко всем функциям для заполнения обход результатов.

Рекурсивные очень просто:

template<typename T>
void PreOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
  if(pNode == 0)
    return;
  vTraverse.push_back(*pNode);
  PreOrderRecursive(pNode->getLeft(), vTraverse);
  PreOrderRecursive(pNode->getRight(), vTraverse);
}

template<typename T>
void InOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
  if(pNode == 0)
    return;
  InOrderRecursive(pNode->getLeft(), vTraverse);
  vTraverse.push_back(*pNode);
  InOrderRecursive(pNode->getRight(), vTraverse);
}

template<typename T>
void PostOrderRecursive (const BinaryNode<T>* const pNode, vector<T> &vTraverse)
{
  if(pNode == 0)
    return;
  PostOrderRecursive(pNode->getLeft(), vTraverse);
  PostOrderRecursive(pNode->getRight(), vTraverse);
  vTraverse.push_back(*pNode);
}

Вы можете видеть рекурсивные функции легко понятны и могут быть связаны друг с другом.

Однако, в итерационных функций, у меня есть проблема. Я в состоянии найти хорошее решение для обход в прямом порядке, немного комплексное решение в обход в обратном порядке и не элегантное решение на обход в обратном порядке:

template<typename T>
void PreOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
  vector<const BinaryNode<T>*> record;
  record.push_back(pNode);
  while(record.size() != 0)
  {
    const BinaryNode<T> *pN = record.back();
    record.pop_back();
    if(pN == 0)
      continue;
    record.push_back(pN->getRight());
    record.push_back(pN->getLeft());
    vTraversal.push_back(*pN);
  }
}

template<typename T>
void InOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
  vector<const BinaryNode<T>*> record;
  record.push_back(pNode);
  while(true)
  {
    const BinaryNode<T> *pN = record.back();
    record.pop_back();
    if(pN == 0)
    {
      if(record.size() == 0)
        break;
      vTraversal.push_back(*record.back());
      record.pop_back();
      continue;
    }
    record.push_back(pN->getRight());
    record.push_back(pN);
    record.push_back(pN->getLeft());
  }
}

template<typename T>
void PostOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
   // :(
}

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



3916
3
задан 30 ноября 2011 в 06:11 Источник Поделиться
Комментарии
1 ответ

Ты хотела сделать это наедине?

class BinaryNode
{
public:
T t_Data;
BinaryNode *pt_Left, *pt_Right;

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

Чтобы лучше отделить проблемы, одной идеи, которую вы можете попробовать, чтобы определить внешнюю структуру, которая содержит BinaryNode. Что-то вроде этого:

template <typename T>
class BinaryTree
{
public:
BinaryTree() : root(0) {}
// rest of your interface methods here
// Insert, GenerateTree etc.
// ...

private:
struct BinaryNode
{
T data;
BinaryNode *left, *right;
void Insert(const T &data_);
};
BinaryNode *root;
};


Для вашего GenerateTree способ, лучше, если у вас это займет итераторы, а не так что он работает с другими контейнерами, кроме сырых массивов. Он только требует незначительного изменения GenerateTree:

template <typename FORWARD>
static BinaryNode<T>* GenerateTree (FORWARD begin, const FORWARD &end)
{
if(begin == end) return;

BinaryNode<T> *pHead = new BinaryNode<T>(*begin);
while(++begin != end)
{
pHead->Insert(*begin);
}
return pHead;
}

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

const char letters[] = {'F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'I', 'H'};
size_t size = sizeof(letters);
BinaryTree<char> letter_tree(letters, letters + size);


Ваш PreOrderIterative функция использует СТД::вектор в стек. Почему бы не переделать его для использования с std::стек напрямую и улучшения читабельности?

void PreOrderIterative (const BinaryNode<T>* const pNode, vector<T> &vTraversal)
{
stack<const BinaryNode<T>*> record;
record.push(pNode);
while( !record.empty() )
{
const BinaryNode<T> *pN = record.top();
record.pop();

if(pN->getRight()) record.push(pN->getRight());
if(pN->getLeft()) record.push(pN->getLeft());
vTraversal.push_back(*pN);
}
}

Я не смотрел на InOrderIterative в слишком много деталей, но я представляю, что подобная оптимизация может быть применена к нему, а также. Я оставлю это в качестве упражнения для вас.

Для PostOrderRecursive, похоже, вы хотите посетить узлы в таком порядке:

     7
/ \
3 6
/ \ / \
1 2 4 5

Один из способов сделать это повторно, чтобы начать в корне и, как вы ходьбы дереве разверните первый ее правый узел затем разверните левую узла после. Вы можете отслеживать, какие узлы посетить со стеком, похожими на PreOrderIterative. При посещении каждого узла вы добавите его в vTraversal. После этого vTraversal будет содержать правильном порядке, за исключением в обратном. Применить СТД::обратный , чтобы получить окончательный результат:

template<typename T>
void PostOrderIterative (const BinaryNode<T>* const root, vector<T> &vTraversal)
{
if(!root) return;

//start with the root
stack<const BinaryNode<T>*> visit_nodes;
visit_nodes.push(root);
while( !visit_nodes.empty() )
{
// visting the node on top of stack
const BinaryNode<T> *curr_node = visit_nodes.top();
vTraversal.push_back(*curr_node);
visit_nodes.pop();

// add nodes that still need to be visited and expand.
// right needs to be handled before left so push in reverse order.
if( curr_node->getLeft() ) visit_nodes.push(curr_node->getLeft());
if( curr_node->getRight() ) visit_nodes.push(curr_node->getRight());
}

// vTraveral contains the desired order but in reverse.
std::reverse(vTraversal.begin(), vTraversal.end());
}

3
ответ дан 1 декабря 2011 в 01:12 Источник Поделиться