前言

如果你是一个开发人员，或多或少对树型结构都有一定的认识，我个人对树型数据结构是又爱又恨。二叉树作为树的一种,是一种重要的数据结构,也是面试官经常考的东西。这篇文章主要分享下关于二叉树相关的知识点，并用go语言实现一个二叉树和对二叉树进行遍历。

二叉树概念

二叉树是具有两个节点的树形结构，通常左边的子树被称为左子树，右边的子树称为右子树，图示如下：

在代码中我们可以用代码来定义一个二叉树结构：

type treeNode struct {
    Val string      //节点值
    left *treeNode  //左节点
    right *treeNode //右节点
}
 

二叉树的性质

• 若二叉树结点的层次从1开始，则在二叉树第i层最多有2i-1 (i > 0)个节点。
• 深度为k的二叉树至少有k个结点，最多有2i - 1个结点。
• 对任何一个二叉树，如果其叶结点有n0 个，度为2的非叶结点有n2 个，则有 n0 = n2 + 1
• 具有n个结点的完全二叉树的深度为⌈log2(𝑛+1)⌉

创建二叉树

// 创建节点
func CreateBinaryTree(data string) *treeNode {
    return &treeNode{data, nil, nil}
}
 
// 插入节点
func (node *treeNode) Insert(n *treeNode, data string) bool {
    cur := n
    for cur != nil {
        if cur.Val < data {
            if cur.Right != nil {
                cur = cur.Right
            } else {
                cur.Right = CreateBinaryTree(data)
                return true
            }
        } else {
            if cur.Left != nil {
                cur = cur.Left
            } else {
                cur.Left = CreateBinaryTree(data) 
                return true
            }
        }
    }
    return false
}
 

树的遍历

树的遍历分为三种方式，分别为前序遍历，中序遍历，后序遍历。

前序遍历(V-L-R)

前序遍历访问顺序为先输 root 结点，然后再输出左子树，然后再输出右子树。

我们通过递归的方式进行遍历

func preOrder(root *bt) {
    if root != nil {
        fmt.Print(root.Val, " ")
        preOrder(root.Left)
        preOrder(root.Right)
    }
}
 

中序遍历(L-V-R)

中序遍历访问顺序为先输出 root 的左子树，再输 root 结点，最后输出 root 的右子树。

func inOrder(root *bt) {
    if root != nil {
        inOrder(root.Left)
        fmt.Print(root.Val, " ")
        inOrder(root.Right)
    }
}
 

后序遍历(L-R-V)

后序遍历访问顺序为先输出 root 的左子树，最后输出 root 的右子树，再输 root 结点。

func posOrder(root *bt) {
    if root != nil {
        posOrder(root.Left)
        posOrder(root.Right)
        fmt.Print(root.Val, " ")
    }
}