树是由N个结点（或元素）组成的有限集合。
树的逻辑表示方法有：树形表示法、文氏图表示法、凹入表示法、括号表示法
结点的度：结点子树的个数
数的度：所有结点的度中的最大值，通常把度为M的树称为M次树。
分支结点：度不为零的结点
叶子结点：度为零的结点
路径：一个结点到另外一个结点的可达序列
路径长度：路径上的结点数-1
结点层次：即结点深度，从根节点开始，根节点为第一层，以此类推，
树的高度：即树的深度，树中结点的最大层次
有序树：按照一定的次序从左到右排列的，且相对次序是不能随意变换的
无序树：没有规律的
森林：N个互不相交树的集合，把含有多个子树的根节点删掉就变成了森林，反之个M（>1)棵独立的树加上一个根节点，森林就变成了一棵树。
树的性质：
| 树中的结点树等于所有结点的度数之和+1 |
| 度为M的树中第i层最多有Mi-—1个结点（i>=1） |
| 高度为h的m次树最多有mk-1/ m-1个结点 |
| 具有n个结点的m次树的最小高度为logm(n(m-1)+1),最大高度为n-m+1 |
树的遍历：①先根遍历：根左右②后根遍历：左右根③层次遍历从根结点开始，按从上到下，从左到右的次序
二叉树：有限的结点集合、这个集合或者为空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
度为2的树中至少有一个结点的度为2，二二叉树没有这种要求
度为2的树不区分左、右子树，二叉树严格区分
满二叉树：①所有分支结点都有左右孩子结点②所有叶子结点都集中在二叉树的最下一层。一棵高度为h的树有2h-1个结点
非空满二叉树特点：①叶子结点都在最下一层②只有度为0和度为2的结点
完全二叉树：①最多只有最下面两层的结点度数可以小于2，②最下面一层的叶子结点都依次排列在最左边的位置上
非空完全二叉树特点：①叶子结点只可能在最下面两层出现②对于最大层次中的叶子结点，都依次排列在该层最左边的位置上③
原创文章，作者：bd101bd101，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/244676.html