一、树结构概述
1.树是一种数据结构，并且是一种非线性结构，该结构中的一个数据元素可以有两个或者两个以上的直接后继元素，树可以用来描述客观中广泛存在的层次结构和关系。
二、树和二叉树的定义
1.树的定义，树是n(n>=0)个结点的有限集合，当n为0时的树被称为空树。在任意非空（n>0）的树中，有并且只有一个称为跟结点，其余结点可分为互不相交的有限子集，这每个子结点又被称为一棵树，都是具有根结点的子树。
树的定义一般都是递归的，类似于我们生活中的树形结构，它同时表示了树本身固有的机构特性。
树形层级结构
2.树的基本概念
a:双亲、孩子和兄弟，结点的子树的根称为该结点的孩子，相应的，该结点称为其子结点的双亲，具有相同双亲的结点互为兄弟，如上图所示，平级和子级。
b:结点的度。一个结点的子树个数为该结点的度，顾名思义就是每个父节点的子结点的个数为此结点的度。
c:叶子结点。叶子结点也被称为终端结点，指度为0的结点。
d:内部结点。即度不为0的结点，也称为分支结点或者非终端结点。除根结点意外，分支结点也称为内存结点。
e:结点的层次，根一般都称为第一层，根的孩子为第二层，依次律推。
f:树的高度。即一颗树的最大层次记为树的高度。
g:有序或无序树，若树中的结点的各个子结点的各子树从左到右具有次序，即不能交换，则称该树为有序树，否则为无序树。
树层次
三、二叉树
1.二叉树的定义。二叉树是（n>=0）个结点的有限集合，它或者是空树，或者时由一个根结点及两颗不相交的且分别称为左、右子树的二叉树所组成。因此二叉树具有同样的递归性质。
2.二叉树的性质和存储结构
（1）二叉树第ｎ层（ｎ>=1）上最多有2的ｎ－１次方个结点。
（２）高度为ｋ的二叉树最多有２的ｋ次方减１个结点。
（３）对于任何一颗二叉树，若其终端结点树为ｎ０，度为２则ｎ０＝ｎ２＋１．
（４）具有ｎ个结点的完全二叉树的深度为［㏒２Ｎ］＋１。
二叉树类型
3.二叉树的存储结构
（1）顺序存储树是用一组地址连续的存储单元存储二叉树中的结点，必须把结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。总之完全二叉树采用顺序存储结构既简单有节省空间，对于一般的二叉树，则不采用顺序存储结构。
顺序存储图
（2）链式存储结构。由于二叉树的结点包含有数据元素，左子树的根、右子树的根及双亲信息，因此可以用三叉链表（即一个结点含有3个指针或两个指针）来存储二叉树，链表的头指向二叉树的根结点。
链式存储图
四、二叉树的遍历
1.二叉树的遍历是按照某种策略访问树中的每个结点，且仅访问一次的过程，二叉树一般有先序、中序、后序三种遍历方式
遍历图
2.线索二叉树。二叉树的遍历实质是对一个非线性结构进行线性化过程，它使得每个结点（除第一个和最后一个）在这个线性序列中有且仅有一个会直接前驱和直接后继，但在二叉树链表中的存储结构中，只能找到一个结点的左、右孩子，不能直接得到结点在任意遍历序列中的前驱和后继。此过程一般为线索二叉树
3.最优二叉树。最优二叉树又被称为哈夫曼树，它是一类带全路径长度最短的树。
结尾：到此树就介绍到这里，后序我会出专栏哦，有想了解的可以点关注。
