1
第四章 二叉树
任课教员：张铭、赵海燕、冯梅萍、王腾蛟
http://db.pku.edu.cn/mzhang/DS/
北京大学信息科学与技术学院
©版权所有，转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2
主要内容
4.1 二叉树的概念
4.2 二叉树的主要性质
4.3 二叉树的抽象数据类型
4.4 周游二叉树
4.5 二叉树的实现
4.6 二叉搜索树
4.7 堆与优先队列
4.8 Huffman编码树
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3
4.1 二叉树的概念
4.1.1 二叉树的定义及相关概念
4.1.2 满二叉树
完全二叉树
扩充二叉树
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4
二叉树的定义
二叉树由结点的有限集合构成:
或者为空集
或者由一个根结点及两棵不相交的分别称作这个根的左
子树和右子树的二叉树(它们也是结点的集合)组成
这是个递归的定义。二叉树可以是空集合，因此根
可以有空的左子树或右子树，或者左右子树皆为空
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5
二叉树的五种基本形态
(a)空 (b)独根 (c)空右 (d)空左 (e)左右都不空
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6
满二叉树
如果一棵二叉树的任何结点，或者是树叶，
或者恰有两棵非空子树，则此二叉树称作
满二叉树
2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7
完全二叉树
若一颗二叉树
最多只有最下面的两层结点度数可以小于2
最下面一层的结点都集中在该层最左边的若干位置上，
则称此二叉树为完全二叉树
在许多算法和算法分析中都明显地或隐含地用到完
全二叉树的概念
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8
完全二叉树
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9
扩充二叉树
当二叉树里出现空的子树时，就增加新的、特
殊的结点——空树叶
对于原来二叉树里度数为1的分支结点，在它下面
增加一个空树叶
对于原来二叉树的树叶，在它下面增加两个空树叶
扩充的二叉树是满二叉树，新增加的空树叶
(外部结点)的个数等于原来二叉树的结点(内
部结点)个数加1
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10
扩充二叉树
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11
扩充二叉树
外部路径长度E 从扩充的二叉树的根到每个外
部结点的路径长度之和
内部路径长度I 扩充的二叉树里从根到每个
内部结点的路径长度之和
E和I两个量之间的关系为 E=I+2n
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12
4.2 二叉树的主要性质
1.满二叉树定理：非空满二叉树树叶数等于其分支结点数
加1。
证明：设二叉树结点数为n，叶结点数为m，分支结点数
为b。
有n（总结点数= m（叶)+b（分支） (公式4.1)
∵ 每个分支，恰有两个子结点（满），故有2*b条边；
一颗二叉树，除根结点外，每个结点都恰有一条边联接
父结点，故共有n-1条边。即n - 1 = 2b (公式4.2)
∴由(公式4.1)，(公式4.2)得 n-1=m+b-1 = 2b，得出
m(叶) = b（分支）+ 1
3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13
4.2 二叉树的性质
2.满二叉树定理推论：一个非空二叉树的空子树(指针)
数目等于其结点数加1。
证明：设二叉树T，将其所有空子树换为树叶，记新 的
扩充满二叉树为T’。所有原来T的结点现在是T’的分支结
点。根据满二叉树定理，新添加的树叶数目等于T结点
个数加1。而每个新添加的树叶对应T的一个空子树。
因此T中空子树数目等于T中结点数加1。
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14
4.2 二叉树的性质
3.任何一颗二叉树，度为0的结点比度为2的结点多一个
证明：设有n个结点的二叉树的度为0、1、2的结点数
分别为=n
0
，n
1
，n
2
，则
n = n
0
+ n
1
+ n
2
(公式4.3)
设边数为e。因为除根以外，每个结点都有一条边进入，故
n = e + 1。由于这些边是有度为1和2的的结点射出的，
因此e = n
1
+ 2·n
2
，于是
n = e + 1= n
1
+ 2·n
2
+ 1 （公式4.4）
因此由公式（1）（2）得
n
0
+ n
1
+ n
2
= n
1
+ 2·n
2
+ 1
即n
0
= n
2
+ 1
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15
4.2 二叉树的性质
4. 二叉树的第i层（根为第0层，i≥1）最多有2
i
个结点
5. 高度为k(深度为k-1。只有一个根结点的二叉
树的高度为1，深度为0)的二叉树至多有2
k
-1个
结点
6. 有n个结点（n>0）的完全二叉树的高度为
⎡log
2
(n+1)⎤ (深度为⎡log
2
(n+1)⎤ -1)
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16
4.2 二叉树的性质
二叉树的高度定义为二叉树中层数最
大的叶结点的层数加1
二叉树的深度定义为二叉树中层数最
大的叶结点的层数
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17
4.3 二叉树的抽象数据类型
定义了二叉树的逻辑结构之后，我们需要考虑在二叉树逻辑
结构之上的各种可能运算，这些运算应该适合二叉树的各种
应用 ：
二叉树的某些运算是针对整棵树的
初始化二叉树
合并两棵二叉树
二叉树的大部分运算都是围绕结点进行的
访问某个结点的左子结点、右子结点、父结点
访问结点存储的数据。
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18
4.3 二叉树的抽象数据类型
二叉树结点抽象数据类型BinaryTreeNode是带有
参数 T 的模板，T是存储在结点中的数据类型
每个元素结点都有leftchild()和rightchild()左右子结点
结构
另外每个结点还包含一个数据域value()。
为了强调抽象数据类型与存储无关，我们并没有具
体规定该抽象数据类型的存储方式
4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19
4.3 二叉树的抽象数据类型
template <class T>
class BinaryTreeNode
{//申明二叉树为结点类的友元类，便于访问私有
//数据成员
friend class BinaryTree;
private:
//二叉树结点数据域
T element;
// 实现时，可以补充private的左子结点
//右子结点定义
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20
4.3 二叉树的抽象数据类型
public:
BinaryTreeNode(); //缺省构造函数
BinaryTreeNode(const T& ele);//拷贝构造函数
//给定了结点值和左右子树的构造函数
BinaryTreeNode(const T& ele,
BinaryTreeNode<T>* l,
BinaryTreeNode<T>* r);
T value() const;//返回当前结点的数据
//返回当前结点指向左子树
BinaryTreeNode<T>* leftchild() const;
//返回当前结点指向右子树
BinaryTreeNode<T>* rightchild() const;
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21
4.3 二叉树的抽象数据类型
//设置当前结点的左子树
void setLeftchild(BinaryTreeNode<T>*) ;
//设置当前结点的右子树
void setRightchild(BinaryTreeNode<T>*) ;
//设置当前结点的数据域
void setValue(const T& val);
//判定当前结点是否为叶结点,若是返回true
bool isLeaf() const;
//重载赋值操作符
BinaryTreeNode<T>& operator=
(const BinaryTreeNode<T>& Node);
};
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22
4.3 二叉树的抽象数据类型
二叉树的抽象数据类型的C++定义BinaryTree，没有具体规
定该抽象数据类型的存储方式
template <class T>
class BinaryTree {
private:
//二叉树根结点指针
BinaryTreeNode<T>* root;
//从二叉树的root结点开始
//查找current结点的父结点
BinaryTreeNode<T>*
GetParent(BinaryTreeNode<T>* root,
BinaryTreeNode<T>* current);
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23
4.3 二叉树的抽象数据类型
public:
BinaryTree(root=NULL); //构造函数
~BinaryTree() {DeleteBinaryTree(root);};//析构函数
bool isEmpty() const; //判定二叉树是否为空树
//返回二叉树根结点
BinaryTreeNode<T>* Root(){return root;};
//返回current结点的父结点
BinaryTreeNode<T>* Parent(BinaryTreeNode<T>*
current);
//返回current结点的左兄弟
BinaryTreeNode<T>* LeftSibling(
BinaryTreeNode<T>* current);
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24
4.3 二叉树的抽象数据类型
//返回current结点的右兄弟
BinaryTreeNode<T>* RightSibling(
BinaryTreeNode<T>* current);
// 以elem作为根结点，leftTree作为树的左子树,
//rightTree作为树的右子树，构造一棵新的二叉树
void CreateTree(const T& elem,
BinaryTree<T>& leftTree,
BinaryTree<T>& rightTree);
//前序周游二叉树或其子树
void PreOrder(BinaryTreeNode<T>* root)；
//中序周游二叉树或其子树
void InOrder(BinaryTreeNode<T>* root)；
5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25
4.3 二叉树的抽象数据类型
//后序周游二叉树或其子树
void PostOrder(BinaryTreeNode<T>* root)；
//按层次周游二叉树或其子树
void LevelOrder(BinaryTreeNode<T>* root)；
//删除二叉树或其子树
void DeleteBinaryTree(BinaryTreeNode<T>*
root);
};
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26
4.4 周游二叉树
周游 系统地访问数据结构中的结点。
每个结点都正好被访问到一次。
周游一棵二叉树的过程实际上就是把二
叉树的结点放入一个线性序列的过程，
或者说把二叉树进行线性化
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27
4.4 周游二叉树
二叉树周游
4.4.1 深度优先周游二叉树
4.4.2 非递归深度优先周游二叉树
4.4.3 广度优先周游二叉树
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28
深度优先周游二叉树
我们变换一下根结点的周游顺序，可以得到
以下三种方案：
① 前序周游(tLR次序)：访问根结点；前
序周游左子树；前序周游右子树。
② 中序周游(LtR次序)：中序周游左子
树；访问根结点；中序周游右子树。
③ 后序周游(LRt次序)：后序周游左子
树；后序周游右子树；访问根结点。
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29
深度优先周游二叉树
深度周游如下二叉树
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30
深度优先周游二叉树
深度周游二叉树结果
① 前序周游：ABDCEGFHI
② 中序周游：DBAEGCHFI
③ 后序周游：DBGEHIFCA
- 1
- 2
- 3
- 4
前往页