森林是n >= 0个互不相交的树的集合。
删除一棵深度大于1的树的根节点,就得到一个森林。
如果T1,...,Tn是一个森林,则对应于该森林的二叉树标记为B(T1,...,Tn);
- 若n = 0,为空
- 根为森林中第一棵树T1的根;左子树是B(T11,T12,...,T1m),其中T11,T12,...,T1m是T1根的所有子树;右子树是B(T2,...,Tn)。
与森林F相对应的二叉树T的前序、中序和后序遍历都自然地对应于森林F的遍历。
二叉树T的前序遍历等价于按前序顺序访问森林F中的的结点。定义如下:
- 如果F为空,则返回
- 访问F的第一棵树的根节点
- 按前序顺序遍历第一棵树的全部子树
- 按前序顺序遍历F的其余的树
二叉树T的中序遍历等价于按中序顺序访问森林F中的的结点。定义如下:
- 如果F为空,则返回
- 按中序顺序遍历第一棵树的全部子树
- 访问第一棵树的根结点
- 按中序顺序遍历其余的树
- 如果F为空,则返回
- 按后序顺序遍历F的第一棵树的全部子树
- 按后序顺序遍历F的其余的树
- 访问F的第一棵树的根节点
public class Forest<T> {
/**
* 树的结点,并不是二叉树结点
*
* @param <T>
*/
public class TreeNode<T> {
public T value;
public TreeNode<T> parent; //父结点
public List<TreeNode<T>> childs = new LinkedList<>(); //子结点,数量不确定
}
public Forest(List<TreeNode<T>> trees) {
if (trees != null)
this.trees = trees;
}
private List<TreeNode<T>> trees = new LinkedList<>(); //树的集合
public boolean isEmpty() {
return trees.isEmpty();
}
public boolean add(TreeNode<T> tree) {
return trees.add(tree);
}
public void add(int position, TreeNode<T> tree) {
trees.add(position, tree);
}
public TreeNode<T> remove(int position) {
return trees.remove(position);
}
public boolean remove(TreeNode<T> tree) {
return trees.remove(tree);
}
public void clear() {
trees.clear();
}
public int size() {
return trees.size();
}
/**
* 森林转换为二叉树
*
* @return
*/
public BinTree<T> toBinTree() {
if (size() == 0) return null;
BinTree<T> binTree = new BinTree<>();
Node<T> root = new Node<>(trees.get(0).value); //根为森林中第一棵树的根
root.setLeftChild(new Forest<T>(trees.get(0).childs).toBinTree().getRoot());
trees.remove(0);
root.setRightChild(toBinTree().getRoot());
binTree.setRoot(root); //根为第一棵树的根
return binTree;
}
}