📄 chapter6_1.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>算法表达中的抽象机制</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
var previous = "chapter6_1.htm";
var next = "end";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>果园或森林的二叉树表示</h2>
<p>从<a href="../tree/chapter6_3.htm">树的左儿子右兄弟表示法</a>和<a href="chapter5_3.htm">二叉树的链式表示法</a>可知，一般树和二叉树都可以用二叉链表作为其存储结构。因此，以二叉链表为媒介可以将一棵一般树转换为一棵二叉树。例如，图11(a)中的树可转化为图11(b)中的二叉树，它们具有相同的二叉链表表示。</p>
<p align="center"><img border="0" src="images/img12.gif" width="274" height="232"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/img25.gif" width="192" height="399"></p>
<p align="center">(b)</p>
<p align="center">图11 将一棵树转化为二叉树</p>
<p>由<a href="../tree/chapter6_3.htm">树的左儿子右兄弟表示法</a>可知，与其对应的二叉树根结点的右子树必为空树。因此，如果我们将一个果园中的所有树转换为二叉树，并将第i+1棵树当作第i棵树的根结点的右子树，i=1,2,..，则可将一个果园转换为一棵二叉树。如图12(a)中的果园，经上述转换，变成为图12(c)中的二叉树。</p>
<p align="center"><a href="images/img20.gif" target="_blank"><img border="0" src="images/img20.gif" width="485" height="197"></a></p>
<p align="center">(点击可以放大图形)</p>
<p align="center">图12 果园的二叉树的表示</p>
<p>对于一个森林，可先确定森林中各树的一个排列顺序，将其变成一个果园，然后再用相应的二叉树来表示。</p>
<p>用树的前序和中序遍历可定义果园的前序和中序遍历如下：</p>
<ol>
<li>
<p style="margin-top: 5; margin-bottom: 5">若果园非空，则对果园的前序遍历是依序对果园中第i棵树，i=1,2,..，进行前序遍历的结果。
</li>
<li>
<p style="margin-top: 5; margin-bottom: 5">若果园非空，则对果园的中序遍历是依序对果园中第i棵树，i=1,2,..，进行中序遍历的结果。
</li>
</ol>
<p>在前序和中序遍历的意义下，果园和与之相应的二叉树是等价的。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -