1. 第 6 章 树和二叉树
?6.1 树及其抽象数据类型
?6.2 二叉树及其抽象数据类型
?6.3 二叉树的表示和实现
?6.4 线索二叉树
?6.5 Huffman编码与Huffman树
?6.6 树的表示和实现
本章是数据结构课程的重中之重，也是难
点所在，表现为二叉链表存储结构和递归算
法相结合。链式存储结构和递归算法本身就
是两个难 点，建立二叉树需要将它们
3. 《数据结构（ Java 版）（第 3 版）》
6.1 树及其抽象数据类型
6.1.1 树定义 6.1.2 树的术
语
6.1.3 树的表示法 6.1.4 树抽象数
据类型
4. 《数据结构（ Java 版）（第 3 版）》
6.1.1 树定义
树（ tree ）是由 n （ n≥0 ）个结点组
成的有限集合。 n=0 的树称为空树； n>0
的树 T ：
?根（ root ）结点，它没有前驱结点。
?其他结点分为 m 棵互不相交的子树。
5. 《数据结构（ Java 版）（第 3 版）》
6.1.2 树的术语
1. 父母、孩子与兄弟结点
2. 度
3. 结点层次、树的高度
4. 边、路径
5. 无序树、有序树
6. 森林
6. 《数据结构（ Java 版）（第 3 版）》
6.1.3 树的表示法
1. 图示法
2. 横向凹入表示法
A
B
E
F
C
G
D
H
I
J
3. 广义表表示
A(B(E, F), C(G), D(H, I,
J))
7. 《数据结构（ Java 版）（第 3 版）》
6.1.4 树抽象数据类
型
public interface TTree<T> // 树接口
{ boolean isEmpty(); // 判断是否空树
TreeNode<T> getChild(TreeNode<T> p,int i);// 返回 p 第 i 个孩
子
TreeNode<T> getParent(TreeNode<T> node);// 返回 node 的父
母
int count(); // 树的结点个数
int height(); // 树的高度
TreeNode<T> search(T x); // 查找并返回元素为 x 的
结点
void preOrder(); // 先根次序遍历树
void postOrder(); // 后根次序遍历树
void levelOrder(); // 按层次遍历树
void insertRoot(T x); // 插入元素 x 作为根结
8. 《数据结构（ Java 版）（第 3 版）》
6.2 二叉树及其抽象数据类型
6.2.1 二叉树定义
6.2.2 二叉树性质
6.2.3 二叉树的遍历
6.2.4 二叉树抽象数据类型
9. 《数据结构（ Java 版）（第 3 版）》
6.2.1 二叉树定义
二叉树（ binary tree ）是 n 个结点的有限
集合：
? 空二叉树；
? 由一个根结点、两棵互不相交的左子树和
右子树组成。
10. 《数据结构（ Java 版）（第 3 版）》
6.2.2 二叉树性质
性质 1 ：若根结点的层次为 1 ，则二叉树
第 i 层最多有 2i
?1 （ i≥1 ）个结点。
性质 2 ：在高度为 k 的二叉树中，最多有
2k
?1 个结点（ k≥0 ）。
性质 3 ：设一棵二叉树的叶子结点数为
n0 ， 2 度结点数为 n2 ，则 n0=n2+1 。
11. 《数据结构（ Java 版）（第 3 版）》
性质 4 ： n 个结点完全二叉树的高度是
。
性质 5 ：一棵具有 n 个结点的完全二叉树，对序号为
i （ 0≤i<n ）的结点，有：
a. 若 i=0 ，则 i 为根结点，无父母结点；若 i >0 ，则 i 的父
母结点序号为。
b. 若 2i+1<n ，则 i 的左孩子结点序号为 2i+1 ；否则 i 无
左孩子。
c. 若 2i+2<n ，则 i 的右孩子结点序号为 2i+2 ；否则 i 无
? ? 1log2 += nk
12. 《数据结构（ Java 版）（第 3 版）》
6.2.3 二叉树的遍历
先根次序：访问根结点，遍历左子树，遍历右子树
。
中根次序：遍历左子树，访问根结点，遍历右子树
。
后根次序：遍历左子树，遍历右子树，访问根结点
。
13. 《数据结构（ Java 版）（第 3 版）》
6.2.4 二叉树抽象数据类型
public interface BinaryTTree<T>
{ boolean isEmpty(); // 判断是否空
int count(); // 返回结点个数
int height(); // 返回高度
void preOrder(); // 先根次序遍历
void inOrder(); // 中根次序遍历
void postOrder(); // 后根次序遍历
void levelOrder(); // 按层次遍历
BinaryNode<T> search(T key); // 查找
BinaryNode<T> getParent(BinaryNode<T> node);// 返回父母
void insertRoot(T x); // 插入元素 x 作为根结点
BinaryNode<T> insertChild(BinaryNode<T> p, T x, boolean
leftChild);
void removeChild(BinaryNode<T> p, boolean leftChild);
void removeAll(); }
14. 《数据结构（ Java 版）（第 3 版）》
6.3 二叉树的表示和实现
6.3.1 二叉树的存储结构
6.3.2 二叉树的二叉链表实现
6.3.3 三叉树的二叉链表实现
17. 《数据结构（ Java 版）（第 3 版）》
6.3.2 二叉树的二叉链表实现
1. 二叉树的二叉链表结点类
public class BinaryNode<T>
{ T data; // 数据元素
BinaryNode<T> left, right; // 左、右孩子
}
2. 二叉树类
public class BinaryTree<T> implements
BinaryTTree<T>
{ BinaryNode<T> root; // 根结点 }
18. 《数据结构（ Java 版）（第 3 版）》
3. 二叉树三种次序遍历的递归算
法
// 先根次序遍历以 p 结点为根的子树
private void preOrder(BinaryNode<T> p)
{ if (p!=null) // 若二叉树不空
{ System.out.print(p.data+" "); // 访问当前
结点
preOrder(p.left); // 按先根次序遍历左子树
preOrder(p.right); // 按先根次序遍历右子树
}
}
23. 《数据结构（ Java 版）（第 3 版）》
（ 4 ）以完全二叉树的层次遍历
序列构造链式存储结构的完全二
叉树
【例 6.3 】 建立二叉链表表示的完全二叉树
。
27. 《数据结构（ Java 版）（第 3 版）》
6.3.3 三叉树的二叉链表
实现
1. 二叉树的三叉链表结点类
public class TriNode<T>
{ public T data; // 数据
域
public TriNode<T> parent, left,
right; // 父母结
点、左和右孩子结点
28. 《数据结构（ Java 版）（第 3 版）》
2. 三叉链表表示的二叉树类
public class TriBinaryTree<T>
{
public TriNode<T> root; // 根结
点
}
（ 1 ）构造二叉树
30. 《数据结构（ Java 版）（第 3 版）》
6.4 线索二叉树
6.4.1 线索二叉树定义
0 left???ò ×ó??×?
ltag
1 left ?? ? ??÷ ?? ???ò ?°???á??C
??
= ?
??
0 right
rtag
1 right ?? ? ??÷ ?? ???ò ?ó ???á??C
?
= ?
?
31. 《数据结构（ Java 版）（第 3 版）》
6.4.2 中序线索二叉树
1. 二叉树的中序线索化
2. 中序线索二叉树类
3. 中根次序遍历中序线索二叉树
【例 6.5 】 构造中序线索二叉树并进行中根次
序遍历。
4. 先根次序遍历中序线索二叉树
5. 后根次序遍历中序线索二叉树
33. 《数据结构（ Java 版）（第 3 版）》
2. 中序线索二叉树类
public class ThreadBinaryTree<T>
{
public ThreadNode<T> root;
}
3. 中根次序遍历中序线索二叉树
36. 《数据结构（ Java 版）（第 3 版）》
6.5 Huffman 编码与 Huffman
树 6.5.1 Huffman 编码
存储“ AAAABBBCDDBBAAA” ，字符集
[A 、 B 、 D 、 C] ，字符出现次数为
7 、 5 、 2 、 1 ，频率为 0.47 、 0.33 、 0.13 、
0.07 ，哈夫曼编码过程为：
A A A A B B B C D D B B A A A
0 0 0 0 10 10 10 111 110 110 10 10 0 0 0
42. 《数据结构（ Java 版）（第 3 版）》
例 6.6 构造 Huffman 树并获得
Huffman 编码。<1> 采用静态三叉链表存储 Huffman
树
43. 《数据结构（ Java 版）（第 3 版）》
图 6-44 Huffman 树和 Huffman
编码
若权值集合 {5,29,7,8,14,23,3,11} 对应字
符 A ～ H
46. 《数据结构（ Java 版）（第 3 版）》
6.6.1 树的遍历
1. 树的先根遍历算法描述如下：
a. 访问根结点。
b. 按照从左到右的次序先根遍历根的每一棵子
树。
2. 树的后根遍历算法描述如下：
a. 按照从左到右的次序后根遍历根的每一棵子
树。
b. 访问根结点。
48. 《数据结构（ Java 版）（第 3 版）》
6.3.3 树的孩子兄弟链表
实现
1. 树的孩子兄弟链表结点类
public class TreeNode<T>
{
public T data; // 数据域
public TreeNode<T> child,
sibling;
// 孩子、兄弟结点
}
49. 《数据结构（ Java 版）（第 3 版）》
2. 树类声明
public class Tree<T> implements
TTree<T>
{
public TreeNode<T> root; // 根结
点
}
3. 树的遍历
4. 返回结点
a. 返回最后一个兄弟结点
52. 《数据结构（ Java 版）（第 3 版）》
7. 树的广义表表示
例 6.9 树的广义表表示及构造。
中国 ( 北京 , 上海 , 江苏 ( 南京 , 苏州 ,
无锡 ), 浙江 ( 杭州 , 宁波 , 温州 ), 广
东 ( 广州 )), 韩国 ( 首尔 ), 美国 ( 华
盛顿 )
![《数据结构（ Java 版）（第 3 版）》
6.5 Huffman 编码与 Huffman
树 6.5.1 Huffman 编码
存储“ AAAABBBCDDBBAAA” ，字符集
[A 、 B 、 D 、 C] ，字符出现次数为
7 、 5 、 2 、 1 ，频率为 0.47 、 0.33 、 0.13 、
0.07 ，哈夫曼编码过程为：
A A A A B B B C D D B B A A A
0 0 0 0 10 10 10 111 110 110 10 10 0 0 0](https://image.slidesharecdn.com/06java-130822184926-phpapp01/85/06-java-36-320.jpg)
