1第第4章章 树与二叉树树与二叉树4.1 树的定义和相关术语树的定义和相关术语4.2 二叉树二叉树4.3 树与森林树与森林4.4 森林与二叉树的关系森林与二叉树的关系4.5 Huffman树与编码树与编码2内蒙古大学内蒙古大学理工学院理工学院计算机学院计算机学院生命科学学院生命科学学院外国语学院外国语学院人文学院人文学院数数学学系系物物理理系系电电子子系系计计算算机机系系计计算算中中心心网网络络中中心心汉汉语语系系历历史史系系哲哲学学系系生生物物系系环环境境系系动动物物中中心心生生物物工工程程中中心心资资源源所所英英语语系系日日语语系系 行政机构行政机构树形结构是一种非线性结构，应用十分广泛。树形结构是一种非线性结构，应用十分广泛。如：行政机构、磁盘目录、家谱等如：行政机构、磁盘目录、家谱等3磁磁 盘盘 目目 录录4的定义和基本术语的定义和基本术语5例例5.1: Tree=(D, R)D=Book, C1, C2, C3, S1.1, S1.2, S2.1, S2.2, S2.3, S2.1.1, S2.1.2 R=, , , , , , , , , Book C1 C2 C3 S1.1 S1.2 S2.1 S2.2 S2.3 S2.1.1 S2.1.2 ChapterSectionSectionv树是一种层次结构树是一种层次结构 （hierarchy structure）6v基本术语：基本术语：主要来源于家谱和树主要来源于家谱和树双亲、子女（双亲、子女（parent, child）：）：若若 R，则称，则称a是是b的双亲，的双亲，b是是a 的子女的子女(孩子孩子);结点度（结点度（degree）：结点所拥有的子女数；结点所拥有的子女数；叶（叶（leaf）：度为度为0的结点；的结点；分枝结点（分枝结点（branch node）：度大于度大于0的结点；的结点；树的度树的度：树中最大的结点度；：树中最大的结点度；ABCDEFGHIJMKL7结点所在的层次（结点所在的层次（level）：根在第根在第1层，其它任一结点所在的层是其双亲的层加层，其它任一结点所在的层是其双亲的层加1；深度或高（深度或高（depth）：结点所在的层次的最大层数；结点所在的层次的最大层数；兄弟（兄弟（sibling)：具有同一双亲的结点互称兄弟；具有同一双亲的结点互称兄弟；堂兄弟（堂兄弟（cousin）：双亲在同层的双亲在同层的非兄弟结点非兄弟结点互称堂兄弟；互称堂兄弟；423ABCDEFGHIJMKL18ABCACB无序有序祖先、子孙（祖先、子孙（ancestor）：一个结点是它所有子树中的结点的祖先一个结点是它所有子树中的结点的祖先,这些结点是它的子孙这些结点是它的子孙;路径（路径（path）：）：是一结点序列是一结点序列n1,n2,n3,nk，并且前并且前1个结点是后个结点是后1个结个结点的双亲；它的长度是点的双亲；它的长度是k-1;有序树（有序树（ordered tree）：）：每个结点的子女由左到右是有次序的；否则是无序树；每个结点的子女由左到右是有次序的；否则是无序树；423ABCDEFG H IJMKL19ABCDEFGHIJKLM结点结点A、B、C的度分别为：的度分别为：3、2、1叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：0结点结点M的层次：的层次：3树的深度：树的深度：3结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先10v森林（森林（Forest）: m(m 0)棵互不相交的树的集合棵互不相交的树的集合.ArootBCDEFGHIJMKLF1112ABCDEFGHK根结点左子树左子树右子树右子树1314二叉树的二叉树的ADT定义定义 :ADT BinaryTree is Data 是有限个结点的集合是有限个结点的集合D。当。当D非空时，其中非空时，其中 有一根结点有一根结点t，其余结点被分为，其余结点被分为t的左子树和的左子树和 右子树。右子树。 Operations Constructor Process: 建立一棵空二叉树建立一棵空二叉树 Delete Process: 删除二叉树删除二叉树15 IsEmpty Process: 判断二叉树是否是空判断二叉树是否是空 Output: 若二叉树为空，则返回若二叉树为空，则返回true, 否则返回否则返回false Size Process: 计算二叉树的结点数计算二叉树的结点数size Output: size Height Process: 计算二叉树的高度计算二叉树的高度height Output: height Root Process: 取二叉树根结点值取二叉树根结点值x Output: 根结点值根结点值x16Parent Input: node是二叉树中的一个结点是二叉树中的一个结点 Process: 求求node的双亲的双亲p，若，若node 是根，则是根，则p为空为空 Output: p CreateBinaryTree Input: 二叉树的某种形式的定义二叉树的某种形式的定义definition Process: 根据此定义根据此定义definition构造二叉树构造二叉树 MakeTree Input: data是根结点值，是根结点值，left是左子树，是左子树，right是右子树是右子树 Process: 创建二叉树，创建二叉树，data是根结点值，是根结点值，left是其左子树，是其左子树， right是其右子树是其右子树17 BreakTree Process: 拆分二叉树，拆分二叉树，data是根结点数据，是根结点数据，left是左子树，是左子树， right是右子树是右子树 Output: data, left, right PreOrder Input: Visit()是结点访问函数是结点访问函数 Process: 按前序遍历对二叉树中每个结点调用按前序遍历对二叉树中每个结点调用Visit( )1次且仅次且仅1次次 Output: 根据根据Visit( )，按前序遍历序列得到结果，按前序遍历序列得到结果 InOrder Input: Visit()是结点访问函数是结点访问函数 Process: 按中序遍历对二叉树中每个结点调用按中序遍历对二叉树中每个结点调用Visit( ) 1次且仅次且仅1次次 Output: 根据根据Visit( )，按中序遍历序列得到结果，按中序遍历序列得到结果18 PostOrder Input: Visit()是结点访问函数是结点访问函数 Process: 按后序遍历次序对二叉树中每个结点调用按后序遍历次序对二叉树中每个结点调用Visit( ) 1次且次且 仅仅1次次 Output: 根据根据Visit( )，按后序遍历序列得到结果，按后序遍历序列得到结果 LevelOrder Input: Visit()是结点访问函数是结点访问函数 Process: 按层次对二叉树中每个结点调用按层次对二叉树中每个结点调用Visit( )1次且仅次且仅1次次 Output: 根据根据Visit( )，按层次遍历序列得到结果，按层次遍历序列得到结果/ BinaryTree 转转19编号完全二叉树的数组表示编号完全二叉树的数组表示 一般二叉树的数组表示一般二叉树的数组表示20 单分支树单分支树2122例：例：2324例：例：25二叉链表中结点定义如下：二叉链表中结点定义如下：class BinaryTreeNode DataType data; BinaryTreeNode *leftChild, *rightChild; /左指针左指针,右指针右指针 public : BinaryTreeNode(DataType &e, BinaryTreeNode *l=NULL,BinaryTreeNode *r=NULL) data = e; leftChild =l; rightChild = r; ;/BinaryTreeNode 26class BinaryTree BinaryTreeNode *root; /根结点指针根结点指针 public : BinaryTree( ) root = NULL; /创建一个空的二叉树创建一个空的二叉树 bool IsEmpty( ); /如果二叉树为空，则返回如果二叉树为空，则返回true，否则返回，否则返回false bool Root(DataType &x); /置置x为根结点值；若操作失败，则返回为根结点值；若操作失败，则返回false，否则返回，否则返回true void CreateBinaryTree(BinaryTreeNode *&t=root); /通过扩充二叉树的前序遍历序列，创建二叉树通过扩充二叉树的前序遍历序列，创建二叉树二叉链表定义如下：二叉链表定义如下：27void MakeTree(DataType &data，BinaryTree &left，BinaryTree &right);/创建二叉树，创建二叉树，data为根结点值，为根结点值，left作为左子树，作为左子树，right作为右子树作为右子树void BreakTree(DataType &data，BinaryTree &left，BinaryTree &right); /拆分二叉树拆分二叉树void PreOrder(void Visit(BinaryTreeNode *&), BinaryTreeNode *&=root);void InOrder(void Visit(BinaryTreeNode *&), BinaryTreeNode *&=root); void PostOrder(void Visit(BinaryTreeNode *&), BinaryTreeNode *&=root); void LevelOrder(void Visit(BinaryTreeNode *&); /逐层遍历逐层遍历/其中，其中，Visit作为遍历的过程参数，负责对结点的访问。作为遍历的过程参数，负责对结点的访问。28void Delete(BinaryTreeNode *&=root); /删除一棵二叉树，释放其结点。删除一棵二叉树，释放其结点。int Size(BinaryTreeNode *&=root);/返回二叉树中结点数。返回二叉树中结点数。int Height(BinaryTreeNode *&=root); /返回二叉树的高度。返回二叉树的高度。;/BinaryTree基本操作的实现：基本操作的实现：bool IsEmpty( ) /如果二叉树为空，则返回如果二叉树为空，则返回true，否则返回，否则返回false return (root? true:false); 29bool Root(DataType &x) /置置x为根结点值，如果没有根结点，则返回为根结点值，如果没有根结点，则返回false if (root) root-data= x; return true; return false; / 没有根结点没有根结点void MakeTree(DataType &data, BinaryTree &left, BinaryTree &right) /用用left, right和和data构成一棵新树，构成一棵新树，left, right与当前二叉树必须与当前二叉树必须是不同的对象是不同的对象 root=new BinaryTreeNode(data, left.root, right.root); /创建新二叉树创建新二叉树 3031VLR123一、一、递归算法递归算法VRLRVLRLVVLRLVRLRV规定规定:先左后右遍历先左后右遍