第6讲树与二叉树.ppt

第6章 树和二叉树 ØØ 树的基本概念树的基本概念 ØØ 二叉树二叉树 ØØ 二叉树遍历二叉树遍历 ØØ 线索二叉树线索二叉树 ØØ 树和森林树和森林 ØØ 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 D是具有相同特性的数据元素的集合。 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root,只有 直接后继，没有直接前驱； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 非线性数据结构、递归的结构 树的类型定义 B A C G D EF H I C G B D EF H I T T1T2 D E F H I T11T12T13 基 本 术 语 结点 结点的度 树的度 叶子结点 分支结点 数据元素+若干指向子树的指针 结点拥有的子树数目 树中所有结点的度的最大值 度为零的结点 度大于零的结点 D D HH I I J J MM 结点的层次 树的深度 A A B B C C D D E E F F GGHH I I J J MMKK L L 假设根结点的层次为1，第l 层的 结点的子树根结点的层次为l+1 树中叶子结点所在的最大 层次 (从根到结点的)路径 孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点 由从根到该结点所 经分支和结点构成 A A B B C C D D E E F F GGHH I I J J MMKK L L 有序树 子树之间存在确定的次序关系 无序树 子树之间不存在确定的次序关系 任何一棵非空树是一个二元组 Tree = （root，F） 其中 root 被称为根结点 F 被称为子树森林 森林森林 是m（m0）棵互 不相交的树的集合 A A rootroot B B C C D D E E F F GGHH I I J J MMKK L L F F 树的基本操作 InitTree 初始化，构建一棵空树。 CreateTree 创建一棵树 Dcestroy 销毁树 Clear 清除树 Locate 定位指定结点 Empty 空树查询 Depth 获取树的深度 Root 定位根结点 GetRoot 读取根元素 GetElem 读取结点的元素值 SetElem 更新结点的元素值 Parent 定位父结点 GetParent 读取父元素 Child 定位结点的孩子 Sibling 定位结点的兄弟 InsertTree 插入子树 DeleteTree 删除子树 Traverse 树遍历 对比树型结构和线性结构 的结构特点 线性结构树型结构 第一个数据元素 (无前驱) 根结点 (无前驱) 最后一个数据元素 (无后继) 多个叶子结点 (无后继) 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继) 二叉树 二叉树或为空树，或是由一个根结点加上两 棵分别称为左子树和右子树的、互不交叉的二 叉树组成 A B C D E F G HK 根结点 左子树 右子树 二叉树的五种基本形态 N 空树只含根结点 NN N L R R 右子树为空树 L 左子树为空树 左右子 树均不 为空树 二叉树 的重要特性 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1； 假设对所有的 j，1 j i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 2i-2 2 = 2i-1 。 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点 （k1）。 证明： 基于上一条性质，深度为 k 的二叉树上的 结点数至多为 20+21+ +2k-1 = 2k-1 。 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结 点、n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。 两类特殊的二叉树： 满二叉树：指的是深度 为k且含有2k-1个结点的 二叉树。 完全二叉树：树中所 含的 n 个结点和满二 叉树中编号为 1 至 n 的结点一一对应。 1 23 4567 89 10 11 12 13 14 15 a bc defg hij 性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。 练习：已知一棵树的度为m，其中有n1个度为1的结点 ，n2个度为2的结点，nm个度为m的结点，问这 棵树有多少个叶子结点？ 假设叶子结点个数为n0个，则树种结点总数为： n0+n1+n2+nm 由性质1得整棵树中结点的个数为： n1+2n2+mnm+1 整理得：n0=n2+2n3+(m-1)nm+1 InitBiTree 初始化，构造一棵空二叉树。 DcestroyBiTree 销毁二叉树 CreateBiTree 构造一棵以指定元素为根的二叉树 Clear 清除二叉树 Empty 查询是否为空二叉树 Size 获取二叉树的规模（结点数） Depth 获取二叉树的深度 GetRoot 读取二叉树根元素的值 SetElem 修改指定元素的值 Locate 定位指定元素 Parent 定位指定元素的父结点 二叉树的主要基本操作 LeftChild 定位指定元素的左孩子 RightChild 定位指定元素的右孩子 LeftSibling 定位指定元素的左兄弟 RightSibling 定位指定元素的右兄弟 GetLeft 读取左孩子 GetRight 读取右孩子 GetParent 读取父元素 InsertLeft 插入左子树 InsertRight 插入右子树 PreOrderTraverse 先序遍历 InOrderTraverse 中序遍历 PostOrderTraverse 后序遍历 二叉树的存储结构 二、二叉树的链 式存储表示 一、二叉树的顺 序存储表示 顺序存储一棵二叉树时，首先对该树中每个结点 进行编号，自顶向下，同一层自左向右连续给结点编 号1,2, n，然后以各结点的编号为下标，把各结点 的值对应存储到一个一维数组中。每个结点的编号与 等深度的满二叉树中对应结点的编号相同。 顺序存储表示顺序存储表示 完全二叉树的数组表示 1. 顺序存储结构 1 2 3 4 56 7 8 91011 891011 2 3 4 567 1 0 1 2 3 4 5 6 7 8 9 10 11 12 A B C DEFG A B C DE G F A B C D E F G 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 4 0 13 2 6 单支树 由于一般二叉树必由于一般二叉树必 须仿照完全二叉树须仿照完全二叉树 那样存储，可能会那样存储，可能会 浪费很多存储空间浪费很多存储空间 ，单支树就是一个，单支树就是一个 极端情况极端情况 链表表示链表表示 最常使用二叉链表作二叉树的存储结构，下面介 绍二叉链表的存储结构 / / 二叉树结点类模板二叉树结点类模板 template structstruct BinTreeNodeBinTreeNode / / 数据成员数据成员: : ElemTypeElemType data; data; / / 数据域数据域 BinTreeNodeBinTreeNode * *leftChildleftChild; ;/ / 左孩子左孩子 BinTreeNodeBinTreeNode * *rightChildrightChild; ;/ / 右孩子右孩子 ; ; / / 二叉树类模板二叉树类模板 template class class BinaryTreeBinaryTree protected:protected: / / 二叉树的数据成员二叉树的数据成员: : BinTreeNodeBinTreeNode *root; *root; intint size; / size; /结点个数结点个数 public:public: ； 练习： 1.n个结点的二叉树的链接存储结构中，有多少 个指针域为空，多少个不空？ 不空：n-1 空指针域：2n-(n-1)=n+1 二叉树遍历二叉树遍历 (Binary Tree Traversal)(Binary Tree Traversal) 顺着某一条搜索路径巡访二叉树中的结点，使 得每个结点均被访问一次，而且仅被访问一次 问题的提出 “访问”的含义可以很广，如：输出结点的信息等 “遍历”是任何类型均有的操作，对线性 结构而言，只有一条搜索路径(因为每个结点 均只有一个后继)，故不需要另加讨论。而二 叉树是非线性结构，每个结点有两个后继，则 存在如何遍历即按什么样的搜索路径遍历的问 题 对“二叉树”而言，可以有三条搜索路径 1先上后下的按层次遍历 2先左（子树）后右（子树）的遍历 3先右（子树）后左（子树）的遍历 设 访问根结点 记作 D 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有 前序前序 DLR DLR 逆前序逆前序 DRLDRL 中序中序 LDR LDR 逆中序逆中序 RDLRDL 后序后序 LRD LRD 逆后序逆后序 RLDRLD 层次遍历层次遍历 前序遍历前序遍历 (Preorder Traversal)(Preorder Traversal) 若二叉树为空，则空操作若二叉树为空，则空操作 否则否则 访问根结点访问根结点(D)(D) 前序遍历左子树前序遍历左子树(L)(L) 前序遍历右子树前序遍历右子树(R)(R) 遍历结果遍历结果 - +- + a a * * b b - - c dc d / / e fe f 若二叉树为空，则空操作若二叉树为空，则空操作 否则否则 中序遍历左子树中序遍历左子树(L)(L) 访问根结点访问根结点(D)(D) 中序遍历右子树中序遍历右子树(R)(R) 遍历结果遍历结果 a a + + b b * * c c - - d d - - e e / / f f 中序遍历中序遍历 ( (InorderInorder Traversal) Traversal) 表达式语法树表达式语法树 后序遍历后序遍历 ( (PostorderPostorder Traversal) Traversal) 若二叉树为空，则空操作若二叉树为空，则空操作 否则否则 后序遍历左子树后序遍历左子树(L)(L) 后序遍历右子树后序遍历右子树(R)(R) 访问根结点访问根结点(D)(D) 遍历结果遍历结果 a b c da b c d - * +- * + e fe f / / - - 层次遍历层次遍历( (LevelorderLevelorder Traversal) Traversal) 从上到下，从左到右从上到下，从左到右 遍历结果遍历结果 - - a a* * e fe f b b - -cdcd 25 16 830 32 37 48 6028 352629 中序遍历 8 16 25 26 28 29 30 32 35 37 48 60 前序遍历 25 16 8 37 30 28 26 29 32 35 48 60 后序遍历 8 16 26 29 28 35 32 30 60 48 37 25 由遍历序列生成二叉树由遍历序列生成二叉树 由二叉树的 由二叉树的前序前序序列和序列和中序中序序列序列可以可以唯一地确唯一地确 定一棵二叉树定一棵二叉树 由二叉树的 由二叉树的后序后序序列和序列和中序中序序列序列可以可以唯一地确唯一地确 定一棵二叉树定一棵二叉树 由二叉树的 由二叉树的前序前序序列和序列和后序后序序列序列不可不可唯一地确唯一地确 定一棵二叉树定一棵二叉树 仅知二叉树的先序序列“abcdefg” 不能唯一确定 一棵二叉树， 由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”，则 会如何？ 二叉树的先序序列 二叉树的中序序列左子树 左子树右子树 右子树 根 根 a b c d e f g c b d a e g f a a b b c c d d e e f f g g a b cd e f g 先序序列 中序序列 练习： 1.一棵二叉数的前序遍历序列为AEFBGCDHIKJ， 中序遍历序列为EFAGBCHKIJD，请写出后序遍历 序列 A EFBGCDHIKJ A E FCDHIKJ B G A EB GFC DHIKJ A EB GFC D HIKJ A E FCDHIKJ B G 前序遍历序列为 AEFBGCDHIKJ 中序遍历序列为 EFAGBCHKIJD A EB GFC D H IKJ K A EB GFC D H I K 后序序列：FEGKJIHDCBA A EB GFC D HIKJ 前序 AEFBGCDHIKJ 中序 EFAGBCHKIJD 2.一棵二叉数的中序遍历序列为icdbaefghj， 后序遍历序列为idcbgfjhea，请写出前序遍历 序列 a be h d c i fj g 前序序列：abcidehfgj 1. 1.先序遍历先序遍历 template void void BinaryTreeBinaryTree:PreOrderHelpPreOrderHelp( ( BinTreeNodeBinTreeNode *r) *r) / / 先序遍历以先序遍历以r r为根的二叉树为根的二叉树,private,private if (r != NULL) if (r != NULL) coutcoutdatadata-leftChildleftChild); );/ / 遍历左子树遍历左子树 PreOrderHelp(rPreOrderHelp(r-rightChildrightChild); ); / / 遍历右子树遍历右子树 遍历算法遍历算法 1. 1.先序遍历先序遍历 template void void BinaryTreeBinaryTree:PreOrderPreOrder() () / / 先序遍历二叉树先序遍历二叉树,public,public PreOrderHelp(rootPreOrderHelp(root); ); 遍历算法遍历算法 2. 2.中序遍历中序遍历 template void void BinaryTreeBinaryTree:InOrderHelpInOrderHelp( ( BinTreeNodeBinTreeNode *r) *r) / / 中序遍历以中序遍历以r r为根的二叉树为根的二叉树,private,private if (r != NULL) if (r != NULL) InOrderHelp(rInOrderHelp(r-leftChildleftChild); );/ / 遍历左子树遍历左子树 coutcoutdatadata-rightChildrightChild); ); / / 遍历右子树遍历右子树 遍历算法遍历算法 2. 2.中序遍历中序遍历 template void void BinaryTreeBinaryTree:InOrderInOrder() () / / 中序遍历二叉树中序遍历二叉树,public,public InOrderHelp(rootInOrderHelp(root); ); 遍历算法遍历算法 模拟算法对如图所示二叉树的中序遍历的执行过程。 A DC B FE G H inorder() inorder(A) inorder(B)Ainorder(G) inorder(C)Binorder(D) inorder(H)G inorder() inorder()Cinorder() inorder(E)inorder(F)D inorder()H inorder()Einorder()inorder()Finorder() 输出序列 CBEDFAHG 3. 3.后序遍历后序遍历 template void void BinaryTreeBinaryTree:PostOrderHelpPostOrderHelp( ( BinTreeNodeBinTreeNode *r) *r) / / 后序遍历以后序遍历以r r为根的二叉树为根的二叉树,private,private if (r != NULL) if (r != NULL) PostOrderHelp(rPostOrderHelp(r-leftChildleftChild); );/ / 遍历左子树遍历左子树 PostOrderHelp(rPostOrderHelp(r-rightChildrightChild); ); / / 遍历右子树遍历右子树 coutcoutdatadata void void BinaryTreeBinaryTree:PostOrderPostOrder() () / / 后序遍历二叉树后序遍历二叉树,public,public PostOrderHelp(rootPostOrderHelp(root); ); 遍历算法遍历算法 template void void BinaryTreeBinaryTree:LevelOrderLevelOrder() () / / 层次遍历二叉树层次遍历二叉树 LinkQueueLinkQueue * q; * q;/ / 队列队列 BinTreeNodeBinTreeNode *t = root; *t = root;/ / 根根 if (t != NULL) if (t != NULL) q.InQueue(tq.InQueue(t); ); / / 如果根非空如果根非空, ,则入队则入队 while (!while (!q.Emptyq.Empty()() / q/ q非空非空, ,说明还有结点未访问说明还有结点未访问 q.OutQueue(tq.OutQueue(t); ); coutcoutdatadataif (t-leftChildleftChild != NULL) != NULL)/ / 左孩子非空左孩子非空 q.InQueue(tq.InQueue(t-leftChildleftChild); );/ / 左孩子入队左孩子入队 if (t-if (t-rightChildrightChild != NULL) != NULL)/ / 右孩子非空右孩子非空 q.InQueue(tq.InQueue(t-rightChildrightChild); );/ / 右孩子入队右孩子入队 4. 4.按层遍历按层遍历 template void BinaryTree:InitBiTree( ) /初始化，构造一棵空二叉树。 root=NULL; size=0 ; 二叉树算法实现二叉树算法实现 1. void InitBiTree( ) 2.void CreatBiTree() template void BinaryTree: CreatBiTree() /交互式创建一棵二叉树 BinTreeNode* r; ElemType end, empty, x; coutend; coutempty; coutx; r=new BinTreeNode; r-data=x; r-leftChild=r-rightChild=NULL; root=r ; size+; creat(r, 0, empty ,end); /创建根结点的左子树 creat(r, 1, empty ,end); /创建根结点的右子树 template /递归创建子树 Void BinaryTree: Creat( BinTreeNode *r, int flag, ElemType empty, ElemType end) BinTreeNode *p; ElemType x; cinx; if(x!=end p-data=x; p-leftChild= p- rightChild=NULL; if(flag=0) r-leftChild=p; /p为左子树 else r-rightChild=p; /p为右子树 size+; creat(p, 0, empty ,end); /递归创建左子树 creat(p, 1, empty ,end); /递归创建右子树 3.BinTreeNode *GetRoot() template BinTreeNode*BinaryTree: GetRoot() / 操作结果：返回二叉树的根 return root; 4.int Locate(ElemType e) 功能：查找元素值为e的结点。 该算法可直接调用先序遍历算法。也可以利用先 序遍历思想设计如下： template BinTreeNode*BinaryTree: Locate(BinTreeNode *r, ElemType e) /private if(r=NULL) return NULL ; /该子树为空 if(r-data=e) return r ; BinTreeNode *p=Locate(r-leftChild, e); if (p=NULL) p=Locate(r-RightChild, e); return p; template int BinaryTree:Locate(ElemType e) /public if (Locate(root, e)=NULL) return FALSE; else return TRUE; 5.int GetLeft(ElemType e, ElemType if (ep=NULL) return NULL ; /找不到结点e if(ep-leftChild=NULL) /e无左孩子 return NULL; return ep-leftChild ; /返回e左孩子的指针 template int BinaryTree: GetLeft(ElemType e, ElemType if (p=NULL) return FALSE ; /e无左孩子 c=p-data; return TRUE; template BinTreeNode* BinaryTree: Parent(BinTreeNode*r, ElemType e) /定位指定元素的父结点，private BinTreeNode* p; if(r=NULL)return NULL ; if(r-leftChild!=NULL /r是e的父结点，返回结点r的指针 p=Parent(r-leftChild, e) /递归调用r的左子树 if (p=NULL) p=Parent(r-rightChild, e); return p; 6.int GetParent(ElemType e, ElemType BinTreeNode *p=Parent(root, e); if (p=NULL)return FALSE; /树中无元素e f=p-data ; return TRUE ; 7.int GetLeftSibling(ElemType e, ElemType BinTreeNode *p=Parent(root, e); if (p=NULL)return NULL ; /无e结点 if(p-leftChild-data=e) /e是其父亲的左孩子 return NULL; return p-leftChild; /返回e的左兄弟指针 template int BinaryTree: GetLeftSibling(ElemType e, ElemType /根结点无兄弟 BinTreeNode *p=LeftSibling(e); if (p=NULL)return FALSE; /e无左兄弟 s=p-data; return TRUE; 8.int InsertChild(ElemType e, ElemType x,ElemType y) template int BinaryTree: InsertChild(ElemType e,ElemType x,ElemType y) /为指定元素 e 插入左、右孩子 BinTreeNode *ep, *xp, *yp; ep=Locate(root, e) ; /定位元素e if (ep=NULL) return FALSE ; /找不到元素e xp=new BinTreeNode ; xp-data=x; xp-rightChild=NULL; yp=new BinTreeNode ; yp-data=y; yp-leftChild=NULL; xp-leftChild=ep-leftChild; ep-leftChild=xp; /结点x置为结点e的左孩子 yp-rightChild=ep-rightChild; ep-rightChild=yp; /结点y置为结点e的右孩子 size=size+2; return TRUE ; 9.int SetElem(ElemType e, ElemType x) template int BinaryTree: SetElem(ElemType e, ElemType x) /更新指定元素 BinTreeNode *p=Locate(root, e); if (p=NULL)return FALSE; p-data=x ; return TRUE ; 10.int Size( ):获取二叉树的结点个数 方法一：如果类中设置有数据成员size template int BinaryTree: Size( ) /public return size ; 方法二：如果类中未设置数据成员size template int BinaryTree: Size( ) /public return Size(root); template int BinaryTree: Size(BinTreeNode *r) /private if(r=NULL)return 0; else return Size(r-leftChild)+Size(r-rightChild)+1; /二叉树的结点总数为左右子树的结点数之和加1 11.int Depth( ) ：获取二叉树的深度 template int BinaryTree: Depth( ) /public return Depth(root); template int BinaryTree: Depth(BinTreeNode *r) /private if(r=NULL)return 0; else int leftD, rightD; leftD=Depth(r-leftChild); rightD=Depth(r-rightChild); return 1+(leftDrightD?leftD:rightD); /二叉树的深度为左右子树的深度的最大值加1 12.int Leaf( ) ：统计并返回叶子结点个数 template int BinaryTree: Leaf( ) /public return Leaf( root ); template int BinaryTree: Leaf(BinTreeNode *r) /private if(r=NULL)return 0; if(r-leftChild=NULL return Leaf(r-leftChild)+Leaf(r-rightChild); /递归遍历左子树和右子树 template void BinaryTree: Clear(BinTreeNode *r) /private if(r!=NULL) /后序递归 Clear(r-leftChild); Clear(r-rightChild); delete r; size-; 13.void Clear(BiNode *r) ：清除指定根结点的二叉 树 14.void DestoryBiTree() ：销毁二叉树 template void BinaryTree: DestoryBiTree() Clear(root); root=NULL: