数据结构--树和森林
数据结构--树和森林
树和森林
森林是m棵互补相交的树的集合.
将树去掉根结点可以变成森林,将森林的每个树全部加上根结点可以变成一颗树.
1.双亲表示法
数据域:存放数据
双亲域:存放双亲结点在数组当中的位置.
特点:找双亲容易,找孩子难.
双亲表示法使用结构体数组存储
- 首先定义结构体结点
- 然后开辟一个结构体数组来存储数据
2.孩子链表存储
寻找孩子容易,找双亲难
- 将每个结点的孩子用链表存储起来
- 保存每个链表的头指针
- 将头指针的数组保存起来,用线性表存储
孩子结点的结构
带双亲的孩子链表
3.孩子兄弟表示法
使用二叉链表来存储树的结构.
一个指针指向下一个孩子
一个指针指向下一个兄弟
通过右指针去寻找兄弟,通过左指针去寻找孩子
二叉链表的具体实现过程
