Golang结构体指针与递归的应用

Golang结构体指针与递归的应用

type Node struct{
content int
leftNode *Node
rightNode *Node
}

这不是错误，但如果我像下面这样修改代码：

type Node struct{
content int
leftNode Node
rightNode Node
}

就会出现错误！无效的递归！

2 回复

你是想问为什么吗？如果是的话，当编译器看到：

type Node struct {
    content int
    leftNode *Node
    rightNode *Node
}

它知道这个结构体的大小将是：

sizeof(int) + 2*sizeof(pointer)

在64位系统上，这就是24字节。

如果你写成：

type Node struct {
    content int
    leftNode Node
    rightNode Node
}

那么编译器计算 Node 类型的大小就会变成：

sizeof(int) + 2 * (
	sizeof(int) + 2 * (
		sizeof(int) + 2 * (
			sizeof(int) + 2 * (
				sizeof(int) + 2 * (
					sizeof(int) + 2 * (
						sizeof(int) + 2 * (...)))))))

无限循环下去。大小是无限的，这不可能存在，所以这是一个错误。

更多关于Golang结构体指针与递归的应用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


这是因为在Go语言中，结构体不能直接包含自身类型的非指针字段，这会导致无限递归的内存分配。当你使用Node类型而非*Node时，编译器无法确定结构体的大小，因为每个Node都包含另外两个Node，而这两个Node又各自包含两个Node，如此循环下去，无法计算内存布局。

正确示例（使用指针）：

type Node struct {
    content   int
    leftNode  *Node  // 使用指针，避免无限递归
    rightNode *Node  // 使用指针，避免无限递归
}

// 创建二叉树节点的示例
func main() {
    root := &Node{
        content: 1,
        leftNode: &Node{
            content: 2,
            leftNode:  nil,
            rightNode: nil,
        },
        rightNode: &Node{
            content: 3,
            leftNode:  nil,
            rightNode: nil,
        },
    }
    fmt.Printf("根节点值: %d\n", root.content)
}

递归遍历示例：

func (n *Node) InOrderTraversal() {
    if n == nil {
        return
    }
    n.leftNode.InOrderTraversal()
    fmt.Println(n.content)
    n.rightNode.InOrderTraversal()
}

// 使用示例
func main() {
    root := &Node{
        content: 1,
        leftNode: &Node{content: 2},
        rightNode: &Node{content: 3},
    }
    root.InOrderTraversal()  // 输出: 2 1 3
}

指针在递归数据结构中是必需的，因为它允许引用其他Node实例而不直接包含它们，这样结构体的大小就是固定的（一个int加两个指针的大小），编译器能够正确计算内存布局。

回到顶部