定义
专业定义
1.有一个称为根的结点
2.有若干个互不相交的子树，这些子树本身也是一个树
通俗定义
1.树是由结点和边组成的
2.每个节点只有一个父节点但可以有多个子节点
3.当有一个子节点例外，该节点没有父节点，此节点称为根节点
专业术语
度：节点拥有的子树
叶子：度为0的节点
树的度：树内各节点的度的最大值
深度：从根结点到最底层节点的层数，根节点是第一层
树的分类
一般树：任意一个节点的子节点的个树都不受限制
二叉树：每个节点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒
森林：n个互不相交的树的集合
二叉树的分类
一般二叉树：
满二叉树：在不增加树的层数的前提下无法在多添加一个节点的二叉树
完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树
树的存储
二叉树的存储
连续存储：只能存完全二叉树，要想存一般的二叉树，需要用0将其转化为完全二叉树。
优点：利用二叉树的性质，查找某个节点的父节点和子节点（包括判断有没有父节点和子节点）速度很快
缺点：耗费内存空间过大
链式存储：每个节点分三部分：左孩子，数据，右孩子；
一般树的存储
双亲表示法：图1；求父节点方便
孩子表示法：图2；求子节点方便
双亲表示法：图3；求子节点和父节点都方便
二叉树表示法（孩子兄弟表示法）：图4；
把一个普通树转化成二叉树来存储
具体转化方法
设法保证任意一个节点
左指针域指向它的第一个孩子
右指针域指向它的兄弟
只要能满足此条件，就可以把一个普通树转化为二叉树
一个普通树转化为一个二叉树一定没有右子树
森林的存储
将森林转化成一个二叉树，再存储二叉树。
左指针指向第一个孩子
右指针指向他的兄弟结点
图片发自简书App
图片发自简书App
图片发自简书App
图片发自简书App
