📄 chapter1.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 = "end";
var next = "chapter2.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>二叉树的定义</h2>
<p><font face="楷体_GB2312"> <b>二叉树</b></font>是一类非常重要的树形结构，它可以递归地定义如下：</p>
<p>二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n<sub>1</sub>和n<sub>2</sub>分别表示T，u(1)和u(2)的结点数，则有n=1+n<sub>1</sub>+n<sub>2</sub>
。u(1)和u(2)有时分别称为T的第一和第二子树。</p>
<p>因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。</p>
<p>二叉树有5种基本形态，如图1所示。</p>
<p align="center"><img border="0" src="images/img14.gif" width="483" height="122"></p>
<blockquote>
<p align="center">图1 二叉树的5种基本形态(其中□表示空)</p>
</blockquote>
<p>在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。</p>
<p> </p>
<p><b><a name="difference"></a>注意：</b>二叉树与<a href="../tree/chapter1.htm">树</a>和<a href="../tree/chapter2.htm">有序树</a>的区别</p>
<p>二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。在有序树中，虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。而在二叉树中，即使是一个儿子也有左右之分。例如图2中(a)和(b)是两棵不同的二叉树。虽然它们与图3中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。</p>
<blockquote>
<p align="center"><img border="0" src="images/img24.gif" width="399" height="254"></p>
<p align="center">图2 两棵不同的二叉树</p>
<p align="center"><img border="0" src="images/img15.gif" width="152" height="260"></p>
<p align="center">图3 一棵普通的树</p>
</blockquote>
<p>由此可见，尽管二叉树与<a href="../tree/chapter1.htm">树</a>有许多相似之处，但<b>二叉树不是<a href="../tree/chapter1.htm">树</a>的特殊情形</b>。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -