目录
1.1树的基本概念
树是由N(N>=0)个有限结点组成的具有层次关系的集合，是一种简单地非线性结构。当N-0时，称为空树
树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点
(1)树的根节点没有前驱节点，根除结点以外的所有结点有且只有一个前驱结点。
(2)树中可以由零个或多个后继结点
① 根节点：在树结构中，只有一个结点没有前件，称该结点为根节点（简称根）
② 父节点：在树结构中，每个结点只有一个前件，这个前件就是该节点的父节点。
③ 子节点：在数据结构中，每个结点可以由多个后件，这些后件就是该结点的子结点
④ 叶子结点：在树结构中，没有后件的结点称为叶子结点
⑤度：树中一个结点的子节点个数称为该节点的度，树中结点的最大度数称为树的度
⑥树的深度：在树结构中，根节点所在的层次为1，其他结点所在的层次为其父结点所在的层次加1，最大的层次称为树的深度。
⑦ 子树：在树结构中，以某一个结点的一个子节点为根节点构成的树，称为该结点的子树
1.2树的性质
(1)总分支数-1xN1+2xN2+....+m x Nm(度为m的结点引出的m条分支)
(2)总结点数==N0+N1+N2+....+Nm
(3)树中的结点数等于所有结点度树加1
(4)度为m的树中第i层上至多有m的i-1方个结点(i>=1)
2.1二叉树的基本概念
二叉树是另一种树形结构，其特点是每个结点至多只有两颗子树(即二叉树中不存在度大于2的结点).并且，二叉树的子树有左右之分，其次序不能颠倒。
二叉树是n(n>=0)个结点的有限集合：
①当n=0时，为空二叉树
② 当n>=1时，二叉树由一个根结点和两个互不相交的被称为左子树和右子树组成，左子树和右子树又分别是一颗二叉树
满二叉树：一个高度为h，含有2的h方-1个结点的二叉树称为满二叉树，即树中的每一层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，除叶子结点以外每个结点的度数都为2
完全二叉树：深度为k，有一个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树一一对应，称为完全二叉树
2.2二叉树性质
2.3二叉树的存储结构
二叉树的存储结构分为顺序存储和链式存储：
(1)顺序存储：二叉树的顺序存储就是用一组连续的存储单元存放二叉树的结点元素，一般按照二叉树结点自上向下，自左向右的顺序存储。
(2)链式存储：二叉树的链式存储结构是用一个链表来存储一颗二叉树，二叉树中每一个结点用链表的一个链结点来存储。
在二叉树中，结点结构通常包括若干数据域及若干个指针域，在二叉链表中至少包含三个域
由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二次链表
2.4二叉树的遍历
所谓二叉树的遍历，是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，并且仅被访问一次。常见的三种遍历算法分别是前序遍历，中序遍历和后序遍历。
(1)前序遍历(DLR)🎄:首先访问根节点，其次遍历左子树，最后遍历右子树。
(2)中序遍历(LDR)🎄:首先遍历左子树，其次访问根结点，最后遍历右子树。并且在遍历左右子树时，仍先遍历左子树，然后访问根结点，最后遍历右子树
(3)后序遍历(LRD:)🎄:首先遍历左子树，其次遍历右子树，最后访问根结点。并且在遍历左右子树时仍然先遍历左子树，然后遍历右子树，最后访问根结点。
