一、节点的度和树的度
- 节点的度：节点拥有的子树数目称为节点的度，叶子节点的度为0。
- 树的度：树内各节点的度的最大值。
二、树的深度和高度
- 节点n[i]的深度：从根节点到n[i]节点的唯一路径长，即节点n[i]所在的层次(根节点为0层)。
- 树的深度：树中节点最大的层次。
- 节点n[i]的高度：从n[i]到叶子节点的最长路径长，叶子节点的高度为0。
- 树的高度：为根的高度
三、树的遍历方式
说明：遍历方式都是相对于父节点而言的。
1.前序遍历
父节点 => 左孩子 => 右孩子
image.png
2.中序遍历
左孩子 => 父节点 =>右孩子
image.png
3.后序遍历
左孩子 => 右孩子 => 父节点
image.png
四、二叉树
每个节点最多只能有两个节点。
image.png
五、完全二叉树
设二叉树的深度为k，除第k层外，其他各层(0 ~ k-1)的节点数都达到最大个数，第k层所有节点都连续集中在最左边。
image.png
六、满二叉树
如果二叉树的层数为k，且节点总数为2^(k+1) - 1，则该二叉树就是满二叉树。
image.png
七、二叉查找树(Binary Search Tree，BST)
左子树上的值都小于父节点的值，右子树上的值都大于或等于父节点的值。（中序遍历有序）
image.png
八、平衡的二叉查找树(AVL树)
一棵AVL树是每个节点的左子树和右子树的高度最多差1的二叉查找树。
平衡因子 = |左子树高度 - 右子树高度|
image.png
九、总结
本章内容只是简单介绍了树的一些基本概念以及一些常见的树，关于AVL树，红黑树，B树，B+树等等会以独立的篇章详细说明。
