C++ グラフィック レイヤー順序のトラバーサルと、スマート ポインターによって構築されたバイナリ ツリーのレイヤーごとの印刷

二分木は非常に一般的なデータ構造であり、その要素を走査する方法に関する記事は無数にあります。しかし、ほとんどの記事は前順/中順/後順のトラバースについて説明しており、印刷要素をレイヤーごとに説明している記事は少なく、既存の記事の説明も比較的曖昧で読みにくいです。この記事では、レベル順序トラバーサルの実装を理解するのに役立つ、鮮やかな画像と明確なコードを使用し、同時に最新の C が提供するスマート ポインターを使用して、ツリー データ構造のリソース管理を簡素化します。

関連チュートリアル: データ構造ツリー チュートリアル

それでは、本題に入りましょう。

スマート ポインタを使用してバイナリ ツリーを構築する

ここで実装したいのは、バイナリ サーチ ツリーを単純にシミュレートし、バイナリ サーチ ツリーの要件を満たす挿入関数を提供するバイナリ ツリーです。 、順序通りのトラバースを含む。同時に、shared_ptr を使用してリソースを管理します。

ここでは、insert と ldr という 2 つのメソッドのみを実装します。他のメソッドの実装については、この記事では取り上げませんが、それらについては後で説明します。はじめに:

struct BinaryTreeNode: public std::enable_shared_from_this<BinaryTreeNode> {
    explicit BinaryTreeNode(const int value = 0)
    : value_{value}, left{std::shared_ptr<BinaryTreeNode>{}}, right{std::shared_ptr<BinaryTreeNode>{}}
    {}

    void insert(const int value)
    {
        if (value < value_) {
            if (left) {
                left->insert(value);
            } else {
                left = std::make_shared<BinaryTreeNode>(value);
            }
        }

        if (value > value_) {
            if (right) {
                right->insert(value);
            } else {
                right = std::make_shared<BinaryTreeNode>(value);
            }
        }
    }

    // 中序遍历
    void ldr()
    {
        if (left) {
            left->ldr();
        }

        std::cout << value_ << "\n";

        if (right) {
            right->ldr();
        }
    }

    // 分层打印
    void layer_print();

    int value_;
    // 左右子节点
    std::shared_ptr<BinaryTreeNode> left;
    std::shared_ptr<BinaryTreeNode> right;

private:
    // 层序遍历
    std::vector<std::shared_ptr<BinaryTreeNode>> layer_contents();
};

私たちのノード オブジェクトは enable_shared_from_this から継承しています。通常、これは必要ありませんが、レイヤー順序のトラバーサル中の操作を容易にするために、これを構築する必要があります。 this から スマート ポインターなので、この手順は必要です。 insert は、ルートより小さい要素を左側のサブツリーに挿入し、ルートより大きい要素を右側のサブツリーに挿入します。ldr は最も一般的な順序トラバーサルで、ここでは View に実装されています。通常の方法でツリー内のすべての要素を取得します。

ノード ノードの場合、グローバル/ローカル オブジェクトとして初期化するのではなく、make_shared を使用してノードを作成するのが最善であることに注意してください。そうしないと、レイヤー順序のトラバーサル中に が発生します。 .shared_ptr を破棄すると、オブジェクトも破棄され、未定義の動作が発生します。

ここで、データのセット [3, 1, 0, 2, 5, 4, 6, 7] があるとします。最初の要素をルートとして、すべてのデータをツリーに挿入すると、次のようになります。結果は、次のようなバイナリ ツリーになります:

auto root = std::make_shared<BinaryTreeNode>(3);
root->insert(1);
root->insert(0);
root->insert(2);
root->insert(5);
root->insert(4);
root->insert(6);
root->insert(7);

ノードが 4 つのレイヤーに分割されていることがわかります。次に、レイヤーごとに印刷する必要があります。どのように行うか?

レベル順次トラバーサル

実際、アイデアは非常に単純です。幅優先のアイデアを採用し、最初にノードのすべての子を出力し、次に子ノードの子を出力します。 。

上の図を例にとると、最初にルート ノード 3 の値を出力し、次にそのすべての子ノードの値 () を出力します。 1 と 5、次に左右の子ノードの子ノードというように続きます。 。 。 。 。 。

非常に簡単そうに見えますが、コードを書くときに問題が発生します。インオーダートラバーサルのように単純に再帰を使用して問題を解決することはできません (実際、改良された再帰アルゴリズムを使用できます)。再帰は葉ノードに直接到達することになるため、これは私たちが望む結果ではありません。しかし、それは問題ではありません。キューを使用して子ノードのキューをキューの最後に追加し、キューの先頭 (ルート ノード) からたどって、その子ノードをキューに追加して、行末にある場合は、nullptr を使用してそれをマークします。

最初に具体的なコードを見てみましょう:

std::vector<std::shared_ptr<BinaryTreeNode>>
BinaryTreeNode::layer_contents()
{
    std::vector<std::shared_ptr<BinaryTreeNode>> nodes;
    // 先添加根节点，根节点自己就会占用一行输出，所以添加了作为行分隔符的nullptr
    // 因为需要保存this，所以这是我们需要继承enable_shared_from_this是理由
    // 同样是因为这里，当返回的结果容器析构时this的智能指针也会析构
    // 如果我们使用了局部变量则this的引用计数从1减至0，导致对象被销毁，而使用了make_shared创建的对象引用计数是从2到1，没有问题
    nodes.push_back(shared_from_this());
    nodes.push_back(nullptr);
    // 我们使用index而不是迭代器，是因为添加元素时很可能发生迭代器失效，处理这一问题将会耗费大量精力，而index则无此烦恼
    for (int index = 0; index < nodes.size(); ++index) {
        if (!nodes[index]) {
            // 子节点打印完成或已经遍历到队列末尾
            if (index == nodes.size()-1) {
                break;
            }

            nodes.push_back(nullptr); // 添加分隔符
            continue;
        }

        if (nodes[index]->left) { // 将当前节点的子节点都添加进队列
            nodes.push_back(nodes[index]->left);
        }
        if (nodes[index]->right) {
            nodes.push_back(nodes[index]->right);
        }
    }

    return nodes;
}

コード自体は複雑ではありません。重要なのはその背後にあるアイデアです。

アルゴリズムの図

初めてこのコードを理解できなくても問題ありません。以下に図を示します。

最初の状態は次のとおりです。ループの開始、最初の行の内容が決定されました (^ は null ポインターを表します):

#次に、最初の要素からトラバースを開始します。トラバースされる 1 つはルートで、これには 2 つの子があり、値はそれぞれ 1 と 5 です:

次に、インデックス値 1、今回は nullptr にトラバースします。はキューの最後にないので、単純に nullptr をキューの最後に追加して、2 行目のノードがすべてキュー内に収まるようにします。 ## 次に、2 行目のノードのトラバースを開始し、その子ノードを 3 行目のノードとして使用します。行の内容がキューに入れられ、最後に行区切り文字が追加されます。

つまり、前の行のすべてのノードがキューを通じてキャッシュされ、次に次の行のすべてのノードが前の行のキャッシュとサイクルに基づいて取得されます。バイナリ ツリーの最後のレベルまで続きます。もちろん、バイナリ ツリーだけでなく、他のマルチツリーのレベル順序トラバースも同様のアイデアを使用して実装できます。

さて、各行の内容を取得する方法がわかったので、行ごとにノードを処理できます。

void BinaryTreeNode::layer_print()
{
    auto nodes = layer_contents();
    for (auto iter = nodes.begin(); iter != nodes.end(); ++iter) {
        // 空指针代表一行结束，这里我们遇到空指针就输出换行符
        if (*iter) {
            std::cout << (*iter)->value_ << " ";
        } else {
            std::cout << "\n";
        }
    }
}

如你所见，这个方法足够简单，我们把节点信息保存在额外的容器中是为了方便做进一步的处理，如果只是打印的话大可不必这么麻烦，不过简单通常是有代价的。对于我们的实现来说，分隔符的存在简化了我们对层级之间的区分，然而这样会导致浪费至少log2(n)+1个vector的存储空间，某些情况下可能引起性能问题，而且通过合理得使用计数变量可以避免这些额外的空间浪费。当然具体的实现读者可以自己挑战一下，原理和我们上面介绍的是类似的因此就不在赘述了，也可以参考园内其他的博客文章。

测试

最后让我们看看完整的测试程序，记住要用make_shared创建root实例：

int main()
{
    auto root = std::make_shared<BinaryTreeNode>(3);
    root->insert(1);
    root->insert(0);
    root->insert(2);
    root->insert(5);
    root->insert(4);
    root->insert(6);
    root->insert(7);
    root->ldr();
    std::cout << "\n";
    root->layer_print();
}

输出：

可以看到上半部分是中序遍历的结果，下半部分是层序遍历的输出，而且是逐行打印的，不过我们没有做缩进。所以不太美观。

另外你可能已经发现了，我们没有写任何有关资源释放的代码，没错，这就是智能指针的威力，只要注意资源的创建，剩下的事都可以放心得交给智能指针处理，我们可以把更多的精力集中在算法和功能的实现上。

如有错误和疑问欢迎指出！

以上がC++ グラフィック レイヤー順序のトラバーサルと、スマート ポインターによって構築されたバイナリ ツリーのレイヤーごとの印刷の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。