C++ 스마트 포인터로 구성된 이진 트리의 그래픽 레이어 순서 탐색 및 레이어별 인쇄

이진 트리는 매우 일반적인 데이터 구조이며 해당 요소를 탐색하는 방법에 대한 수많은 기사가 있습니다. 하지만 대부분의 기사에서는 선주문/중간/후순 순회에 대해 설명합니다. 기존 기사의 설명도 상대적으로 모호하고 읽기 어렵습니다. 이 기사에서는 생생한 그림과 명확한 코드를 사용하여 레벨 순서 탐색 구현을 이해하는 데 도움을 주는 동시에 최신 C++에서 제공하는 스마트 포인터를 사용하여 트리 데이터 구조의 리소스 관리를 단순화합니다.

관련 튜토리얼: 데이터 구조 트리 튜토리얼

이제 본론으로 들어가겠습니다.

스마트 포인터를 사용하여 이진 트리 구축

여기서 구현하고 싶은 것은 단순히 이진 검색 트리를 시뮬레이션하고 다음 요구 사항을 충족하는 삽입 기능을 제공하는 이진 트리입니다. 이진 탐색 트리. 동시에 우리는 shared_ptr을 사용하여 리소스를 관리합니다.

이제 우리는 insert와 ldr의 두 가지 메소드만 구현합니다. 다른 메소드의 구현은 이 기사에서 다루는 내용이 아니지만, 나중에 기사에서 하나씩 소개합니다: insert和ldr两个方法，其余方法的实现并不是本文所关心的内容，不过我们会在后续的文章中逐个介绍：

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();
};

我们的node对象继承自enable_shared_from_this，通常这不是必须的，但是为了在层序遍历时方便操作，我们需要从this构造智能指针，因此这步是必须的。insert会将比root小的元素插入左子树，比root大的插入到右子树；ldr则是最为常规的中序遍历，这里实现它是为了以常规方式查看tree中的所有元素。

值得注意的是，对于node节点我们最好使用make_shared进行创建，而不是将其初始化为全局/局部对象，否则在层序遍历时会因为shared_ptr的析构进而导致对象被销毁，从而引发未定义行为。

现在假设我们有一组数据：[3, 1, 0, 2, 5, 4, 6, 7]，将第一个元素作为root，将所有数据插入我们的树中会得到如下的一棵二叉树：

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);

可以看到节点一共分成了四层，现在我们需要逐层打印，该怎么做呢？

层序遍历

其实思路很简单，我们采用广度优先的思路，先将节点的孩子都打印，然后再去打印子节点的孩子。

以上图为例，我们先打印根节点的值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;
}

우리의 노드 개체는 enable_shared_from_this에서 상속됩니다. 일반적으로 이는 필요하지 않지만 레이어 중 작업을 용이하게 하기 위해- 순회 순서를 지정하려면 이부터 시작하여 스마트 포인터를 구성해야 하므로 이 단계가 필요합니다. insert는 루트보다 작은 요소를 왼쪽 하위 트리에 삽입하고 루트보다 큰 요소를 오른쪽 하위 트리에 삽입합니다. ldr는 여기에서 구현되는 가장 일반적인 순회입니다. 일반적인 방법으로 트리의 모든 요소를 ​​보는 것입니다.

노드 노드의 경우 전역/로컬 개체로 초기화하는 대신 make_shared를 사용하여 생성하는 것이 가장 좋습니다. 그렇지 않으면 레이어로 인해 발생합니다. -순서 탐색. shared_ptr이 소멸되면 개체가 소멸되어 정의되지 않은 동작이 발생합니다.

이제 데이터 세트가 있다고 가정합니다: [3, 1, 0, 2, 5, 4, 6, 7], 첫 번째 요소를 루트로 사용하고 모든 데이터를 트리에 삽입 다음 이진 트리를 얻습니다:

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";
        }
    }
}

# 🎜🎜#

노드가 4개의 레이어로 나뉘어져 있는 것을 볼 수 있습니다. 이제 레이어별로 인쇄해야 합니다.

레벨 순서 탐색

사실 아이디어는 매우 간단합니다. 너비 우선 아이디어를 채택하여 먼저 모든 자식을 인쇄합니다. 노드를 선택한 다음 자식을 인쇄합니다. 노드의 자식입니다.

예를 들어 위 그림에서는 먼저 루트 노드 3의 값을 인쇄한 다음 모든 하위 노드의 값인 를 인쇄합니다. >1 및 5, 왼쪽 및 오른쪽 자식의 자식 등입니다. . . . . .

말하기는 쉽지만 코드를 작성할 때 문제가 발생합니다. 순차 순회와 같은 문제를 해결하기 위해 단순히 재귀를 사용할 수는 없습니다(실제로 개선된 재귀 알고리즘을 사용할 수 있음). 이는 우리가 원하는 결과가 아닌 리프 노드로 직접 이동하기 때문입니다. 하지만 문제가 되지 않습니다. 대기열을 사용하여 대기열 끝에 자식 노드 대기열을 추가한 다음 루트 노드인 대기열의 시작 부분에서 순회하고 해당 자식 노드를 대기열에 추가한 다음 두 번째 노드에서 동일한 작업을 수행합니다. 줄 끝에서 nullptr를 사용하여 표시합니다.

먼저 특정 코드를 살펴보겠습니다.

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();
}

코드 자체는 복잡하지 않습니다. 중요한 것은 코드 뒤에 숨은 아이디어입니다.

알고리즘 다이어그램

이 코드를 처음 이해하지 못해도 상관 없습니다. 아래 다이어그램을 제공합니다.

우선 루프 시작 부분의 상태, 첫 번째 줄의 내용이 결정되었습니다(^는 널 포인터를 나타냄).

Then 첫 번째 요소에서 순회를 시작합니다. 한 순회는 각각 값이 1과 5인 두 개의 자식이 있는 루트입니다.

#🎜🎜##🎜🎜#그런 다음 인덱스 값 +1, 이번에는 순회 도착은 nullptr입니다. 큐의 끝이 아니기 때문입니다. 따라서 큐의 끝에 nullptr을 추가하면 두 번째 행의 노드가 모두 큐에 있게 됩니다. #🎜🎜##🎜🎜##🎜🎜##🎜🎜# #🎜🎜#그런 다음 두 번째 행의 노드를 순회하기 시작하고 해당 하위 노드를 세 번째 행의 콘텐츠로 대기열에 넣은 다음 마지막으로 추가합니다. 행 구분 기호 등: #🎜🎜##🎜🎜## 🎜🎜##🎜🎜##🎜🎜#간단히 말하면 이전 행의 모든 ​​노드가 대기열을 통해 캐시된 다음 모든 노드가 캐시됩니다. 다음 행의 노드는 이전 행의 캐시를 기반으로 획득되며 이진 트리의 마지막 수준까지 순환이 계속됩니다. 물론 이진 트리뿐만 아니라 다른 다중 트리의 레벨 순서 순회도 유사한 아이디어를 사용하여 구현할 수 있습니다. #🎜🎜##🎜🎜#좋아, 이제 각 행의 콘텐츠를 가져오는 방법을 알았으므로 노드를 행별로 처리할 수 있습니다. #🎜🎜#

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!