⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 chapter2.htm

📁 介绍各种数据结构的讲义
💻 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 = "chapter1.htm";
var next = "chapter3.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> 
<!-- #BeginEditable "MainContent" --> 
<h2>树的相关术语</h2>
<ol>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">一个结点的儿子结点的个数称为该结点的<font face="楷体_GB2312">度</font>。一棵<font face="楷体_GB2312">树的度</font>是指该树中结点的最大度数。 
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">树中度为零的结点称为<font face="楷体_GB2312">叶结点</font>或<font face="楷体_GB2312">终端结点</font>。 
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">树中度不为零的结点称为<font face="楷体_GB2312">分枝结点</font>或<font face="楷体_GB2312">非终端结点</font>。除根结点外的分枝结点统称为<font face="楷体_GB2312">内部结点</font>。</p>
    <p style="margin-top: 10; margin-bottom: 10">例如在图1中，结点A，B和E的度分别为3，2，0。其中A为根结点,B为内部结点，E为叶结点，树的度为3。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">如果存在树中的一个结点序列K<sub>1</sub>,K<sub>2</sub>,..,K<sub>j</sub>，使得结点K<sub>i</sub>是结点K<sub>i+1</sub>的父结点(1≤i≤j)，则称该结点序列是树中从结点K<sub>1</sub>到结点K<sub>j</sub>的一条<font face="楷体_GB2312">路径</font>或<font face="楷体_GB2312">道路</font>。我们称这条<font face="楷体_GB2312">路径的长度</font>为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。</p>
    <p style="margin-top: 10; margin-bottom: 10">例如，在图1中，结点A到结点I有一条路径ABFI，它的长度为3。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的<font face="楷体_GB2312">祖先</font>，也称结点M是结点K的<font face="楷体_GB2312">子孙</font>或<font face="楷体_GB2312">后裔</font>。</p>
    <p style="margin-top: 10; margin-bottom: 10">例如在图1中，结点F的祖先有A，B和F自己，而它的子孙包括它自己和I,J。注意，任一结点既是它自己的祖先也是它自己的子孙。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">我们将树中一个结点的非自身祖先和子孙分别称为该结点的<font face="楷体_GB2312">真祖先</font>和<font face="楷体_GB2312">真子孙</font>。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。<font face="楷体_GB2312">子树</font>是树中某一结点及其所有真子孙组成的一棵树。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">树中一个<font face="楷体_GB2312">结点的高度</font>是指从该结点到作为它的子孙的各叶结点的最长路径的长度。<font face="楷体_GB2312">树的高度</font>是指根结点的高度。</p>
    <p style="margin-top: 10; margin-bottom: 10">例如图1中的结点B，C和D的高度分别为2，0和1，而树的高度与结点A的高度相同为3。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的<font face="楷体_GB2312">深度</font>或<font face="楷体_GB2312">层数</font>。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。</p>
    <p style="margin-top: 10; margin-bottom: 10">例如，在图1中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，G，H的深度为2；结点I和J的深度为3。在树的第二层的结点有E，F，J和H，树的第0层只有一个根结点A。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为<font face="楷体_GB2312">祖先子孙关系</font>。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵<font face="楷体_GB2312">有序树</font>；否则称为<font face="楷体_GB2312">无序树</font>。设结点n的所有儿子按其从左到右的次序排列为n<sub>1</sub>,n<sub>2</sub>,..,n<sub>k</sub>，则我们称n<sub>1</sub>是n的<font face="楷体_GB2312">最左儿子</font>，或简称<font face="楷体_GB2312">左儿子</font>，并称n<sub>i</sub>是n<sub>i-1</sub>的<font face="楷体_GB2312">右邻兄弟</font>，或简称<font face="楷体_GB2312">右兄弟</font>(i=2,3,..k)。</p>
    <p style="margin-top: 10; margin-bottom: 10">图2中的两棵树作为无序树是相同的，但作为有序树是不同的，因为结点a的两个儿子在两棵树中的左右次序是不同的。后面，我们只关心有序树，因为无序树总可能转化为有序树加以研究。</p>
      <p style="margin-top: 10; margin-bottom: 10" align="center"><img border="0" src="images/img1.gif" width="342" height="123"></p>
    <p style="margin-top: 10; margin-bottom: 10" align="center">图2 两棵不同的有序树</p>
    <p style="margin-top: 10; margin-bottom: 10">我们还可以将兄弟结点之间的左右次序关系加以延拓：如果a与b是兄弟，并且a在b的左边，则认为a的任一子孙都在b的任一子孙的左边。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10"><font face="楷体_GB2312">森林</font>是m(m&gt;0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个<font face="楷体_GB2312">树表</font>。在这种情况下，称这些树组成的森林为<font face="楷体_GB2312">有序森林</font>或<font face="楷体_GB2312">果园</font>。
  </li>
  <li> 
    <p style="margin-top: 10; margin-bottom: 10">在讨论表的时候，我们对表的每一位置的元素赋予一个元素值。这里，我们也用树的结点来存储元素，即对于树中的每一个结点赋予一个<font face="楷体_GB2312">标号</font>，这个标号并不是该结点的名称，而是存储于该结点的一个值。结点的名称总是不变的，而它的标号是可以改变的。我们可以做这样的类比：</p>
    <p style="margin-top: 10; margin-bottom: 10">树：表 = 标号：元素 = 结点：位置
  </li>
</ol>
<!-- #EndEditable --> 
</div>
<script src='../../../lib/footer.js'>
</script> 
</body> 
<!-- #EndTemplate --></html>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -