Julia 中使用结构数据类型、指针和 this 的树和图问题

Question

我想用 Julia 语言编写解决一些图/树问题。这是一些很好的例子。在C中是这样完成的：
Recursive C program for level order traversal of Binary Tree

#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node *left, *right;
};

/* Function prototypes */
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
    int h = height(root);
    int i;
    for (i=1; i<=h; i++)
        printGivenLevel(root, i);
}

/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1)
    {
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

/* Compute the "height" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int height(struct node* node)
{
    if (node==NULL)
        return 0;
    else
    {
        /* compute the height of each subtree */
        int lheight = height(node->left);
        int rheight = height(node->right);

        /* use the larger one */
        if (lheight > rheight)
            return(lheight+1);
        else return(rheight+1);
    }
}

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                        malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

/* Driver program to test above functions*/
int main()
{
    struct node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);

    printf("Level Order traversal of binary tree is \n");
    printLevelOrder(root);

    return 0;
}

我尝试在 Julia 中以类似的方式执行此操作，但存在一些问题，特别是在访问结构元素时。（如节点->右和节点->左）。或者某种方式创建自引用结构和函数来分配节点。

struct node
  data::Int
  left::Ptr{node}
  right::Ptr{node}
end

# Compute the "height" of a tree -- the number of
#     nodes along the longest path from the root node
#     down to the farthest leaf node.
function height = (node::Ptr{node})
  if node === nothing
    return 0
  else
    # compute the height of each subtree 
    lheight = height(node->left)
    rheight = height(node->right)

    # use the larger one 
    if lheight > rheight
      return lheight+1
    else return rheight+1
    end

  end
end

从我所看到的尝试以 C 方式重新创建问题解决方案并不是正确的方法，但是这种结构类型应该很有用。我只需要知道如何创建自引用结构，如何分配此节点中的元素以及如何获取它们。

Answer 1

首先，我强烈建议阅读https://docs.julialang.org/en/v1/，因为 Julia 在很多方面与 C 不同。这里有很多事情需要指出：

• Julia 中的默认struct值是不可变的，这意味着在创建字段后您无法修改字段。它也总是通过复制而不是通过引用传递，因为它没有特定的内存地址并且通常在堆栈上分配。这实际上对编译器有多种好处，也是 Julia 如此快的部分原因。在您的示例中，您可能需要 a mutable struct，它struct与 C 中的a 更相似。
• 在 Julia 中，您永远不必Ptr直接使用指针 ()，除非您正在调用 C 代码。由于 Julia 使用垃圾收集器，因此在内存管理方面，原始指针有很多问题，通常应该避免。您通常只是直接使用对象，或者，如果您想通过引用传递不可变对象，您可以将它们包装在Ref.
• 在 Julia 中，字段总是仅使用点x.field（相当于getproperty(x, :field)）来访问，或者在某些情况下使用getfield(x, :field)。（后者不能被用户重载，这有时很有用）。->实际上创建了一个匿名函数。

对于您的示例，以下内容应该有效：

mutable struct Node
    data::Int
    left::Node
    right::Node
    Node(data::Int) = new(data)
end

function height(node::Node, field::Symbol)
    isdefined(node, field) || return 0
    return height(getproperty(node, field))
end

function height(node::Node)
    lheight = height(node, :left)
    rheight = height(node, :right)

    # use the larger one 
    if lheight > rheight
        return lheight+1
    else
        return rheight+1
    end
end

第一部分所做的是创建一个mutable struct Node，其中包含自引用字段，如您的 C 示例。该行Node(data::Int) = new(data)实际上是一个仅获取数据的内部构造函数，如果您new直接在可变结构中调用，则可以保留尾随字段未定义。您可以随后使用 定义这些字段x.field = y。如果这些字段本身是可变的，您还可以使用 来检查它们是否未定义isdefined(x, :field)。在这里，我向 中添加了另一个方法height，它也接受字段名称，如果已定义，则返回字段的高度，否则返回 0。

然后，您将构造节点并计算它们的高度，如下所示：

julia> n = Node(1)
Node(1, #undef, #undef)

julia> n.left=Node(2)
Node(2, #undef, #undef)

julia> n
Node(1, Node(2, #undef, #undef), #undef)

julia> height(n)
2

希望有帮助！如果您想了解更多信息，我上面链接的文档通常非常好。