Wghdr's Blog!

go

golang二叉树

wghdr

介绍

二叉树（Binary Tree）是一种常见的树状数据结构，其中每个节点最多有两个子节点：一个左子节点和一个右子节点。二叉树常用于实现搜索算法、排序算法以及其他需要组织数据的应用中。

概念

  • 节点（Node）：二叉树中的每个元素称为节点。每个节点包含一个值和指向左右子节点的指针。
  • 根节点（Root Node）：根节点是二叉树的顶部节点，它是整个树的起点。在一个二叉树中，只有一个根节点。
  • 父节点、子节点：在二叉树中，一个节点可以有零个、一个或两个子节点。节点的直接连接到其子节点的边称为父子关系。节点A是节点B的父节点，节点B是节点A的子节点。
  • 叶子节点（Leaf Node）：叶子节点是没有子节点的节点，也称为终端节点。在二叉树中，叶子节点位于树的末端。它的度为零
  • 子树：在二叉树中，以某个节点为根节点的子树包含该节点及其所有后代节点。一个节点拥有的子树的个数被称为节点的度。
  • 深度（Depth）：节点的深度是指从根节点到该节点的路径长度。根节点的深度为0，其子节点的深度为1，以此类推。
  • 高度（Height）：节点的高度是指从该节点到其最远叶子节点的路径长度。叶子节点的高度为0，没有子节点的节点的高度为0，以此类推。

特性

  • 结点的层次从根开始定义。根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度。
  • 如果树中结点的各子树看成从左到右是有次序的，则称为该树为有序树，否则称为无序树。
  • 二叉树的特点是每个结点最多有两棵子树。并且，二叉树的子树有左右之分，次序不能任意颠倒。
  • 二叉搜索树的特点就是，左子树的结点的值都比父结点小，右子树的结点的值，都比父结点的值大。

分类

二叉树的分类：二叉树可以分为满二叉树、完全二叉树和平衡二叉树等不同类型。

  • 满二叉：是一棵每个节点都有两个子节点的二叉树。
  • 完全二叉树：是一棵除了最后一层外，其它层都是满的二叉树。
  • 平衡二叉树：是一棵左右子树的高度差不超过1的二叉树。

操作方法

在二叉树的应用中，常见的操作包括插入节点、删除节点、搜索节点、遍历等。常用的遍历方式有三种：

  • 前序遍历（Preorder Traversal）：首先访问根节点，然后递归遍历左子树和右子树。
  • 中序遍历（Inorder Traversal）：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
  • 后序遍历（Postorder Traversal）：先递归遍历左子树和右子树，最后访问根节点。

示例代码

下面的代码分别实现了插入节点，指定位置插入节点，前序遍历，中序遍历，后序遍历，搜索节点，删除节点，查找最大值，最小值，打印二叉树。

package main

import (
    "fmt"
)

// Node 二叉树的节点
type Node struct {
    // 节点值
    value int
    // 左子树
    left *Node
    // 右子树
    right *Node
}

// BinaryTree 二叉树
type BinaryTree struct {
    // 根节点
    root *Node
}

// NewBinaryTree 创建空的二叉树
func NewBinaryTree() *BinaryTree {
    // 返回一个指向新创建的 BinaryTree 结构体的指针
    return &BinaryTree{}
}

// Insert 向二叉树中插入节点
func (bt *BinaryTree) Insert(value int) {
    // 如果二叉树为空，则将新节点作为根节点插入
    if bt.root == nil {
        bt.root = &Node{value: value, left: nil, right: nil}
    } else {
        insertNode(bt.root, value)
    }
}

// insertNode 根据节点值的大小关系，递归地在左子树或右子树中插入新节点
func insertNode(node *Node, value int) {
    if value < node.value {
        if node.left == nil {
            node.left = &Node{value: value, left: nil, right: nil}
        } else {
            insertNode(node.left, value)
        }
    } else {
        if node.right == nil {
            node.right = &Node{value: value, left: nil, right: nil}
        } else {
            insertNode(node.right, value)
        }
    }
}

// InsertAt 根据指定的位置向二叉树中插入节点
func (bt *BinaryTree) InsertAt(index string, value int) {
    if bt.root == nil {
        bt.root = &Node{value: value, left: nil, right: nil}
    } else {
        insertNodeAt(bt.root, index, value)
    }
}

// insertNodeAt 根据传入的位置参数，在左子树或右子树中递归地找到合适的位置插入新节点
func insertNodeAt(node *Node, index string, value int) {
    // 如果索引为 "left"，则将新节点作为当前节点的左子节点插入
    if index == "left" {
        if node.left == nil {
            node.left = &Node{value: value, left: nil, right: nil}
        } else {
            // 如果不为空，则递归调用 insertNodeAt 方法，在当前节点的左子节点上继续插入
            insertNodeAt(node.left, index, value)
        }
        // 如果索引为 "right"，则将新节点作为当前节点的右子节点插入
    } else if index == "right" {
        if node.right == nil {
            node.right = &Node{value: value, left: nil, right: nil}
        } else {
            insertNodeAt(node.right, index, value)
        }
    } else {
        fmt.Println("Invalid index")
    }
}

// PreOrder 二叉树的前序遍历并打印节点值
func (bt *BinaryTree) PreOrder() {
    PreOrder(bt.root)
}
func PreOrder(node *Node) {
    if node != nil {
        // 根节点 -> 左子树 -> 右子树
        fmt.Printf("%d ", node.value)
        PreOrder(node.left)
        PreOrder(node.right)
    }
}

// InOrder 二叉树的中序遍历并打印节点值
func (bt *BinaryTree) InOrder() {
    InOrder(bt.root)
}

func InOrder(node *Node) {
    if node != nil {
        // 左子树 -> 根节点 -> 右子树
        InOrder(node.left)
        fmt.Printf("%d ", node.value)
        InOrder(node.right)
    }
}

// PostOrder 二叉树的后序遍历并通过自定义函数处理节点值
// f 是一个回调函数，它作为参数传递给 PostOrder 函数
func (bt *BinaryTree) PostOrder(f func(value int)) {
    PostOrder(bt.root, f)
}

func PostOrder(node *Node, f func(value int)) {
    if node != nil {
        // 左子树 -> 右子树 -> 根节点，在访问每个节点时调用自定义函数进行处理
        // 当遍历到一个节点时，回调函数 f 将被调用，并且当前节点的值将作为参数传递给该函数
        PostOrder(node.left, f)
        PostOrder(node.right, f)
        f(node.value)
        //fmt.Printf("%d ", node.value)
    }
}

func (bt *BinaryTree) PostOrder2() {
    PostOrder2(bt.root)
}

func PostOrder2(node *Node) {
    if node != nil {
        // 左子树 -> 右子树 -> 根节点
        PostOrder2(node.left)
        PostOrder2(node.right)
        fmt.Printf("%d ", node.value)
    }
}

// FindMin 二叉树的最小值
func (bt *BinaryTree) FindMin() int {
    if bt.root == nil {
        fmt.Println("Tree is empty")
        return -1
    } else {
        return findMin(bt.root)
    }
}

// 从根节点开始，沿着左子节点的路径一直向下，直到找到没有左子节点的节点，即为最小值节点
func findMin(node *Node) int {
    if node.left == nil {
        return node.value
    } else {
        return findMin(node.left)
    }
}

// FindMax 二叉树的最大值
func (bt *BinaryTree) FindMax() int {
    if bt.root == nil {
        fmt.Println("Tree is empty")
        return -1
    } else {
        return findMax(bt.root)
    }
}

// 从根节点开始，沿着右子节点的路径一直向下，直到找到没有右子节点的节点，即为最大值节点
func findMax(node *Node) int {
    if node.right == nil {
        return node.value
    } else {
        return findMax(node.right)
    }
}

// Search 查找指定的值
func (bt *BinaryTree) Search(value int) bool {
    return search(bt.root, value)
}

// 从根节点开始，根据节点值与目标值的大小关系，递归地向左子树或右子树搜索，直到找到匹配的节点
func search(node *Node, value int) bool {
    if node == nil {
        return false
    } else if value == node.value {
        return true
    } else if value < node.value {
        return search(node.left, value)
    } else {
        return search(node.right, value)
    }
}

// Delete 删除指定的值对应的节点
func (bt *BinaryTree) Delete(value int) {
    deleteNode(bt.root, value)
}

func deleteNode(node *Node, value int) *Node {
    if node == nil {
        return nil
    }
    if value < node.value {
        node.left = deleteNode(node.left, value)
    } else if value > node.value {
        node.right = deleteNode(node.right, value)
    } else {
        // 如果节点没有子节点或只有一个子节点，直接删除节点
        if node.left == nil {
            return node.right
        } else if node.right == nil {
            return node.left
        }
        // 如果节点有两个子节点，需要找到右子树中的最小值节点，将其替代要删除的节点，并递归地删除最小值节点
        minValue := findMin(node.right)
        node.value = minValue
        node.right = deleteNode(node.right, minValue)
    }
    return node
}

// PrintTree 打印二叉树
func (bt *BinaryTree) PrintTree() {
    printTree(bt.root, 0)
}

func printTree(node *Node, level int) {
    if node == nil {
        return
    }
    // 先打印右子树，然后打印当前节点，最后打印左子树
    printTree(node.right, level+1)
    // 为了保持对齐，根据节点所在的层级进行缩进
    fmt.Printf("%*s%d\n", level*4, "", node.value)
    printTree(node.left, level+1)
}

func main() {
    // 创建一个二叉树
    bt := NewBinaryTree()
    // 插入节点
    bt.Insert(6)
    bt.Insert(8)
    bt.Insert(3)
    bt.Insert(5)
    bt.Insert(4)
    bt.Insert(2)
    bt.Insert(7)
    // 指定位置插入节点
    bt.InsertAt("left", 1)
    bt.InsertAt("right", 9)
    bt.PrintTree()

    fmt.Println("前序遍历:")
    bt.PreOrder()
    fmt.Println()
    fmt.Println("----------")

    fmt.Println("中序遍历:")
    bt.InOrder()
    fmt.Println()
    fmt.Println("----------")

    fmt.Println("后序遍历:")
    bt.PostOrder(func(value int) {
        fmt.Printf("%d ", value)
    })
    fmt.Println()
    fmt.Println("----------")

    fmt.Println("后序遍历2:")
    bt.PostOrder2()
    fmt.Println()
    fmt.Println("----------")

    min := bt.FindMin()
    fmt.Println("最小值:", min)
    fmt.Println("----------")

    max := bt.FindMax()
    fmt.Println("最大值:", max)
    fmt.Println("----------")

    fmt.Println("查找5:", bt.Search(5))
    fmt.Println("查找10:", bt.Search(10))
    fmt.Println("----------")

    fmt.Println("删除3:")
    bt.Delete(3)
    fmt.Println("删除7:")
    bt.Delete(7)
    fmt.Println("----------")

    fmt.Println("删除后的前序遍历:")
    bt.PreOrder()
    fmt.Println()
    fmt.Println("----------")

    fmt.Println("打印二叉树:")
    bt.PrintTree()
}

        9
    8
        7
6
        5
            4
    3
        2
            1
前序遍历:
6 3 2 1 5 4 8 7 9 
----------
中序遍历:
1 2 3 4 5 6 7 8 9 
----------
后序遍历:
1 2 4 5 3 7 9 8 6 
----------
后序遍历2:
1 2 4 5 3 7 9 8 6 
----------
最小值: 1
----------
最大值: 9
----------
查找5: true
查找10: false
----------
删除3:
删除7:
----------
删除后的前序遍历:
6 4 2 1 5 8 9
----------
打印二叉树:
        9
    8
6
        5
    4
        2
            1
分类： go
0 0 投票数
文章评分
订阅评论
提醒
guest

0 评论
内联反馈
查看所有评论

相关文章

开始在上面输入您的搜索词，然后按回车进行搜索。按ESC取消。

返回顶部
0
希望看到您的想法，请您发表评论x