Go语言数据结构之二叉树必会知识点总结

目录

• 前言
• 二叉树概念
• 二叉树的性质
• 创建二叉树
• 树的遍历
• 前序遍历(V-L-R)
• 中序遍历(L-V-R)
• 后序遍历(L-R-V)

前言

如果你是一个开发人员，或多或少对树型结构都有一定的认识，我个人对树型数据结构是又爱又恨。二叉树作为树的一种,是一种重要的数据结构,也是面试官经常考的东西。这篇文章主要分享下关于二叉树相关的知识点，并用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(