<H2>果园或森林的二叉树表示</H2>< >从<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_3.htm" target="_blank" >树的左儿子右兄弟表示法</A>和<a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/chapter5_3.htm" target="_blank" >二叉树的链式表示法</A>可知，一般树和二叉树都可以用二叉链表作为其存储结构。因此，以二叉链表为媒介可以将一棵一般树转换为一棵二叉树。例如，图11(a)中的树可转化为图11(b)中的二叉树，它们具有相同的二叉链表表示。</P>< align=center><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img12.gif"></P>< align=center>(a)</P><P align=center><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img25.gif"></P><P align=center>(b)</P><P align=center>图11 将一棵树转化为二叉树</P><P>由<a href="http://algorithm.myrice.com/datastructure/basic/tree/chapter6_3.htm" target="_blank" >树的左儿子右兄弟表示法</A>可知，与其对应的二叉树根结点的右子树必为空树。因此，如果我们将一个果园中的所有树转换为二叉树，并将第i+1棵树当作第i棵树的根结点的右子树，i=1,2,..，则可将一个果园转换为一棵二叉树。如图12(a)中的果园，经上述转换，变成为图12(c)中的二叉树。</P><P align=center><a href="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img20.gif" target="_blank" ><img src="http://algorithm.myrice.com/datastructure/basic/binary_tree/images/img20.gif"></A></P><P align=center>(点击可以放大图形)</P><P align=center>图12 果园的二叉树的表示</P><P>对于一个森林，可先确定森林中各树的一个排列顺序，将其变成一个果园，然后再用相应的二叉树来表示。</P><P>用树的前序和中序遍历可定义果园的前序和中序遍历如下：</P><OL><LI><P 5px; MARGIN-BOTTOM: 5px">若果园非空，则对果园的前序遍历是依序对果园中第i棵树，i=1,2,..，进行前序遍历的结果。 </P><LI><P 5px; MARGIN-BOTTOM: 5px">若果园非空，则对果园的中序遍历是依序对果园中第i棵树，i=1,2,..，进行中序遍历的结果。 </P></LI></OL><P>在前序和中序遍历的意义下，果园和与之相应的二叉树是等价的</P> |
楼主
发表于 2004-9-20 18:21:22