树的存储结构
常见的三种
双亲表示法
双亲表示法的结点
| data | parent |
|---|
双亲表示法图例
双亲定义序号用层序遍历顺序一次表示。
孩子表示法
孩子表示法两种结点
| data | children1 | children2 | children3 | children4 | children5 |
|---|
| data | degree | children1 | children2 | children3 | children4 | children5 |
|---|
孩子表示法图例
孩子兄弟表示法
孩子兄弟表示法的结点
| firstchidren | data | nextsibling |
|---|
image.png
上图可知中间为孩子结点，右边的为兄弟结点指针，沿着firstchildren域或者nextsibling域连续走，可实现查找操作。
树和二叉树的转换
树转换为二叉树
树转换为二叉树
- 将兄弟相连
- 删除除左边子树和兄弟的连线的连线。
- 展开所得二叉树。
二叉树转换为树
二叉树转换为树
- 找见所有右子树向双亲遍历，直至找见双亲路径改变，连接该结点。
- 删除除左子树的连接线和 1中所得连接线。
- 展开所得的树。
