树与森林¶

树的存储结构¶

双亲表示法¶

孩子表示法¶

孩子兄弟表示法¶

树、森林与二叉树的转换¶

• 将树转换为二叉树:

  1. 在兄弟节点之间加一连线

  2. 对每个节点，只保留它与第一个子节点的连线，而抹去它与其他子节点的连线

  3. 以树根为轴心，顺时针旋转 \(45^\circ\)

  

  

  

  

• 由树转换成二叉树，其根结点的右子树总是空的

• 将森林转换成二叉树:

  与将树转换成二叉树的操作类似。

  1. 将森林中的每棵树转换成相应的二叉树

  2. 每棵树的根也可视为兄弟结点，在每棵树的根之间加一连线

  3. 以第一棵树根为轴心，顺时针旋转 \(45^\circ\)

  

  

  

  

• 由森林转换而成的二叉树，其左子树为其第一棵树的二叉树，其右子树为其剩余树构成的二叉树

• 判断一棵二叉树能够转换成一棵树还是森林: 该二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树

• 从二叉树还原为树或森林只需执行上述操作的逆操作

  

  

  

  

树与森林的遍历¶

树的遍历¶

1. 先根遍历: 若树非空，则先访问根结点，然后依次先根遍历各棵子树

2. 后根遍历: 若树非空，则先依次后根遍历各棵子树，然后访问根结点

与二叉树的先序遍历和中序遍历类似。

森林的遍历¶

1. 先序遍历: 若森林非空，则先访问森林中第一棵树的根结点，然后依次先序遍历各棵子树，再依次先序遍历森林中其余树构成的森林

2. 中序遍历: 若森林非空，则先访问森林中第一棵树的根结点，然后依次中序遍历各棵子树，再依次中序遍历森林中其余树构成的森林

与二叉树的先序遍历和中序遍历类似。