前言
如果你是一个开发人员,或多或少对树型结构都有一定的认识,我个人对树型数据结构是又爱又恨。二叉树作为树的一种,是一种重要的数据结构,也是面试官经常考的东西。这篇文章主要分享下关于二叉树相关的知识点,并用go语言实现一个二叉树和对二叉树进行遍历。
二叉树概念
二叉树是具有两个节点的树形结构,通常左边的子树被称为左子树,右边的子树称为右子树,图示如下:
在代码中我们可以用代码来定义一个二叉树结构:
二叉树的性质
若二叉树结点的层次从1开始,则在二叉树第i层最多有2i-1 (i > 0)个节点。
深度为k的二叉树至少有k个结点,最多有2i - 1个结点。
对任何一个二叉树,如果其叶结点有n0 个,度为2的非叶结点有n2 个,则有 n0 = n2 + 1
具有n个结点的完全二叉树的深度为⌈log2(𝑛+1)⌉
创建二叉树
树的遍历
树的遍历分为三种方式,分别为前序遍历,中序遍历,后序遍历。
前序遍历(V-L-R)
前序遍历访问顺序为先输 root 结点,然后再输出左子树,然后再输出右子树。
我们通过递归的方式进行遍历
中序遍历(L-V-R)
中序遍历访问顺序为先输出 root 的左子树,再输 root 结点,最后输出 root 的右子树。
后序遍历(L-R-V)
后序遍历访问顺序为先输出 root 的左子树,最后输出 root 的右子树,再输 root 结点。