Преобразование многострочного дерева в формат левого ребенка / правого брата?

Question

Я пытаюсь написать код C ++, который при наличии многострочного дерева преобразует это дерево в двоичное дерево, представленное в формате left-child / right-sibling .Например, учитывая это дерево:

          A
        / | \
       B  C  D
     / | \   |
    E  F  G  H
      / \
     I   J

Я хотел бы вывести это дерево:

           A
          /
         B
       /   \
      E     C
       \     \
        F     D
       / \   /
      I   G H
       \
        J

Я не уверен, как решить эту проблему.Как я должен думать об этом?

Answer 1

---

Предполагается,

Предполагается, что двоичное дерево подразумевается в соответствии с https://en.wikipedia.org/wiki/Binary_tree, а многоходовое дерево похоже на двоичное дерево, но со счетными подузлами вместонеобязательные левый и правый подузлы, тогда как алгоритм соответствует https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree.

---

Типам

Типами могут быть следующие шаблоны - для многоканальногодерево:

template <typename T>
class CMultiWayTree {
public:
    typedef CMultiWayTree<T>*   NodePtr;
    typedef list<NodePtr>       List;
public:
    T                           m_tData;
protected:
    List                        m_lNodes;
public:
    // ...
};

... и для двоичного дерева:

template <typename T>
class CBinaryTree {
public:
    typedef CBinaryTree<T>*     NodePtr;
public:
    typedef CGeneralTree<T>*    MTNodePtr;
public:
    T                           m_tData;
protected:
    NodePtr                     m_pLeftNode;
    NodePtr                     m_pRightNode;
    //...
};

---

код

Если принять правильное, токод может быть как ниже.Принимая во внимание, что алгоритм преобразования («двоичное дерево левого потомка справа») реализован в конструкторе «CBinaryTree (MTNodePtr pmtToConvert)».

#include    <iostream>
#include    <list>

using namespace std;

string  ident(int nDepth) {
    string  sIndent;

    for (int n = 0; n < nDepth; n++) {
        sIndent += ' ';
    }
    return sIndent;
}

template <typename T>
class CMultiWayTree {
public:
    typedef CMultiWayTree<T>*   NodePtr;
    typedef list<NodePtr>       List;
public:
    T                           m_tData;
protected:
    List                        m_lNodes;
public:
    CMultiWayTree(const T& rtData) {
        m_tData = rtData;
    };
    virtual ~CMultiWayTree() {
        typename List::iterator it;

        it = m_lNodes.begin();
        while ( it != m_lNodes.end() ) {
            delete (*it);
            it++;
        }
    }
    virtual const T& getNode() { 
        return m_tData;
    };
    virtual void goToFirstChildNode(typename List::iterator& it) { 
        it = m_lNodes.begin();
    };
    virtual void goToNextChildNode(typename List::iterator& it) { 
        it++;
    };
    virtual bool getChildNode(typename List::iterator& it, NodePtr& pNode) { 
        bool    bIsChildNode;

        bIsChildNode = it != (m_lNodes.end());
        if ( bIsChildNode ) {
            pNode = (*it);
        } else {
            pNode = NULL;
        }
        return bIsChildNode;
    };
    virtual NodePtr appendChildNode(const T& rtData) { 
        NodePtr pNode = new CMultiWayTree(rtData);
        m_lNodes.push_back(pNode);
        return pNode;
    };
    virtual void print(ostream& os, int nDepth = 0) { 
        NodePtr     pNode;
        typename List::iterator     it;

        os << ident(nDepth) << m_tData << endl;
        nDepth++;
        goToFirstChildNode(it);
        while ( getChildNode(it, pNode) ) {
            pNode->print(os, nDepth);
            goToNextChildNode(it);
        }
    };
};

template <typename T>
class CBinaryTree {
public:
    typedef CBinaryTree<T>*     NodePtr;
public:
    typedef CMultiWayTree<T>*   MTNodePtr;
public:
    T                           m_tData;
protected:
    NodePtr                     m_pLeftNode;
    NodePtr                     m_pRightNode;
public:
    CBinaryTree(const T& rtData) {
        m_tData = rtData;
        m_pLeftNode = NULL;
        m_pRightNode = NULL;
    };
    CBinaryTree(GTNodePtr pmtToConvert) {
        if ( pmtToConvert != NULL ) {
            NodePtr                                     pNewNode;
            MTNodePtr                                   pNode;
            typename CMultiWayTree<T>::List::iterator   it;

            m_tData = pmtToConvert->m_tData;

            m_pRightNode = NULL;
            pmtToConvert->goToFirstChildNode(it);
            if ( pmtToConvert->getChildNode(it, pNode) ) {
                pNewNode = new CBinaryTree(pNode);
                m_pLeftNode = pNewNode;
                pmtToConvert->goToNextChildNode(it);
            } else {
                m_pLeftNode = NULL;
            }
            while ( pmtToConvert->getChildNode(it, pNode) ) {
                pNewNode = pNewNode->setRight(new CBinaryTree(pNode));
                pmtToConvert->goToNextChildNode(it);
            }
        }
    };
    virtual ~CBinaryTree() {
        if ( m_pLeftNode != NULL ) {
            delete m_pLeftNode;
            m_pLeftNode = NULL;
        }
        if ( m_pRightNode != NULL ) {
            delete m_pRightNode;
            m_pRightNode = NULL;
        }
    };
    virtual NodePtr setRight(NodePtr pNew) {
        if ( m_pRightNode != NULL ) {
            delete m_pRightNode;
        }
        m_pRightNode = pNew;
        return m_pRightNode;
    }
    virtual void print(ostream& os, int nDepth = 0, char chPreFix = '\0') { 
        NodePtr     pNode;

        if ( chPreFix != '\0' ) {
            os << ident(nDepth - 1) << chPreFix << m_tData << endl;
        } else {
            os << ident(nDepth) << m_tData << endl;
        }
        nDepth++;
        if ( m_pRightNode != NULL ) {
            m_pRightNode->print(os, nDepth, 'r');
        }
        if ( m_pLeftNode != NULL ) {
            m_pLeftNode->print(os, nDepth, 'l');
        }
    };
};

int main() {
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNode = new CMultiWayTree<char>('A');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeB = pMultiWayTreeNode->appendChildNode('B');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeC = pMultiWayTreeNode->appendChildNode('C');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeD = pMultiWayTreeNode->appendChildNode('D');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeE = pMultiWayTreeNodeB->appendChildNode('E');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeF = pMultiWayTreeNodeB->appendChildNode('F');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeG = pMultiWayTreeNodeB->appendChildNode('G');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeH = pMultiWayTreeNodeD->appendChildNode('H');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeI = pMultiWayTreeNodeF->appendChildNode('I');
    CMultiWayTree<char>::NodePtr    pMultiWayTreeNodeJ = pMultiWayTreeNodeF->appendChildNode('J');

    cout << "Input (multi-way tree):" << endl;
    pMultiWayTreeNode->print(cout, 3);
    cout << endl;

    CBinaryTree<char>::NodePtr  pBinaryTreeNode = new CBinaryTree<char>(pMultiWayTreeNode);

    cout << "Output (binary tree):" << endl;
    pBinaryTreeNode->print(cout, 3);

    delete pMultiWayTreeNode;
    delete pBinaryTreeNode;

    return 0;
}

---

Вывод

Программа создаст следующий вывод:

Input (multi-way tree):
   A
    B
     E
     F
      I
      J
     G
    C
    D
     H

Output (binary tree):
   A
   lB
    rC
     rD
      lH
    lE
     rF
      rG
      lI
       rJ

Answer 2

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

Во-первых, действительно легко преобразовать пустое дерево в формат LC / RS: оно возвращается как пустое дерево.

С другой стороны, предположим, что у вас есть непустое дерево.Начните с преобразования каждого из его дочерних элементов в формат LC / RS (рекурсивно).Например, учитывая это дерево:

          A
        / | \
       B  C  D
     / | \   |
    E  F  G  H
      / \
     I   J

Вы начнете с рекурсивного преобразования каждого дочернего элемента в LC / RS, возвращая эти три дерева:

   B        C         D
  /                  /
 E                  H
  \
   F
  / \
 I   G
  \
   J

Эти деревья в настоящее времясвободно плавающий и не связанный друг с другом.Но так как вы знаете, что они братья и сестры, вы захотите сделать C правильным потомком B, а D - правильным потомком C. По сути, это обход связанного списка.Вот как все должно выглядеть, когда вы закончите:

         B
       /   \
      E     C
       \     \
        F     D
       / \   /
      I   G H
       \
        J

После того, как вы это сделаете, все, что осталось сделать, это сделать B левым потомком A, как показано здесь:

           A
          /
         B
       /   \
      E     C
       \     \
        F     D
       / \   /
      I   G H
       \
        J

Напомним, что логика выглядит следующим образом:

• Если дерево для преобразования пусто, вернуть пустое дерево.
• В противном случае:
  • Рекурсивно преобразуйте каждого из дочерних элементов корневого узла в формат LC / RS.
  • Итерируйте по этим деревьям, назначая правые дочерние ссылки для связывания деревьев вместе.
  • Назначьте указатель левого дочернего элемента A на точкук результирующему дереву (или к нулю, если у него нет дочерних элементов).

Я оставлю вам детали C ++ для заполнения. Если вы попыталисьЧтобы решить эту проблему и столкнуться с трудностями, не стесняйтесь задавать дополнительный вопрос с подробным описанием кода, который вы написали до сих пор, а также с конкретным неудачным тестом или конкретными ошибками компилятора, с которыми вы сталкиваетесь.Удачи!