严蔚敏数据结构 ch6 树和二叉树

2i-1 … … 2i-1
2层：21 … i层：2i-1 …
2k-1
2k-1 k层：2k-1
满二叉树和完全二叉树
满二叉树：一棵深度为k且有2k-1个结点的二叉树。 完全二叉树：若深度为k、有n个结点的二叉树中各结
点能与深度为k的顺序编号的满二叉树编号从1到n的结 点相对应。
所有的叶结点都出现在第k层或k－1层。 若任一结点右子树最大层次为l，其左子树最大层
{ if(visit(T->data))//访问当前的根结点 if(PreorderTraverse(T->lchild,visit))//先序遍历左子树 if(PreorderTraverse(T->rchild,visit))//先序遍历右子树 return OK;
return ERROR;//若访问不到当前根结点值，出错 } else return OK;//树空 } 时间复杂度：n个结点的二叉树先序遍历时间复杂度O(n)
} ADT Tree
6．1树的定义和基本术语（续）
结点的度：分支的个数 树的度：树中所有结点的度的最大值 树的深度（高度）：树中叶子结点所在的最大层次
6．1树的定义和基本术语（续）
双亲(结点)： 孩子(结点)：结点子树的根称为该结点的孩子 祖先(结点) ：从根到该结点所经分支上的所有结点。 子孙(结点) ：以某结点为根的子树的任一结点 兄弟(结点) ：同一双亲的孩子互称兄弟。 堂兄弟(结点) ：双亲在同一层的结点互称堂兄弟
typedef struct BiTNode {
TElemType data; struct BiTNode *lchild,*rchild;
lChild rChild
} BiTNode,*BiTree;

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第7 章查找 (54)第8 章排序 (65)第1章绪论1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，± 1，± 2,, }，字母字符数据对象是集合C={ ‘ A',' B'，,，‘ Z',‘ a','b'，,，' z ' }，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

如图6-1(b)中结点H、I、J、K、L、M、N是叶子 结点，而所有其它结点都是分支结点。
⑷ 孩子结点、双亲结点、兄弟结点
一个结点的子树的根称为该结点的孩子结点(child) 或子结点；相应地，该结点是其孩子结点的双亲结点 (parent)或父结点。
4
如图6-1(b)中结点B 、C、D是结点A的子结点，而结 点A是结点B 、C、D的父结点；类似地结点E 、F是结 点B的子结点，结点B是结点E 、F的父结点。
这是树的递归定义，即用树来定义树，而只有 一个结点的树必定仅由根组成，如图6-1(a)所示。
2
2 树的基本术语
⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。 ⑵ 结点的度(degree) 、树的度：结点所拥有的子树
的棵数称为结点的度。树中结点度的最大值称为树的度。
A
B
C
D
A
E
F G HI J
同一双亲结点的所有子结点互称为兄弟结点。
如图6-1(b)中结点B 、C、D是兄弟结点；结点E 、 F是兄弟结点。
⑸ 层次、堂兄弟结点
规定树中根结点的层次为1，其余结点的层次等于 其双亲结点的层次加1。
若某结点在第l(l≧1)层，则其子结点在第l+1层。
双亲结点在同一层上的所有结点互称为堂兄弟结点。 如图6-1(b)中结点E、F、G、H、I、J。
(a) 只有根结点
K
LM N
图6-1 树的示例形式
(b) 一般的树
3
如图6-1(b)中结点A的度是3 ，结点B的度是2 ，结点 M的度是0，树的度是3 。
⑶ 叶子(left)结点、非叶子结点：树中度为0的
结点称为叶子结点(或终端结点)。相对应地，度不为 0的结点称为非叶子结点(或非终端结点或分支结点)。 除根结点外，分支结点又称为内部结点。

InitQueue(Q);
// 置空的辅助队列 Q
if (T) EnQueue(Q, T); // 根结点入队列
while (!QueueEmpty(Q)) {
DeQueue(Q, p); // 队头元素出队并置为 p
Visit(p);
if (p->Lchild)
EnQueue(Q, p->Lchild); // 左子树根入队列
Void exchg_tree(BiTree BT)
{if (BT!=null)
/*非空*/
{exchg_tree(BT->lchild); /*交换左子树所有结点指针*/
exchg_tree(BT->rchild); /*交换右子树所有结点指针*/
p=BT->lchild;
/*交换根结点左右指针*/
1
９.左边是前驱右边是后继
六、算法设计题 １.解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。 法一：核心部分为： LeafCount (BiTree T) /*中序遍历 递归函数*/ {if(T!=NULL) {if((T ->lchild==NULL)&&( T ->rchild==NULL)){sum++; printf("%d\n", T ->data);}
递归程序执行完毕之后才能出栈，这样才能实现逆序。
７. 解：方案 1；哈夫曼编码先将概率放大 100 倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32