计算机软件基础(自考本科树)

1、1. 树的定义树的定义树：是一个具有树：是一个具有n（n0）个节点的）个节点的有限有限集合集合T。满足以下两个条件：满足以下两个条件：（1） 任意一颗树有且仅有一个特定的根节点（任意一颗树有且仅有一个特定的根节点（root node）。）。（2）除根节点以外，其余节点可以分为）除根节点以外，其余节点可以分为m（m 0 ）个互不相交的子集个互不相交的子集T1，T2, Tm，其中每个子集本，其中每个子集本身又是一颗树，称为根的身又是一颗树，称为根的子树子树。结论：结论：一棵树由若干子树构成，而每一颗子树由一棵树由若干子树构成，而每一颗子树由若干颗子子树构成。若干颗子子树构成。2. 树的表示形式树的

2、表示形式3. 树的有关名词树的有关名词（1）节点的度：节点的孩子数。）节点的度：节点的孩子数。（2）树的度）树的度=树的叉树的叉=拥有孩子最多节点的孩子个数拥有孩子最多节点的孩子个数（3）叶子节点）叶子节点=终端节点终端节点=没有孩子的节点没有孩子的节点（4）双亲节点：指的是这个节点的父亲节点。）双亲节点：指的是这个节点的父亲节点。（5）树的高度）树的高度=树的层数树的层数1. 二叉树：最多具有两个树杈的树。其中，左边的二叉树：最多具有两个树杈的树。其中，左边的树杈称为该节点的左子树，右边的树杈称为该节点树杈称为该节点的左子树，右边的树杈称为该节点的右子树。的右子树。2. 二叉树的基本形态：共

3、二叉树的基本形态：共5种种3. 二叉树与一般树的区别：二叉树与一般树的区别：一般树一般树二叉树二叉树树中至少有一个根节树中至少有一个根节点（点（n0）可以一个根节点都没可以一个根节点都没有（有（n 0）树的度树的度0树的度树的度2不要求子树木顺序不要求子树木顺序（无序树）（无序树）子树有左、右之分子树有左、右之分（有序树）（有序树）4. 二叉树的性质二叉树的性质性质性质1：二叉树的第：二叉树的第 i 层上最多有层上最多有2i-1个节点（个节点（i ）；）；性质性质2：高度为：高度为 k 的二叉树最多有的二叉树最多有2k-1个节点（个节点（k ） ；性质性质3：任意一颗二叉树中，如果没有孩子的节

4、点个数：任意一颗二叉树中，如果没有孩子的节点个数为为n0，有两个孩子的节点个数为，有两个孩子的节点个数为n2，那么，那么n0=n2+15. 二叉树的两种特殊情形：二叉树的两种特殊情形：（1）满满二叉树：除叶子节点以外，其它节点都有两个二叉树：除叶子节点以外，其它节点都有两个孩子，而且叶子节点位于同一层上的二叉树。孩子，而且叶子节点位于同一层上的二叉树。（2）完全完全二叉树：一个满二叉树的最下层，从右向左二叉树：一个满二叉树的最下层，从右向左连续连续缺少缺少n个节点的二叉树。个节点的二叉树。注意：注意：深度为深度为k的满二叉树，有的满二叉树，有2k-1个节点个节点例：例： （2010.4单选）一

5、个深度为单选）一个深度为 k 的完全二叉树中的完全二叉树中节点数至少有（节点数至少有（ ）。）。A 2k B 2k-1 C 2k+1 D 2k-1例例10-1 试写出具有试写出具有3个节点的所有不同形态的树和个节点的所有不同形态的树和二叉树。二叉树。二叉树有五种：二叉树有五种：树有树有2种：种：6. 二叉树的存储结构二叉树的存储结构顺序存储顺序存储操作步骤为：操作步骤为： step1：现将二叉树变成完全二叉树（给有关节点补：现将二叉树变成完全二叉树（给有关节点补够两个孩子，所补节点为虚拟节点，仅占个空间）够两个孩子，所补节点为虚拟节点，仅占个空间） step2：将这个完全二叉树中各节点从上到下

6、，逐层：将这个完全二叉树中各节点从上到下，逐层由左向右一次存放到计算机连续空间中。由左向右一次存放到计算机连续空间中。例例10-2：例例10-3 一个深度为一个深度为K且只有且只有K个节点的二叉树顺序存储个节点的二叉树顺序存储最多需要多少个存储空间，最少需要多少个。最多需要多少个存储空间，最少需要多少个。（2）完全二叉树节点顺序编号的意义）完全二叉树节点顺序编号的意义例例10-4 一个完全二叉树节点个数为一个完全二叉树节点个数为1000，则，则n0、n1、n2和高度和高度h各为多少各为多少?6. 二叉树的存储结构二叉树的存储结构链式存储链式存储（1）二叉树）二叉树链式存储中，每个节点有链式存储

7、中，每个节点有3个成员（域）个成员（域） 6. 二叉树的存储结构二叉树的存储结构链式存储链式存储（2）二叉树）二叉树链式存储类型的定义链式存储类型的定义例例10-51. 中序中序遍历遍历如果二叉树不为空，则依次执行如下操作：如果二叉树不为空，则依次执行如下操作：（1）先：）先：中序遍历中序遍历左子树；左子树；（2）再：）再：访问访问根节点；根节点；（3）最后：）最后：中序遍历中序遍历右子树。右子树。 二叉树的遍历：按照一定的顺序访问树中所有节点，二叉树的遍历：按照一定的顺序访问树中所有节点，而且每个节点仅被访问一次的操作。而且每个节点仅被访问一次的操作。例：如图所示二叉树，试写出对其例：如图所

8、示二叉树，试写出对其中序中序遍历的结果。遍历的结果。中序遍历结果：中序遍历结果： DBGEHACIF中中序遍历的算法描述序遍历的算法描述1. 先序先序遍历遍历如果二叉树不为空，则依次执行如下操作：如果二叉树不为空，则依次执行如下操作：（1）先：）先：访问访问根节点；根节点；（2）再：）再：先序遍历先序遍历左子树；左子树；（3）最后：）最后：先序遍历先序遍历右子树。右子树。例：如图所示二叉树，试写出对其例：如图所示二叉树，试写出对其先序先序遍历的结果。遍历的结果。先序遍历结果：先序遍历结果：ABDEGHCFI1. 后序后序遍历遍历如果二叉树不为空，则依次执行如下操作：如果二叉树不为空，则依次执行

9、如下操作：（1）先：）先：后序遍历后序遍历左子树；左子树；（2）再：）再：后序遍历后序遍历右子树；右子树；（3）最后：）最后：访问访问根节点根节点 。例：如图所示二叉树，试写出对其例：如图所示二叉树，试写出对其后序后序遍历的结果。遍历的结果。后序遍历结果：后序遍历结果：DGHEBIFCA结论：由结论：由先序和中序先序和中序或或后序和中序后序和中序遍历结果，可以确遍历结果，可以确定唯一的一棵二叉树。定唯一的一棵二叉树。口诀：口诀：先序后序定树根；先序后序定树根；中序区分左和右。中序区分左和右。例：（例：（2010.4）已知二叉树的）已知二叉树的后序后序遍历序列是遍历序列是dabec，中序中序遍历

10、序列是遍历序列是debac，它的前序遍历序列，它的前序遍历序列是是 。例例10-7 已知二叉树的已知二叉树的后序后序遍历序列和遍历序列和中序中序遍历序列结遍历序列结果分别是果分别是DGHEBIFCA和和DBGEHACIF，试确定这，试确定这个二叉树。个二叉树。一、一、 树的存储结构树的存储结构1、双亲静态链表存储法、双亲静态链表存储法序号节点双亲0A-11B02C03D04E25F2一、一、 树的存储结构树的存储结构2、孩子链表存储法、孩子链表存储法datanext0A1231B2C453D4E5F1）树的孩子兄弟表示树的孩子兄弟表示口诀：竖线连接口诀：竖线连接左左孩子，横线连接孩子，横线连接

11、亲亲兄弟。兄弟。例：将如图所示树，用树的孩子兄弟表示。例：将如图所示树，用树的孩子兄弟表示。3、孩子兄弟链式存储法、孩子兄弟链式存储法2）用链连接各节点。用链连接各节点。3、孩子兄弟链式存储法、孩子兄弟链式存储法1. 树变二叉树树变二叉树step1:写出树的孩子兄弟表示；写出树的孩子兄弟表示；step2:将竖线变成左子树，横向变成右子树。将竖线变成左子树，横向变成右子树。一、一、 树的存储结构树的存储结构3. 树的遍历树的遍历树的遍历有：先序和后序树的遍历有：先序和后序注意：注意：树的树的先序先序遍历结果与对应二叉树的遍历结果与对应二叉树的先序先序遍历结果相同；遍历结果相同；树的树的后序后序遍

12、历结果与对应二叉树的遍历结果与对应二叉树的中序中序遍历结果相同。遍历结果相同。4. 森林变二叉树森林变二叉树step1: 把构成森林的每一棵树变成二叉树；把构成森林的每一棵树变成二叉树；step2: 依次把后一棵二叉树连在前一棵二叉树依次把后一棵二叉树连在前一棵二叉树根根的的右子树上。右子树上。4. 森林变二叉树（续）森林变二叉树（续）5. 森林的遍历森林的遍历森林的遍历有：先序和后序森林的遍历有：先序和后序注意：注意：森林的森林的先序先序遍历结果与对应二叉树的遍历结果与对应二叉树的先序先序遍历结果相同；遍历结果相同；森林的森林的后序后序遍历结果与对应二叉树的遍历结果与对应二叉树的中序中序遍历

13、结果相同。遍历结果相同。例例.（2010.4解答）已知下图所示的二叉树，要求：解答）已知下图所示的二叉树，要求：（1）将该二叉树还原成森林；）将该二叉树还原成森林；（2）写出森林的先根遍历序列和后根遍历序列）写出森林的先根遍历序列和后根遍历序列解（解（1）将该二叉树还原成森林；）将该二叉树还原成森林；（2）写出森林的先根遍历序列和后根遍历序列）写出森林的先根遍历序列和后根遍历序列解（解（1）将该二叉树还原成森林；）将该二叉树还原成森林；解（解（1）将该二叉树还原成森林；）将该二叉树还原成森林；解（解（2）先根遍历序列：）先根遍历序列：abdgcefhij后根遍历序列：后根遍历序列：bgdaec

14、ihjf1. 几个基本术语几个基本术语 （1）第）第i个个叶子节点的叶子节点的权值权值Wi：给第：给第i个节点所赋予的个节点所赋予的重要程度值；重要程度值； （2）第）第i个叶子节点的个叶子节点的路径长度路径长度Li：从根到第：从根到第i个节点个节点所经路径的段数；所经路径的段数； （3）第）第i个叶子节点的个叶子节点的带权路径长度带权路径长度WPLi： WPLi=WiLi； （4）树的）树的带权路径长度带权路径长度WPL：等于该树中所有叶子：等于该树中所有叶子 的带权路径长度之和。的带权路径长度之和。2.就是带权路径长度为就是带权路径长度为最小最小的的二叉树二叉树。3.step1：将该树的叶

15、子权值：将该树的叶子权值由小到大由小到大进行排序；进行排序；step2：从所排序中取出两个最小的权值：从所排序中取出两个最小的权值 和和 构造构造二叉树，该二叉树的根节点为二叉树，该二叉树的根节点为W（ ）iW1iW1iiWWWstep3：从权值序列中划去：从权值序列中划去 和和 。划去后，如果。划去后，如果序列为空，说明所要求的二叉树已经构成；否则，序列为空，说明所要求的二叉树已经构成；否则，将将W加入权值序列中，重复加入权值序列中，重复step1step3。iW1iW例：（例：（09.4月）给定一组权值：月）给定一组权值：4、1、12、2、10，构，构造对应的造对应的step1：按权值：按

16、权值由小到大由小到大排序：排序：1step2：取两个最小权值，：取两个最小权值，、2 、 4 、1012、3构建一颗二叉树构建一颗二叉树12step3：从原序列中划去：从原序列中划去1和和2将将3插入到序列中插入到序列中3step3：重复步骤：重复步骤1347710171217294.（1）（2）（3）（4）5. 哈夫曼编码哈夫曼编码（1）定义：长度最小的二进制串电文编码。）定义：长度最小的二进制串电文编码。（2）求哈夫曼编码的步骤：）求哈夫曼编码的步骤：step1：构造哈夫曼树构造哈夫曼树（依据：以电文中各字符出现的（依据：以电文中各字符出现的次数为权值）；次数为权值）；step2：构造哈夫曼编码树构造哈夫曼编码树（方法：（方法：在在哈夫曼树哈夫曼树左子左子树的边上添树的边上添0，右子树的边上添，右子树的边上添1）；）；step3：求各字符的哈夫曼编码求各字符的哈夫曼编码（从根到各字符节点（从根到各字符节点路径上的二进制序列路径上的二进制序列）；）；例：（例：（2008.04）假设字符）假设字符a，b，c，d，e，f使用的频率分别为使用的频率分别为0.