1,线性结构
线性表
栈
队列
串
2,非线性结构
数组
矩阵
树与二叉树
树结构是一种非常重要的非线性结构，该结构中的一个数据元素可以有两格或者两格以上的直接后继元素，树可以用来描述客观世界中广泛存在的层次结构关系
🍁 结点的度：当前结点的孩子结点的个数。比如结点2有两个孩子结点4和5，所以结点2的度为2；而结点4和5没有孩子节点，所以度为0；结点3只有一个孩子节点6，所以度为1。
🍁 树的度：树中所有结点的度最大的那个。比如上面这棵树中，结点的度最大为2，所以该树的度为2。
🍁叶子结点：度为0的结点。
🍁 内部节点：度不为0的结点，也称为分支结点或非终端结点。除根结点外，分支结点也称为内部结点。
🍁父结点、子结点、兄弟结点：1是2和3的父结点，4和5是2的子结点，4和5、2和3称为兄弟结点。
🍁层次：根结点为第一层，之后层数依次加1。
二叉树是n(n>=0)个结点的有限集合，它或者是空树（n=0）,或者是一个由根节点及两颗不想交且分别称为左，右子树的二叉树所组成。
树转二叉树（孩子结点-左子数结点。兄弟结点-右孩子结点。）
🍀（1）将树的初始根节点直接作为二叉树的根节点。
🍀（2）将树的根节点的第一个子节点作为二叉树根节点的左指针，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右指针。
🍀（3）树中的剩余节点按照上一步的方式（左孩子，右兄弟），依序添加到二叉树中。直到树中所有的节点都在二叉树中。
二叉树的性质与存储结构
二叉树的性质
💧二叉树的第i层（i>=1）上最多有2i-1个节点
💧高度（深度）为k的二叉树最多有2k-1个节点（k>=1）
💧对于任何一颗二叉树，若其终端结点树为n0,度为2的节点数为n2，则n0=n2+1
💧如果对一颗有n个结点的完全二叉树的结点按层序编号（从第1层到[log2n]+1,每层从左到右），则对任一结点i(1<=i<=n) 有
如果i=1,则结点i无父节点，是二叉树的根；如果i>1,则父节点是[i/2]
如果2i>n,则结点i为叶子结点，无左子节点，否则其左子结点是结点2i;
如果2i+1>n,则结点i无右子叶点，否则，其右子结点是结点2i+1;
满二叉树和非完全二叉树和完全二叉树
满二叉树：除叶子结点，所有的结点都有两个子节点。
完全二叉树：即除最后一层节点外，其他层节点都要有2个字节点，并且最后一层节点都要有左排。
二叉树的遍历
对于上面的二叉树，我们来求一下它的先序、中序、后序以及层次遍历：
(1)先序遍历：采用DLR（根左右），得到的结果是：1 24578 36。
(2)中序遍历：采用LDR（左根右），得到的结果是：42785 1 36。
(3)后序遍历：采用LRD（左右根），得到的结果是：48752 63 1。
线索二叉树
最优二叉树
图
图是由集合V和E构成的二元组，记作G=(V,E),其中，V是图中顶点的非空有限集合，E是图中边的有限集合。
