c++ - C++ 中的二叉搜索树，叶子为空值，不使用引用参数

Question

我试图编写一个简单的函数来决定二叉树也是二叉搜索树作为学习 C++ 的一种方式。然而，我发现的第一个问题是在我的递归 Node struct 中定义结束叶子。

#include <iostream>
#include <map>
#include <string>

struct Node {
    int data;
    Node* left;
    Node* right;
};
Node CreateNode(const int data, const Node& left, const Node& right) {
    Node node;
    node.data = data;
    node.left -> left;
    node.right -> right;
    return node;
}

int main(int argc, const char * argv[]) {
    auto root = CreateNode(1, NULL, NULL);
    isBST(&root);

    return 0;
}

bool isBST(Node* root) {

}

一种解决方案是使用指针代替 CreateNode 的参数，但我不想这样做，因为 C++11 建议将指针参数替换为引用参数。

我的问题是如何在上面的代码中定义叶子，因为我不能像我的参数是指针那样将它们设为空指针。

更新: isBST 有一个参数作为指针，只是因为我想将它混合起来以了解差异。

Answer 1

在这种情况下，引用并不合适，因为它们暗示没有所有权转让，也没有可选供应。另一种方法是使用智能指针。

#include <memory>
#include <utility>

struct Node;

using UniqueNode = ::std::unique_ptr<Node>;

struct Node 
{
   int data;
   UniqueNode left;
   UniqueNode right;

   explicit Node(void): data{} {}

   explicit Node(int const init_data, UniqueNode init_left, UniqueNode init_right)
   :   data{init_data}
   ,   left{::std::move(init_left)}
   ,   right{::std::move(init_right)}
   {}
};

// no need to manually write create function...
// UniqueNode CreateNode(const int data, UniqueNode left, UniqueNode right) 

int main(int argc, const char * argv[]) {
   UniqueNode root{::std::make_unique<Node>(42, nullptr, nullptr)};
   isBST(*root);

  return 0;
}

// takes a reference because no ownership is transferred, probably should be a member funciton
bool isBST(Node & root) {

}