树是一种抽象的数据结构，乍一听，就给人一种晦涩难懂的感觉，也确实如此，因为它的表现形式不像线性表那样那么直观。但是树结构太重要了，生活中常见的：文件的目录，族谱都是基于树结构；编程中常见的，数据库的索引，数据的快速定位等也是基于树结构，而且也有超级多的有关树结构的面试题。下面进入主题
来源于现实的树结构01树的概念
前几篇分享的都是线性表数据结构，特点就是所有的项都有一个前驱，并且除了最后一项，每个数据也都拥有一个后继项。而在树结构中，前驱和后继项的概念也存在，只不过改个名，叫做父节点和子节点。
我们可以想象一下现实中的大树，每棵树都有树干，树枝，树叶等结构，新的树枝，树叶永远都是从已经存在的树枝，树叶中生长而来。我们可以想象，从树根到每一片树叶都有固定且唯一的一条路径，而路径上可能会呈现出不同的数据特点，路径还包含着层级的关系，我们根据这种特点，将路径上的数据抽象成自己所要的特点，树的结构就诞生了
说到这，对于刚接触的朋友们来说，肯定还是蒙的，所以我们先介绍下术语。
02树的相关术语
边/分支
树是由节点（Node）和边（Edge）组成的，将一个父节点连接到其子节点的线，从（树的结构）上往下看，针对这条边，上面的节点是这个边的出边，下面的节点是这个边的入边父节点
一个节点是其所有出边所连接节点的父节点，一个节点只能有一个父节点子节点
入边均来自于同一个节点的若干节点，称之为这个节点的子节点兄弟节点
具有同一个父节点的节点之间称之为兄弟节点叶节点
没有子节点的节点称之为叶节点深度/层级
一个节点的深度或者层级数等于将其连接到根节点的路径的长度，根节点深度为0高度
树中的最长的路径的长度（叶子节点的最大层级数）。最大层数即为树的高度，根节点的高度为0路径
由边依次连接在一起的节点可以看成是一个有序的列表后代
一个节点的子节点，以及其子节点的子节点，以此类推
03树结构特点
树是由节点（Node）和边（Edge）组成的树的节点包含一个数据元素以及若干指向其子树的分支。节点拥有的子树称为节点的度，度为0的节点称为叶节点，度不为0的节点称之为分支节点，也叫内部节点树的每条边都连接两个节点，表示节点有关联树是一种分层的数据结构，一般规律是，越接近顶部的层越普遍（包含的数据范围越大），反之则数据会越来越集中一棵树的不同节点的子节点之间不能相交叶子节点具有唯一性（叶子节点是指没有子分支的节点）从根节点开始，每一个节点下方连接着的分支都称之为该节点的孩线性结构和树结构最大的不同在于线性结构是一对一的，而树结构是一对多的关系
04生活中的案例
文件系统
linux系统/windows系统的目录都是以树状图的方式设计域名系统xml/html文档结构
树结构一般性特征说到这就差不多了，接下来介绍树结构中最重要的一种：二叉树。
05二叉树相关
概念
一棵树，如果每个节点最多有两个子树，就称之为二叉树。
二叉树是n个节点的有限集合：该集合可以为空集（称为空二叉树），也可以由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树组成
特点
每个节点最多有两个子树，所以二叉树中不存在度大于2的节点。可以没有子树或者只有一课子树也是可以的左子树和右子树是有顺序的，次序不能颠倒即便树中只有一棵子树，也要区分它是左子树还是右子树树结构为什么这么复杂，因为树结构本就分了很多种，细分到二叉树时，又分了很多种，所以这里得介绍下不同的二叉树的类型。
06几种重要且特殊的二叉树
平衡二叉树
除了最后一个层级，其他的每一层都包含了完整的节点(每个节点都有两个子节点)满二叉树
所以分支节点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树满二叉树是同样深度的二叉树中节点最多的完全二叉树
最后一层上的所有节点(叶子节点)都是从左往右填充的完全二叉树按照线性表的方式进行存储，如果某个节点的下标为p，则其左子节点的下标为2p，右子节点为2p+1，其父节点下标为p//2，根节点的下标默认从1开始满二叉树和完全二叉树的区别
满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树，满二叉树是完全二叉树的一个特例完全二叉树的叶子节点只能出现在最下面两层最下面的叶子一定集中在左边连续位置倒数第二层，若有叶子节点，一定在右部连续位置二叉树的特点
在二叉树的第n层上最多有2^(n-1)节点（最多的情况其实就是满二叉树）。反过来说，对于包含N个节点的满二叉树，高度为h=log2(n+1)-1深度为n的二叉树最多有2^n-1个节点对任何一棵二叉树，如果其终端节点数为n0,度为2的节点数为n2,则n0=n2+1具有n个节点的完全二叉树的深度为logn+1一般来讲，二叉树越平衡，插入，访问以及删除的性能越高二叉树的这些特点都是后面理解二叉树应用的关键，接下来分享二叉树的实现(基于python)，基于列表和链表
07二叉树的实现
列表实现
还是那句话：二叉树是一种逻辑结构，物理结构怎样实现取决于操作者，先分享数组实现的二叉树，不推荐数组，比较麻烦，且占用内存大。
链表实现
链表的实现要优于数组实现，更推荐，我们来看下如何实现
08总结
本篇主要介绍了树结构的一般特性，二叉树的几种变体以及二叉树的基于python的实现。希望你对树结构能有一个初步的了解，当然，树结构还没有说完，比如树的几种遍历模式，树的一些经典应用等等，这些会放到下篇文章分享。
我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎