森林.md

森林（Forest）

定义

森林是n >= 0个互不相交的树的集合。

删除一棵深度大于1的树的根节点，就得到一个森林。

森林转换为二叉树

如果T1,...,Tn是一个森林，则对应于该森林的二叉树标记为B(T1,...,Tn);

1. 若n = 0，为空
2. 根为森林中第一棵树T1的根；左子树是B(T11,T12,...,T1m),其中T11,T12,...,T1m是T1根的所有子树；右子树是B(T2,...,Tn)。

森林的遍历

与森林F相对应的二叉树T的前序、中序和后序遍历都自然地对应于森林F的遍历。

前序遍历

二叉树T的前序遍历等价于按前序顺序访问森林F中的的结点。定义如下：

1. 如果F为空，则返回
2. 访问F的第一棵树的根节点
3. 按前序顺序遍历第一棵树的全部子树
4. 按前序顺序遍历F的其余的树

中序遍历

二叉树T的中序遍历等价于按中序顺序访问森林F中的的结点。定义如下：

1. 如果F为空，则返回
2. 按中序顺序遍历第一棵树的全部子树
3. 访问第一棵树的根结点
4. 按中序顺序遍历其余的树

后序遍历

1. 如果F为空，则返回
2. 按后序顺序遍历F的第一棵树的全部子树
3. 按后序顺序遍历F的其余的树
4. 访问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;
    }

}