|
树或森林与二叉树之间有一个自然的一一对应关系任何一个森林或一棵树可惟一地对应到一棵二叉树反之任何一棵二叉树也能惟一地对应到一个森林或一棵树 ．树森林到二叉树的转换 （）将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟按照这种关系很自然地就能将树转换成相应的二叉树 ①在所有兄弟结点之间加一连线 ②对每个结点除了保留与其长子的连线外去掉该结点与其它孩子的连线 【例】下面(a)图所示的树可转换为(c)图所示的二叉树具体转换过程可【参见动画演示】 注意 由于树根没有兄弟故树转化为二叉树后二叉树的根结点的右子树必为空 （）将一个森林转换为二叉树 具体方法是 ① 将森林中的每棵树变为二叉树 ② 因为转换所得的二叉树的根结点的右子树均为空故可将各二叉树的根结点视为兄弟从左至右连在一起就形成了一棵二叉树 【例】下图中左边包含三棵树的森林可转换为右边的二叉树 具体转换过程可【参见动画演示】 二叉树到树森林的转换 把二叉树转换到树和森林自然的方式是若结点x是双亲y的左孩子则把x的右孩子右孩子的右孩子…都与y用连线连起来最后去掉所有双亲到右孩子的连线 【例】下图的森林就是由例中二叉树转换成的 具体转换过程可【参见动画演示】 |
