【www.myl5520.com--经典名言】
树的定义
篇一:给定树的父子关系,求这棵树的高度
树的定义
树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:
1、单个结点是一棵树，树根就是该结点本身。
2、设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n
作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称
n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
一棵典型的树如图1所示：
图1 树的层次结构
由图1可以看出树的形状就像一棵现实中的树，只不过是倒过来的。 树的相关术语
1. 一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结点的
最大度数。
2. 树中度为零的结点称为叶结点或终端结点。
3. 树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统
称为内部结点。
例如在图1中，结点A，B和E的度分别为3，2，0。其中A为根结点,B为内部结点，E为叶结点，树的度为3。
4. 如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父
结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。 例如，在图1中，结点A到结点I有一条路径ABFI，它的长度为3。
5. 如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，
也称结点M是结点K的子孙或后裔。
例如在图1中，结点F的祖先有A，B和F自己，而它的子孙包括它自己和I,J。注意，任一结点既是它自己的祖先也是它自己的子孙。
6. 我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子
孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。
7. 树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径
的长度。树的高度是指根结点的高度。
例如图1中的结点B，C和D的高度分别为2，0和1，而树的高度与结点A的高度相同为3。
8. 从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的
深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。
例如，在图1中，结点A的深度为0；结点B，C和D的深度为1；结点E，F，G，H的深度为2；结点I和J的深度为3。在树的第二层的结点有E，F，J和H，树的第0层只有一个根结点A。
9. 树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子
孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,..k)。
图2中的两棵树作为无序树是相同的，但作为有序树是不同的，因为结点a的两个儿子在两棵树中的左右次序是不同的。后面，我们只关心有序树，因为无序树总可能转化为有序树加以研究。
图2 两棵不同的有序树
我们还可以将兄弟结点之间的左右次序关系加以延拓：如果a与b是兄弟，并且a在b的左边，则认为a的任一子孙都在b的任一子孙的左边。
森林是m(m>0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个树表。在这种情况下，称这些树组成的森林为有序森林或果园。
10. 在讨论表的时候，我们对表的每一位置的元素赋予一个元素值。这里，我们
也用树的结点来存储元素，即对于树中的每一个结点赋予一个标号，这个标号并不是该结点的名称，而是存储于该结点的一个值。结点的名称总是不变的，而它的标号是可以改变的。我们可以做这样的类比：
树：表 = 标号：元素 = 结点：位置
*树的数学定义
连通无回路的无向图称为无向树，简称树。若该无向图至少含有两个连通分支，则称为森林。
在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。 设D是有向图，若D的基图是无向树，则称D为有向树。
设T是n(n≥2)阶有向树，若T中有一个顶点的入度为0，其余顶点的入度均为1，则称T为根树。入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点。从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高。将平凡树也称为根树。
注意：在计算机学中所讨论的树和纯粹数学中的树有所不同。事实上，计算机学中的树就是离散数学中的根树。
父亲数组表示法
设T是一棵树，表示T的一种最简单的方法是用一个一维数组存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域，这样可使Parent操作非常方便。类型定义如下： Type
TPosition=integer; {结点的位置类型为整型}
NodeType=Record
Label:LabelType; {该结点的标号}
Parent:TPosition; {该结点的父亲的数组下标,对于根结点该域
为0}
End;
TreeType=Record
NodeCount:integer; {树的结点的总数目}
Node:Array [1..MaxNodeCount] of NodeType;{存储树的结点}
End;
由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲，再到其祖父等等。求这样的道路所需的时间正比于道路上结点的个数。在树的父亲数组表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。
父亲数组实现的树操作
函数 Parent(v,T)
功能
这是一个求父结点的函数，函数值为树T中标号为v的结点的父亲。当v是根结点时，函数值为0，表示结点v没有父结点。 实现
Function Parent(v:TPosition;var T:TreeType):TPosition； begin
return(T.Node[v].Parent);
end;
说明
由于每个结点都有一个域存储了其父亲结点的标号(数组下标)，因此Parent操作实现非常简单。
复杂性
显然为O(1)。
函数 Leftmost_Child(v,T)
功能
这是一个求最左儿子结点的函数。函数值为树T中标号为v的结点的最左儿子。当v是叶结点时，函数值为0，表示结点v没有儿子。 实现
Function
Leftmost_Child(v:TPosition;var T:TreeType):TPosition;
begin
i:=v+1;
while (i<=T.NodeCount)and(T.Node[i].Parent<>v)
do inc(i);
if i=T.NodeCount+1 then return(0)
else
return(i);
end;
说明
因为没有保存每个结点的子结点的信息，因此只能依次扫描每个结点，根据我们的约定，子结点一定排在父结点的后面，且兄弟结点的下标从左到右依次递增，因此第一次遇到的父亲是n的结点就是n的最左结点。
复杂性
该算法的复杂性取决于while循环。若设T.NodeCount=n，显然，在最坏情况下循环执行n-v次，最好情况下执行1次，平均情况下执行(n-v)/2，所以无论何种情况下，复杂性都为O(n)。
函数 Right_Sibling(v,T)
功能
这是一个求右邻兄弟的函数，函数值为树T中结点v的右邻兄弟。当v没有右邻兄弟时，函数值为0。
实现
Function
Right_Sibling(v:TPosition;var T:TreeType):TPosition;
begin
i:=v+1;
while
(i<=T.NodeCount)and(T.Node[i].Parent<>T.Node[v].Parent) do
inc(i);
if i=T.NodeCount+1 then return(0)
else
return(i);
end;
说明
依次搜索排在v之后的结点，遇到第一个与v有相同父结点的结点就是v的右邻兄弟。
复杂性
同Leftmost_Child一样，该函数复杂性为O(n)，其中n为树的总结点数。
函数 Create(i,x,T1,T2,..,Ti)
功能
这是一族建树过程。对于每一个非负整数i，该函数生成一棵新树T，T的根结点是标号为x的新结点v，并令v有i个儿子，这些儿子从左到右分别为树T1,T2,..,Ti的根。当i=0时，v既是树根，又是树叶。
实现
Procedure Create(i:integer;var x:LabelType;var
T1,T2,..,Ti,T:TreeType);
var
k,j,father:integer;
begin
with T do
begin
NodeCount:=1;
Node[1].Label:=x;
Node[1].Parent:=0; {生成根结点}
for k:=1 to i do
if Tk.NodeCount<>0 then
begin
inc(NodeCount);
Node[NodeCount]:=Tk.Node[1];
Node[NodeCount].Parent:=1;{修改Tk的根结点的父亲使其指向T的根}
树结构
篇二:给定树的父子关系,求这棵树的高度
第3章 树结构
3.2 习题
3.2.1 填空题
3-1 已知(L,N)，(G,K)，(G,L)，(G,M)，(B,E)，(B,F)，(D,G)，(D,H)，(D,I)，(D,J)，(A,B)，(A,C)，(A,D)是表示一棵树中具有父子关系的边，那么：
（1）树的根、叶、非叶结点分别是__________。
（2）树的高度为______________。
（3）各个结点的度数分别是_____________。
（4）各个结点的层数分别是_____________。
（5）结点G的父亲、真祖先、儿子、真子孙、兄弟分别是__________。
3-2 含3个结点的普通树的树形共有（1）____种，其树形分别为（2）__________。
3-3 含3个结点的二叉树的树形共有（1）____种，其树形分别为（2）___________；其中有（3）____个是完全二叉树。
3-4 图3-1中：
二叉树1的先序、中序、后序序列分别为：（1）_____________。
二叉树2的先序、中序、后序序列分别为：（2）_____________。
图3-1
3-5 任何二叉树的叶结点在先序、中序和后序序列中的相对次序_____。
3-6 由二叉树的先序序列和中序序列，求后序序列：
先序序列ABDGCEF，中序序列DGBAECF，后序序列是（1）___________。
先序序列ABEFGCD，中序序列BFEGADC，后序序列是（2）___________。
3-7 由二叉树的后序序列和中序序列，求先序序列：
后序序列DBKHFEGCA，中序序列DBAKHEFCG，先序序列是（1）__________。
后序序列HGFBEDCA，中序序列HFGBAECD，先序序列是（2）__________。
3-8 由正则二叉树的先序序列和后序序列，求中序序列：
先序序列ABCDE，后序序列BDECA，中序序列是（1）__________。
先序序列ABCDFGHKE，后序序列BFHKGDECA，中序序列是（2）__________。 3-9 已知二叉树的先序序列是15，5，3，10，8，11，18，24，而后序序列是3，8，11，10，5，24，18，15，除结点18只有右儿子而无左儿子之外，其余每个非叶结点均有两个儿子。那么，它的中序序列是____________。
3-10 已知二叉树的扩充先序序列是“ABC空空DE空FG空空空空空”。那么，它的中序序列是（1）__________，后序序列是（2）_________。
3-11 （1）已知检索树的先序序列是18，16，8，29，21，27，38，那么，它的后序序列是________________。
（2）已知检索树的后序序列是12，21，19，67，45，23，那么，它的先序序列是________________。
3-12 由输入序列46，70，25，15，28，10，36，78，55所构造的检索树，其先序序列是
（1）_____________，后序序列是（2）___________。在此树上插入结点30和32后，它的先序序列是（3）___________。再删除结点46，它的后序序列是（4）__________。 3-13 由权14，7，8，2，5，4，23所构造的Huffman树为（1）________，该树的权W(T)=
（2）__________（要列出计算步骤）。
3-14 已知字符集{A，B，C，D，E，F}各字符的Huffman编码依次是011，010，10，001，11，000，那么，对编码序列“01011011000111011001”的译码结果是___________。 答案
3-1此题所描述的树结构如图3-2所示
图3-2
（1）根结点：A ；叶结点：E、F、C、K、N、M、H、I、J；非叶结点：B、D、G、L；
（2）5
（3）度为0的结点：E、F、C、K、N、M、H、I、J；度为1的结点：L；度为2的结点：B；度为3的结点：A、G；度为4的结点：D
（4）层数为1的结点：A；层数为2的结点：B、C、D；层数为3的结点：E、F、G、H、I、J；层数为4的结点：K、L、M；层数为5的结点：N
（5）D，A、D，K、L、M，K、L、M、N，H、I、J
3-2（1）2
（2）如图3-3所示：
图3-3
3-3（1）5
（2）如图3-4所示：
图3-4
（3）1
3-4（1）ABDGCEFH，DGBAECHF，GDBEHFCA （2）ABDEFCG，DFEBAGD，FEDBGCA 3-5 是一致的
3-6（1）GDBEFCA （4）FGEBDCA
3-7（1）ABDCEHKFG （2）ABFHGCED
3-8（1）BADEC （2）BAFDHGKCE
3-9 3，5，8，10，11，15，18，24
3-10（1）CBEGFDA （2）CGFEDBA
3.11（1）8，16，27，21，38，29，18 （2）23，19，12，21，45，67给定树的父子关系,求这棵树的高度。
3-12（1）46，25，15，10，28，36，70，55，78
（2）10，15，36，28，25，55，78，70，46
（3）46，25，15，10，28，36，30，32，70，55，78
（4）10，15，32，30，28，25，55，78，70，36
3-13（1）如图3-5所示：
图3-5
（2）（14＋23）×2＋（5＋7+8）×3＋（2＋4）×4＝158
（3）如图3-6所示：
图3-6
3-14 BEAFECED
3.2.3 选择题
3-15 k层满三元树的结点数为____。
A．(3-1)/2 kB．3-1 kC．(3-1)/3 kD．3 k
3-16 高为h的m元树（m≥2， h≥1）的第i层上结点数ni（1）_____，树中结点总数n
（2）_____。
（1）A．≤mi
B．≤mi-1 C．≤mi+1 D．≥mi-1 D．≤mh/(m-1) （2）A．≤mh+1-1 B．≥mh+1-1 C．≤(mh-1)/(m-1)
3-17 若三元树中，度数为1，2，3的结点数分别是2，1，3。叶子数必为____个。
A．4 B．5 C．6 D．7
3-18 图3-7中，_____都是完全二叉树。
A．1和4
3
1
(1) (2) (3) (4)
图3-7
3-19 对普通树先根遍历的规则是：先访问根结点，再依次遍历根的各个子树；后根遍历的规则是：先依次遍历根的各个子树，再访问根结点。
对普通树T先根遍历和后根遍历得到先根序列和后根序列，
与将T转换成二叉树B的先序序列、中序序列、后序序列之间的关系是_____。
A．T的先根序列与B的先序序列相同
C．T的先根序列与B的中序序列相同 B．T的后根序列与B的后序序列相同 D．无简单的对应关系
3-20 图3-8所示的二叉树是由某森林转换而来的，那么原森林中，共有（1）_____棵树，共有（2）_____片叶子。
A．3 B．4 C．5 D．6
图3-8
3-21 若二叉树中，2度结点数为m，则叶子数为____。
A．m B．m+1 C．2m D．不确定
3-22 若k元正则树中共有m个非叶结点，则叶子数________。
A．≥(k-1)m B．≤km C．=(k-1)m-1 D．=(k-1)m+1
3-23 高度为h的正则二叉树至少有_____结点。
A．2h B．2h-1 C．2h+1 D．2h+1
3-24 二叉树的中序序列之中，根结点r的右边_____。
A．只有r所有的右子孙 B．只有r的一部分右子孙
D．只有r所有的左子孙 C．只有r的一部分左子孙
3-25 二叉树的中序序列之中，结点a排在结点b之前的条件是_____。
树的孩子兄弟存储法求树的高度、宽度、结点数、叶子数
篇三:给定树的父子关系,求这棵树的高度
树的孩子兄弟存储法求树的高度、宽度、结点数、叶子数
摘 要
C是一种通用的程序设计语言，C语言在很多方面继承和发展了以往许多高级程序设计语言的成功经验和特色，具有书写格式自由、数据类型丰富、语句功能强大、执行速度快和存储控制能力强等优点。
学生信息管理系统设计是关于对学生各种信息管理来设计的一个系统。整个系统从符合操作简便、界面友好、灵活、实用、安全的要求出发，完成学生信息管理的全过程，包括创建学生信息、查找学生信息、修改学生信息、插入学生信息、删除学生信息、按平均分或者总分排序、统计学生信息等工作。
本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词：学生管理系统，C语言，数据结构，Wintc
目录
树的孩子兄弟存储法求树的高度、宽度、结点数、叶子数.................. 1
摘 要.............................................................. 1 1 课题背景介绍 .................................................... 1
1.1 课题背景 ............................................................................................................................ 1
1.2 目的 .................................................................................................................................... 1 2 需求分析 ........................................................ 2
2.1 数据需求分析 .................................................................................................................... 2
2.2 功能需求分析 .................................................................................................................... 2 3 系统总体设计 .................................................... 3
3.1 系统模块划分 .................................................................................................................... 3
3.2 系统模块结构图 ................................................................................................................ 3 4 系统详细设计 .................................................... 4
4.1创建孩子兄弟存储法 ......................................................................................................... 4
4.2计算结点数 ......................................................................................................................... 4
4.3计算树的高度 ..................................................................................................................... 5
4.4计算树的叶子数 ................................................................................................................. 5
4.5计算树的宽度 ..................................................................................................................... 6
总 结.............................................................. 7
参考文献............................................................ 8给定树的父子关系,求这棵树的高度。
1 课题背景介绍
1.1 课题背景
随着网络技术的迅速发展，各种行业纷纷应用网络技术操作和管理。当然学校是一个很大的管理系统，随着学生的大量增加，其管理难度也越来越大，如何对学生的个人信息进行更好的管理，这就是我们研究这个课题的目的。
在计算机迅速发展的今天，将计算机这一信息处理器应用于学生的个人信息管理已是势必所然，而且这也将学生信息管理带来前所未有的改变。采用计算机对学生的信息管理是信息科学化和现代化的重要标志，它也给各大高校带来了明显的社会效益。主要体现在：极大地提高了管理工作人员的工作效率，大大地减少了以往的资料室所存在的各种弊端，同时也加强和规范学习对于学生信息的管理。
为了能够更好的来实现对学生信息的管理，通过对学生信息管理日常工作的详细调查，搜集了大量的资料，从系统结构的组织，功能的实现，技术的要求以及可行性等多方面进行考虑，认为本课题是一个适应现今学校学生个人信息管理需求的计算机信息管理系统，具有一定的实际开发价值和使用价值。
1.2 目的
本课题运用C语言进行开发，C语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。
经过这一个学期对《数据结构》的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。做这么一个课程设计，一方面是为了检查我们一个学期以来的学习成果，另一方面也是为了让我们进一步的掌握和运用它，同时也让我们认清自己的不足之处和薄弱环节，加以弥补和加强。
2 需求分析
随着学校规模的发展扩大，学校要向着大型化，规模化发展，而对于学生信息管理系统有关的信息随之增加。在这种情况下单靠人工来处理学生的信息不但显得大不从心，而且极容易出错。因此，需要开发学生管理系统，该系统可以实现由计算机代替人工执行一系列复杂而繁琐的操作，使得学校管理人员可以轻松快捷的完成学生信息管理的任务。
2.1 数据需求分析
本系统的主要是使用算法设计利用孩子兄弟存储求树的结点数、叶子数、高度、宽度、树的度。
2.2 功能需求分析
本系统主要实现对学生成绩信息进行管理，需要实现以下几个方面的管理功能：
（1）创建树
（2）求树的结点数。
（3）求树的高度。
（4）求树的叶子树。
（5）求树的宽度。
3 系统总体设计
3.1 系统模块划分
本系统主要是对树的孩子兄弟存储法求树的各项运算。整个系统分为以下几
3.2 系统模块结构图
根据系统功能设计，对应的系统模块结构图如图1所示：
图1 系统模块结构图
数据结构(c语言版)习题-树
篇四:给定树的父子关系,求这棵树的高度
一、选择题
1．一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++
3. 在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点。则树T的叶结点个数是( )。
A. 41 B. 82 C. 113 D. 122
4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A．5 B．6 C．7 D．8
5. 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A．9 B．11 C．15 D．不确定
8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A．M1 B．M1+M2 C．M3 D．M2+M3
9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。
A． 250 B． 500 C．254 D．505 E．以上答案都不对
10. 设给定权值总数有n 个，其哈夫曼树