课程名称 数据结构B 章节名称 树和二叉树
授课学时 总学时：6 课堂学时：6
教学目标与要求:
了解：树、森林的概念；二叉树的概念、性质和表示
掌握：二叉树遍历方法；二叉树的特点及寻找结点的前驱和后继；树和森林的实现与遍历；二叉树的实现、计数方法。
掌握：霍夫曼树的实现方法及霍夫曼编码的概念。
主要知识点、重点、难点
知识点：1）树、森林、二叉树的定义
2）二叉树的定义、性质、抽象类型、数组表示和链表存储表示
3）二叉树的遍历，二叉树的存储表示，二叉树的计数
4）霍夫曼树
重点难点：1）二叉树的定义、性质、抽象类型、数组表示和链表存储表示
2）二叉树的遍历，二叉树的存储表示
教学过程设计
强调二叉树的重要性；利用实例说明二叉树在解决实际问题中的灵活性及二叉树的特点
作业
建立二叉树-并对树进行操作数据结构课程设
1
课题名:建立二叉树,并对树进行操作
系别:信息与计算科学系
年级:2009级
专业:数学与应用数学
班级:一班
学号:2009031116、2009031112、2009123123、2009031102、2009031110
姓名:唐永桥、杨文升、李兵、陈丕权、范庆勇
指导老师:李学勇
2 2011-5-10
目录
摘 要 ........................................................................................... 错误!未定义书签。
1、引言 ......................................................................................... 错误!未定义书签。
1.1设计目标 .................................................................................................... 5
1.2 相关知识 ................................................................................................... 5
2、总体设计 ............................................................................................................... 10
2.1主要数据存储结构设计 .......................................................................... 10
数据结构—学习笔记四
主 题： 《数据结构》学习笔记
内 容：
《数据结构》学习笔记四
——树
一、树形结构
1、术语：
树、子树、根结点、结点的度、叶结点、树的度、结点的子结点、结点的父结点、
结点 的层次、树的深度（高）、森林。
2、二叉树：
2.1二叉树不属于“树”。
2.2 二叉树的性质：
①在二叉树的第i层上至多有2i-1个结点（i≥1）
②深度为K的二叉树至多有2k-1个结点（k≥1）
③对任何一棵二叉树，如叶结点的个数为n0，2度结点个数为n2则n0＝n2+1
说明：分支数为B，二叉树的结点总数为n=n0+n1+ n2
∵B=n-1(从结点的头上看)
B=n1+2n2（从结点的下方看）
∴n-1=n1+2n2即n0+n1+n2-1=n1+2n2
∴n0＝n2+1
3、二叉树的存储结构：
struct node
{char data;
struct node *lchild;
struct node *rchild;
}
4、树转换为二叉树：
（右链为兄弟） A
BC
DEFA
C
E^^F^^B^
D^^datalchildrchild
A
BC
DE
FA
B
C
DE
F数据结构—学习笔记四 -
二、遍历二叉树
1、规则：
1.1先序：打印，遍历左子树，遍历右子树。A，B，D，C，E，F
1.2中序：遍历左子树，打印，遍历右子树。D，B，A，E，C，F
1.3后序：遍历左子树，遍历右子树，打印。D，B，E，F，C，A
2、实例
a*b-c此式可画成一个二叉树，如左：
先序： -*abc
中序： a*b-c
后序： ab*c-
3、程序：
3.1先序：
preorder(p)
struct node *p
{if (p)
{printf(“%c,”,p->data);
preorder (p->lchild);
preorder(p->rchild);
}
数据结构之⼆叉树（BinaryTree）⽬录
导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。
⽬录
⼀、 ⼆叉树的定义
⼆、⼆叉树为何不是特殊的树
三、⼆叉树的五种基本形态
四、⼆叉树相关术语
五、⼆叉树的主要性质（6个）
六、⼆叉树的存储结构（2种）
七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码
⼀、⼆叉树的定义
如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。定义：⼆叉树是n(n≥0)个结点的有限集，
⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。（这⾥的左⼦树和右⼦树也是⼆叉树）。 值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。具体分析如下
⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同
⼆叉树的⼦树有左右之分，不能颠倒。⽆序树的⼦树⽆左右之分。 2、⼆叉树与有序树也不同（关键）
当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：
三、⼆叉树的五种基本状态
四、⼆叉树相关术语
满⼆叉树：所有叶⼦结点全部集中在最后⼀层，这样的⼆叉树称为满⼆叉树。（注意：国内的定义是每⼀层的结点都达到最⼤值时才算是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。这两种概念完全不同，既
然在国内，我们就默认第⼀种定义就好）。
完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置
的编号完全对应，那么这就是⼀颗完全⼆叉树。如图所⽰：
五、⼆叉树的主要性质
⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。
