第06章 数据结构 树和二叉树(Java版)第三版.ppt

第6章 树和二叉树 6.1 树及其抽象数据类型 6.2 二叉树及其抽象数据类型 6.3 二叉树的表示和实现 6.4 线索二叉树 6.5 Huffman编码与Huffman树 6.6 树的表示和实现 本章是数据结构课程的重中之重，也是难点所在，表现为二叉链表存储结构和递归算法相结合。链式存储结构和递归算法本身就是两个难 点，建立二叉树需要将它们有机结合。 目的和要求 目的：理解树型结构；掌握链式存储结构表达 非线性结构，掌握递归算法设计。 内容：二叉树的定义、性质、存储结构，二叉链 表表示的二叉树类；中序线索二叉树； Huffman树；树的定义、存储结构和实现。 要求：理解树和二叉树概念，掌握树和二叉树的 表示和实现，掌握递归算法设计。 重点：二叉链表表示的二叉树类；Huffman树；树 的定义、存储结构和构造算法。 难点：链式存储结构表达非线性结构；递归算法 设计。 实验：树和二叉树的基本操作，链式存储结 构表示树和二叉树；递归算法。 6.1 树及其抽象数据类型 6.1.1 树定义 6.1.2 树的术语 6.1.3 树的表示法 6.1.4 树抽象数据类型 6.1.1 树定义 树（tree）是由n（n≥0）个结点组成的有限集合。n=0的树称为空树；n0的树T： 根（root）结点，它没有前驱结点。 其他结点分为m棵互不相交的子树。 6.1.2 树的术语 父母、孩子与兄弟结点 度 结点层次、树的高度 边、路径 无序树、有序树 森林 6.1.3 树的表示法 图示法 横向凹入表示法 A B E F C G D H I J 6.1.4 树抽象数据类型 public interface TTreeT //树接口 { boolean isEmpty(); //判断是否空树 TreeNodeT getChild(TreeNodeT p,int i);//返回p第i个孩子 TreeNodeT getParent(TreeNodeT node);//返回node的父母 int count(); //树的结点个数 int height(); //树的高度 TreeNodeT search(T x); //查找并返回元素为x的结点 void preOrder(); //先根次序遍历树 void postOrder(); //后根次序遍历树 void levelOrder(); //按层次遍历树 void insertRoot(T x); //插入元素x作为根结点 TreeNodeT insertChild(TreeNodeT p,T x,int i);//插入孩子 void removeChild(TreeNodeT p, int i); //删除孩子 } 6.2 二叉树及其抽象数据类型 6.2.1 二叉树定义 6.2.2 二叉树性质 6.2.3 二叉树的遍历 6.2.4 二叉树抽象数据类型 6.2.1 二叉树定义 二叉树（binary tree）是n个结点的有限集合： 空二叉树； 由一个根结点、两棵互不相交的左子树和右子树组成。 6.2.2 二叉树性质 性质1：若根结点的层次为1，则二叉树第i层最多有2i?1（i≥1）个结点。 性质2：在高度为k的二叉树中，最多有2k?1个结点（k≥0）。 性质3：设一棵二叉树的叶子结点数为n0，2度结点数为n2，则n0=n2+1。 性质4：n个结点完全二叉树的高度是 。 性质5：一棵具有n个结点的完全二叉树，对序号为i（0≤in）的结点，有： 若i=0，则i为根结点，无父母结点；若i 0，则i的父母结点序号为。 若2i+1n，则i的左孩子结点序号为2i+1；否则i无左孩子。 若2i+2n，则i的右孩子结点序号为2i+2；否则i无右孩子