c++ - 二分木: 反復的な順不同印刷

Question

私は組み込みのインオーダートラバーサル (ネストされたを使用) を使用して、赤黒ツリーの実装を作成しましたclass Iterator。

順序トラバーサルを使用してバイナリツリーをグラフィカルに出力する (可能であれば反復的な) アルゴリズムを探しています。

印刷方向は関係ありません。つまり、コマンドライン出力のツリーは、次のように方向付け (フォーマット) できます。

またはこのように：

 |1
 |
 |
2
 | |3
 | |
 |4
   |
   |5

または上下逆さまでも構いませんが、以下に示す方法を使用して、インオーダートラバーサルを使用してツリーを出力する必要があります。

void Iteraor::first(); // Traverses to the first node.
void Iterator::next(); // Traverses to the next node.
void Iterator::last(); // Traverses to the last node.

可能なので、次のようにします。

RBTree tree;
/* Tree init. */
Iterator from(&tree), until(&tree);
from.first();
until.last();
for (Iterator i = from; i != until; i.next()) {
// PRINTING.
}

これは元のコードです:

/** A program for Red-Black Tree manipulation: insertion and value retrieval.
  * All position relations (first, last, previous, next) are in-order.
  */

class RBTree {
    struct Node {
        enum class Colour : bool { RED, BLACK };
        int value;
        Node *left, *right, *parent;
        Colour colour;
    public:
        /* ... */
    };
    class Iterator {
        class Stack {
            /* ... */
        };
        Stack stack;
        const RBTree* const tree; // Once set, neither the reference nor the referenced object's attributes can be modified.
        Node* pointer;
    public:
        Iterator(const RBTree*);
        void first();
        void next();
        void last();
        /* ... */
        Node* getNode() const;
        bool operator != (const Iterator&) const;
    };
    Node *root;
    Iterator iterator;
public:
    RBTree() : root(nullptr), iterator(this) {}
    /* ... */
    bool printTree() const;
    ~RBTree() { deleteTree(); }
};

// TREE // public: //

/* ... */

bool RBTree::printTree() const {
    if (root != nullptr) {
        // print ??
        return true;
    }
    else
        return false;

}

// NODE: Ensures the proper connection. //

void RBTree::Node::setLeft(Node *p_left) {
    left = p_left;
    if (p_left != nullptr)
        p_left->parent = this;
}

void RBTree::Node::setRight(Node *p_right) {
    right = p_right;
    if (p_right != nullptr)
        p_right->parent = this;
}

// ITERATOR //

RBTree::Iterator::Iterator(const RBTree* p_tree) : tree(p_tree), pointer(p_tree->root) {}

// Traverses to the first node (leftmost).
void RBTree::Iterator::first() {
    if (pointer != nullptr) {
        while (true) {
            if (pointer != nullptr) {
                stack.push(pointer);
                pointer = pointer->left;
            }
            else {
                pointer = stack.peek();
                break;
            }
        }
    }
}

// Traverses to next node in-order.
void RBTree::Iterator::next() {
    if (pointer != nullptr) {
        if (!stack.isEmpty()) {
            pointer = stack.pop();
            if (pointer->right != nullptr) {
                pointer = pointer->right;
                first();
            }
        }
    }
}

// Traverses to the last node (rightmost).
void RBTree::Iterator::last() {
    pointer = tree->root;
    if (pointer != nullptr)
        while (pointer->right != nullptr)
            pointer = pointer->right;
    stack.clear();
}

/* ... */

RBTree::Node* RBTree::Iterator::getNode() const {
    return pointer;
}

bool RBTree::Iterator::operator != (const Iterator& p_iterator) const {
    return pointer != p_iterator.pointer ? true : false;
}

私は同様の質問で回答を調査しましたが、どのアルゴリズムも順序通りのトラバーサルを利用していません (そしてそれらのほとんどは再帰的です)。

編集：

@nonsensickle のアドバイスに従って、コードは最小限に切り詰められています。

c++ - 二分木: 反復的な順不同印刷

1 に答える 1

Related

Reference