大学《数据结构》第五章：树和二叉树-第一节-树的基本概念和术语

本章概览当前讲授一、知识结构二、本章重难点本章重点是二叉树的各种次序的遍历及其应用，二叉树的线索化的方法及应用、使用哈夫曼算法生成哈夫曼树和构造哈夫曼编码，其中二叉树的运算，要求达到"综合应用"层次。难点是有关树和二叉树的应用问题的算法设计和实现。

第一节树的基本概念和术语当前讲授一、引言树形结构是一类重要的非线性数据结构，树中结点之间具有明确的层次关系，并且结点之间有分支，非常类似于真正的树。树形结构在客观世界中大量存在，如行政组织机构和人类社会的家谱等都可用树形结构形象地表示。二、树的定义1、树(Tree)是n(n≥0)个结点的有限集T，n=0时称为空树，任意非空树（1）有且仅有一个特定的称为根(Root)的结点；（2）n>1时，除根结点外的其余结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。2、从逻辑上看，树形结构具有以下特点：（1）任何非空树中有且仅有一个结点没有前驱结点，这个结点就是树的根结点。（2）除根结点之外，其余所有结点有且仅有一个直接前驱结点。（3）包括根结点在内，每个结点可以有多个直接后继结点。（4）树形结构是一种具有递归特征的数据结构。（5）树形结构中的数据元素之间存在的关系通常是一对多，或者多对一的关系。三、树的表示法1、树结构2、嵌套集合3、凹形表示法4、广义表表示法（A（B（E，（F（J,K））），C（G），D（H，I）））四、树结构的基本术语（1）结点的度：结点所拥有的子树的个数。如A的度为3，E的度为2。（2）树的度：树中结点度的最大值。如图4-1所示的树的度为3。（3）叶子（终端结点）：度为0的结点。如K，L，F，J等结点都是叶子结点。（4）分支结点（非终端结点）：度不为0的结点。除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。如A，B、I等结点是分支结点。（5）孩子：结点的直接后继（即结点的子树的根）。如B是A的孩子，N是I的孩子。（6）双亲：结点的直接前趋。如B的双亲是A，N的双亲是I。（7）兄弟：同一双亲的孩子互为兄弟。如B、C，D互为兄弟，M，N互为兄弟。（8）子孙：一棵树上的任何结点（不包括根结点）称为根的子孙。如图中其它结点都是根结点A的子孙。（9）祖先：从根结点开始到该结点连线上的所有结点（除该结点）都是该结点的祖先。如N的祖先是I，C，A。（10）路径：若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条路径或道路。路径的长度指路径所经过的边（即连接两个结点的线段）的数目，等于j-1。注意：若一个结点序列是路径，则在树的树形图表示中，该结点序列"自上而下"地通过路径上的每条边。从树的根结点到树中其余结点均存在一条唯一的路径。（11）结点的层：设根结点的层数为1，其余结点的层数等于双亲结点的层数加1。如B的层数是2，N的层数是4。（12）树的高度（或深度）：树中所有结点层数的最大值。图所示的树的高度为4。（13）有序树和无序树：将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树；否则称为无序树。（14）森林：是m(m≥0)棵互不相交的树的集合。树和森林的概念相近，删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。五、树的性质性质一：非空树中的结点总数等于树中所有结点的度之和加1。证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个双亲结点，即每个结点与指向它的一个分支结点一一对应，因而除了树的根结点之外的结点数等于树中所有结点的分支数（度数），由此可得知树中的结点总数应为所有结点的度之和加1。性质二：度为k的非空树的第i层最多有ki-1个结点（i≥1）。证明：（略）性质三：深度为h的k叉树最多有

个结点。证明：显然，只有当深度为h的k叉树上的每一层都达到该层最大结点总数时，该树的结点总数将达到最大，因此，有证毕【真题选解】（例题•填空题）已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为

。隐藏答案【答案】((k-1)×n+1)／k【解析】设度为k的分支结点数为nk，度为0的叶子结点数为n0，树中总分支数为B。除根结点之外，其他每个结点都有且仅有一个进入支，而这些进入支是由度为k的结点发出的，度为k的结点总共发出k×nk个分支。显然有：nk=n-n0