5.4 树、森林
5.4.1 树的存储结构
1.双亲表示法
用数组表示结点和其父结点。
2.孩子表示法
顺序(父结点)+ 链式(孩子结点)
3.孩子兄弟表示法
链式(孩子 + 兄弟)
5.4.2 树、森林与二叉树的转换
树——>二叉树
左孩子右兄弟
森林——>二叉树
先分别变成二叉树,再连接起来
5.4.3 树和森林的遍历
树 | 森林 | 二叉树 |
---|---|---|
先根遍历 | 先序遍历 | 先序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |
用数组表示结点和其父结点。
顺序(父结点)+ 链式(孩子结点)
链式(孩子 + 兄弟)
左孩子右兄弟
先分别变成二叉树,再连接起来
树 | 森林 | 二叉树 |
---|---|---|
先根遍历 | 先序遍历 | 先序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |