什么是树结构?
存在层次关系的可以称为是树结构，树是一种重要的非线性数据结构。
现实中有很多事物都有层次关系，
- 社会组织结构
- 管理硬盘
- 家谱
- 图书信息管理
- 公司组织结构
- …….
为什么要有树结构
因为分层次组织管理具有更高效率。
树的概念
- 空树：不含有任何结点（元素）
- 非空树：至少含有一个结点（元素）
树的术语
- 结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有10个结点。
- 结点的度(Degree of Node)：结点所拥有的子树的个数，在图中，结点A的度为3。
- 树的度(Degree of Tree)：树中各结点度的最大值。在图中，树的度为3。
- 叶子结点(Leaf Node)：度为0的结点，也叫终端结点。在图中，结点E、F、G、H、I、J都是叶子结点。
- 分支结点(Branch Node)：度不为0的结点，也叫非终端结点或内部结点。在图中，结点A、B、C、D是分支结点。
- 孩子(Child)：结点子树的根。在图中，结点B、C、D是结点A的孩子。
- 双亲(Parent)：结点的上层结点叫该结点的双亲。在图中，结点B、C、D的双亲是结点A。
- 祖先(Ancestor)：从根到该结点所经分支上的所有结点。在图中，结点E的祖先是A和B。
- 子孙(Descendant)：以某结点为根的子树中的任一结点。在图中，除A之外的所有结点都是A的子孙。
- 兄弟(Brother)：同一双亲的孩子。在图中，结点B、C、D互为兄弟。
- 结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。
- 堂兄弟(Sibling)：同一层的双亲不同的结点。在图中，G和H互为堂兄弟。
- 树的深度(Depth of Tree)：树中结点的最大层次数。在图中，树的深度为3。
- 无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。
- 有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。
- 森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。
树的性质：
- 树中的结点数等于所有结点的度数加1
- 度为k的树中第i层上至多有Ki-1个结点(i>=1)
- 深度为h的k叉树至多有(kh-1)/(k-1)个结点
- 具有n个结点的k叉树的最小深度为[logk(n(k-1)+1)]