golang中单向、双向链表以及二叉树的实现

单向链表

package main

import "fmt"

type SinglyNode struct {
    Value int
    Next  *SinglyNode
}

type SinglyLinkedList struct {
    Head *SinglyNode
}

// 插入到尾部
func (l *SinglyLinkedList) Append(value int) {
    newNode := &SinglyNode{Value: value}
    if l.Head == nil {
        l.Head = newNode
        return
    }
    curr := l.Head
    for curr.Next != nil {
        curr = curr.Next
    }
    curr.Next = newNode
}

// 打印链表
func (l *SinglyLinkedList) Print() {
    for curr := l.Head; curr != nil; curr = curr.Next {
        fmt.Print(curr.Value, " -> ")
    }
    fmt.Println("nil")
}

双向链表

type DoublyNode struct {
    Value int
    Prev  *DoublyNode
    Next  *DoublyNode
}

type DoublyLinkedList struct {
    Head *DoublyNode
    Tail *DoublyNode
}

// 插入到尾部
func (l *DoublyLinkedList) Append(value int) {
    newNode := &DoublyNode{Value: value}
    if l.Tail == nil {
        l.Head = newNode
        l.Tail = newNode
        return
    }
    l.Tail.Next = newNode
    newNode.Prev = l.Tail
    l.Tail = newNode
}

// 从前往后打印
func (l *DoublyLinkedList) PrintForward() {
    for curr := l.Head; curr != nil; curr = curr.Next {
        fmt.Print(curr.Value, " <-> ")
    }
    fmt.Println("nil")
}

// 从后往前打印
func (l *DoublyLinkedList) PrintBackward() {
    for curr := l.Tail; curr != nil; curr = curr.Prev {
        fmt.Print(curr.Value, " <-> ")
    }
    fmt.Println("nil")
}

二叉树

type TreeNode struct {
    Value int
    Left  *TreeNode
    Right *TreeNode
}

// 插入节点（二叉搜索树）
func Insert(root *TreeNode, value int) *TreeNode {
    if root == nil {
        return &TreeNode{Value: value}
    }
    if value < root.Value {
        root.Left = Insert(root.Left, value)
    } else {
        root.Right = Insert(root.Right, value)
    }
    return root
}

// 中序遍历
func InOrder(node *TreeNode) {
    if node != nil {
        InOrder(node.Left)
        fmt.Print(node.Value, " ")
        InOrder(node.Right)
    }
}

func main() {
    // 测试单向链表
    fmt.Println("单向链表:")
    slist := &SinglyLinkedList{}
    slist.Append(1)
    slist.Append(2)
    slist.Append(3)
    slist.Print()

    // 测试双向链表
    fmt.Println("\n双向链表:")
    dlist := &DoublyLinkedList{}
    dlist.Append(10)
    dlist.Append(20)
    dlist.Append(30)
    fmt.Print("正向: ")
    dlist.PrintForward()
    fmt.Print("反向: ")
    dlist.PrintBackward()

    // 测试二叉树
    fmt.Println("\n二叉树:")
    var root *TreeNode
    for _, val := range []int{5, 3, 7, 2, 4, 6, 8} {
        root = Insert(root, val)
    }
    fmt.Print("中序遍历: ")
    InOrder(root)
    fmt.Println()
}