树-基础
基本概念
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/tree.png
- 数据元素一对多的关系
- 根节点唯一
- 现实生活中一对多的关系很多
- 除了根节点，其他节点只有一个双亲节点
- 叶子节点无孩子，度为0
- 每个分支节点有一个双亲，多个孩子
- 子树是分支节点和他的孩子组成的树
- 森林是多个不相交的子树
- 节点的度：节点的孩子数量
- 树的度：节点度的最大值
- 深度：树的层数
- 兄弟：同一深度，同一双亲的节点
- 堂兄弟：同一深度，不同双亲的节点
树的存储结构
树不像二叉树，没有前、中、后序遍历
树也是用顺序和链式存储，但结构会比较灵活
双亲表示法
| data | parent |
|---|---|
一个元素包含两个域(data，parent)，数据域和指向双亲的指针（链式存储），然后把多个元素保存在一个数组（顺序存储）中。
孩子表示法
| data | child1 | child2 | ... | childn |
|---|---|---|---|---|
同上，每个节点都保存在数组中，而每个节点的多个指针又指向了保存在数组其他位置上的孩子节点
孩子兄弟表示法
| data | firstchild | rightsib |
|---|---|---|
逻辑和上面两种表示法相同
不同的表示法是为了解决不同的查询需求，例如查询是自下而上的，那就会用双亲表示法
总结
因为树的度无法预知，也无法控制，存储结构不容易实现，所以树不常用，从而引申出了有规律可循的‘二叉树’
