《讲树与叉树》PPT课件.ppt

第6章 树和 二叉树,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。,树的类型定义,基 本 术 语,结点,结点的度,树的度,叶子结点,分支结点,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径,孩子结点、双亲结点 兄弟结点、堂兄弟结点 祖先结点、子孙结点,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,结点的层次,树的深度,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大 层次,任何一棵非空树是一个二元组 Tree = （root，F） 其中 root 被称为根结点 F 被称为子树森林,森林,是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,() 有确定的根 () 树根和子树根之间为有向关系,有向树,有序树,子树之间存在确定的次序关系,无序树,子树之间不存在确定的次序关系,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),二叉树,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的五种基本形态,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,1BinTreeNode *GetRoot() const 初始条件：二叉树已存在。 操作结果：返回二叉树的根。 2bool Empty() const 初始条件：二叉树已存在。 操作结果：如二叉树为空，则返回true，否则返回false。,二叉树的主要基本操作,3StatusCode GetElem(TreeNode *cur, ElemType &e) const 初始条件：二叉树已存在，cur为二叉树的一个结点。 操作结果：用e返回结点cur元素值,如果不存在结点cur,函数返回NOT_PRESENT,否则返回ENTRY_FOUND。 4StatusCode SetElem(TreeNode *cur, const ElemType &e) 初始条件：二叉树已存在，cur为二叉树的一个结点。 操作结果：如果存在结点cur,则返回FAIL,否则返回SUCCESS,并将结点cur的值设置为e。,5void InOrder(void (*Visit)(const ElemType &) const 初始条件：二叉树已存在。 操作结果：中序遍历二对树，对每个结点调用函数(*visit)。 6void PreOrder(void (*Visit)(const ElemType &) const 初始条件：二叉树已存在。 操作结果：先序遍历二对树，对每个结点调用函数(*visit)。,7void PostOrder(void (*Visit)(const ElemType &) const 初始条件：二叉树已存在。 操作结果：后序遍历二对树，对每个结点调用函数(*visit)。 8void LevelOrder(void (*Visit)(const ElemType &) const 初始条件：二叉树已存在。 操作结果：层次遍历二对树，对每个结点调用函数(*visit)。 9int NodeCount() const 初始条件：二叉树已存在。 操作结果：返回二叉树的结点个数。,10 BinTreeNode *LeftChild(const BinTreeNode *cur) const; 初始条件：二叉树已存在，cur是二叉树的一个结点。 操作结果：返回二叉树结点cur的左孩子。 11 BinTreeNode *RightChild(const BinTreeNode *cur) const 初始条件：二叉树已存在，cur是二叉树的一个结点。 操作结果：返回二叉树结点cur的右孩子。,12 BinTreeNode *Parent(const BinTreeNode *cur) const 初始条件：二叉树已存在，cur是二叉树的一个结点。 操作结果：返回二叉树结点cur的双亲结点。 13 void InsertLeftChild( BinTreeNode *cur, const ElemType &e) 初始条件：二叉树已存在，cur是二叉树的一个结点，e为一个数据元素，并且cur非空。 操作结果：插入e为cur的左孩子，如果cur的左孩子非空，则cur原有左子树成为e的左子树。,14 void InsertRightChild(BinTreeNode *cur, const ElemType &e) 初始条件：二叉树已存在，cur是二叉树的一个结点，e为一个数据元素，并且cur非空。 操作结果：插入e为cur的右孩子，如果cur的右孩子非空，则cur原有右子树成为e的右子树。 15void DeleteLeftChild(BinTreeNode *cur) 初始条件：二叉树已存在，cur是二叉树的一个结点。 操作结果：删除二叉树结点cur的左子树。,16void DeleteRightChild(BinTreeNode *cur) 初始条件：二叉树已存在，cur是二叉树的一个结点。 操作结果：删除二叉树结点cur的右子树。 17int Height() const 初始条件：二叉树已存在。 操作结果：返回二叉树的高。,二叉树 的重要特性,性质 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,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，因此， k =log2n + 1 。,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,二叉树的存储结构,二、二叉树的链 式存储表示,一、二叉树的顺 序存储表示,完全二叉树的 一般二叉树的 数组表示 数组表示,顺序存储表示,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 struct BinTreeNode / 数据成员: ElemType data; / 数据域 BinTreeNode *leftChild; / 左孩子 BinTreeNode *rightChild; / 右孩子 / 构造函数: BinTreeNode(); / 无参构造函数 BinTreeNode(const ElemType ,/ 二叉树类 template class BinaryTree protected: / 二叉树的数据成员: BinTreeNode *root; / 辅助函数: BinTreeNode *CopyTreeHelp( BinTreeNode *copy); / 复制二叉树,void DestroyHelp(BinTreeNode * / 返回二叉树的高,int NodeCountHelp(const BinTreeNode *r) const; / 返回二叉树的结点个数 BinTreeNode *ParentHelp( BinTreeNode *r, const BinTreeNode *cur) const; / 返回cur的双亲 public: / 二叉树方法声明及重载编译系统默认方法声明: BinaryTree(); / 无参数的构造函数 virtual BinaryTree(); / 析构函数 BinTreeNode *GetRoot() const; / 返回二叉树的根,BinTreeNode *GetRoot() const; / 返回二叉树的根 bool Empty() const; / 判断二叉树是否为空 StatusCode GetElem(BinTreeNode *cur, ElemType / 二叉树的后序遍历,void LevelOrder(void (*Visit)(const ElemType / 插入左孩子,void InsertRightChild(BinTreeNode *cur, const ElemType ,二叉树遍历 (Binary Tree Traversal),顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次,问题的提出,“访问”的含义可以很广，如：输出结 点的信息等,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题,对“二叉树”而言，可以有三条搜索路径,1先上后下的按层次遍历 2先左（子树）后右（子树）的遍历 3先右（子树）后左（子树）的遍历,设 访问根结点 记作 V 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有 前序 VLR 逆前序 VRL 中序 LVR 逆中序 RVL 后序 LRV 逆后序 RLV 层次遍历,前序遍历 (Preorder Traversal),若二叉树为空，则空操作 否则 访问根结点(V) 前序遍历左子树(L) 前序遍历右子树(R) 遍历结果 - + a * b - c d / e f,template void BinaryTree:PreOrderHelp( BinTreeNode *r, void (*Visit)(const ElemType / 遍历右子树 ,template void BinaryTree:PreOrder( void (*Visit)(ElemType ,若二叉树为空，则空操作 否则 中序遍历左子树(L) 访问根结点(V) 中序遍历右子树(R) 遍历结果 a + b * c - d - e / f,中序遍历 (Inorder Traversal),表达式语法树,后序遍历 (Postorder Traversal),若二叉树为空，则空操作 否则 后序遍历左子树(L) 后序遍历右子树(R) 访问根结点(V) 遍历结果 a b c d - * + e f / -,层次遍历(Levelorder Traversal),从上到下，从左到右 遍历结果 - a* e f b -cd,template void BinaryTree:LevelOrder( void (*Visit)(const ElemType / 右孩子入队 ,对应中缀表达式 (a+b)c-d/e 的二叉树,a,b,c,d,e,-,+,/,特点： 操作数为叶子结点 运算符为分支结点,按给定的中缀表达式建相应二叉树,a+b,(a+b)c d/e,a+bc,分析表达式和二叉树的关系,a,b,+,a,b,c,+,a,b,c,+,(a+b)c,a,b,c,d,e,-,+,/,问题是有n个数据值，可能构造多少种不同的二叉树？ 我们可以固定前序排列，选择所有可能的中序排列,二叉树的计数,二叉树的计数 有0个, 1个, 2个, 3个结点的不同二叉树如下,具有4个结点的不同二叉树,计算具有n个结点的不同二叉树的棵数,Catalan函数,二叉树中序遍历非递归 算法的实现,template BinTreeNode *GoFarLeft(BinTreeNode *r, LinkStack * / cur为最左侧的结点 ,template void NonRecurInOrderHelp(BinTreeNode *r, void (*Visit)(const ElemType / 访问当前结点,if (cur-rightChild != NULL) / cur的中序序列后继为右子树的最左 / 侧的结点 cur = GoFarLeft(cur-rightChild, s); else if (!s.Empty() / cur的中序序列后继为栈s的栈顶结点 s.Pop(cur); / 取出栈顶结点 else / 栈s为空,无后继 cur = NULL; / 无后继 ,template void NonRecurInOrder(BinaryTree / 调用辅助函数完成中序遍历二叉树 ,遍历算法的应用举例,1、统计二叉树中结点的个数 (先序遍历),2、求二叉树的深度(后序遍历),3、复制构造函数,4、建立二叉树的存储结构,1、统计二叉树中叶子结点的个数,算法基本思想:,二叉树的结点个数等于左子树的结点数加上右子树的结点数再加上根结点数1，因此求二叉树的结点数的问题可以分解为计算其左右子树的结点数目问题,template int BinaryTree:NodeCountHelp( const BinTreeNode *r) const / 操作结果：返回以r为根的二叉树的结点个数 if (r =NULL) return 0; / 空二叉数结点个数为0 else return 1 + NodeCountHelp(r-leftChild) + NodeCountHelp(r-rightChild); / 结点个为左右子树的结点数和再加1 template int BinaryTree:NodeCount() const / 操作结果：返回二叉树的结点个数 return NodeCountHelp(root); ,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,template int BinaryTree:HeightHelp( const BinTreeNode *r) const / 操作结果：返回以r为根的二叉树的高 if(r = NULL) / 空二叉树高为0 return 0; ,else / 非空二叉树高为左右子树高的最大值再加1 int lHeight, rHeight; lHeight = HeightHelp(r-leftChild); /左子树高 rHeight=HeightHelp(r-rightChild);/右子树高 return 1 + (lHeight rHeight ? lHeight : rHeight);/ 高为左右子树高的最大值加1 template int BinaryTree:Height() const / 操作结果：返回二叉树的高 return HeightHelp(root); ,3、复制构造函数,首先讨论二叉树复制 其基本操作为：生成一个结点。,根元素,T,左子树,右子树,根元素,NEWT,左子树,右子树,左子树,右子树,template BinTreeNode *BinaryTree: CopyTreeHelp (BinTreeNode *copy) / 操作结果：将以copy为根的二叉树复制成新的二叉树,返 / 回新二叉树的根 if (copy = NULL) / 复制空二叉树 return NULL; / 空二叉树根为空 else / 复制非空二叉树,BinTreeNode *lChild = CopyTree(copy-leftChild); / 复制左子树 BinTreeNode *rChild = CopyTree(copy-rightChild); / 复制右子树 BinTreeNode *r = new BinTreeNode( copy-data, lChild, rChild); / 复制根结点 return r; ,template BinaryTree:BinaryTree(const BinaryTree / 复制二叉树 ,A,B,C,D,E,F,G,H,K, D ,C , B, H , K ,G, F ,E ,A,例如：下列二叉树的复制过程如下：,newT,4、建立二叉树的存储结构,由遍历序列生成二叉树,由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树,仅知二叉树的先序序列“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,c,d,e,f,g,先序序列 中序序列,template void CreateBinaryTreeHelp(BinTreeNode * / 空二叉树根为空 ,else / 二叉树有结点,非空二叉树 r = new BinTreeNode (prepreLeft); / 生成根结点 int mid = inLeft; while (inmid != prepreLeft) / 查找prepreLeft在in中的位置 / 也就是中序序列中根的位置 mid+; CreateBinaryTreeHelp(r-leftChild, pre, in, preLeft+1, preLeft + mid - inLeft, inLeft, mid - 1); / 生成左子树 CreateBinaryTreeHelp(r-rightChild, pre, in, preLeft + mid - inLeft + 1, preRight, mid + 1, inRight); / 生成右子树 ,template BinaryTree ,线索二叉树,遍历二叉树的结果是， 求得结点的一个线性序列,A,B,C,D,E,F,G,H,K,先序序列 A B C D E F G H K,中序序列 B D C A H G K F E,后序序列 D C B H K G F E A,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,与其相应的二叉树， 称作 “线索二叉树”,包含 “线索” 的存储结构，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,对线索链表中结点的约定,在二叉链表的结点中增加两个标志域 leftTag和rightTag,并作如下规定:,若该结点的左子树不空， 则leftChild域的指针指向其左孩子， 且左标志leftTag的值为0 否则，leftChild域的指针指向其“前驱”， 且左标志leftTag的值为1,若该结点的右子树不空， 则rightChild域的指针指向其右孩子， 且右标志Rrightag的值为0 否则，rightChild域的指针指向其“后继”，且右标志rightTag的值为1,如此定义的二叉树的存储结构称作“线索链表”,后序序列 D B E C A,前序序列 A B D C E,带表头结点的中序线索二叉树,树的存储结构,一、双亲表示法 二、孩子表示法 三、孩子兄弟表示法,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5,data parent,双亲表示法,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5,data firstchild,1 2 3,4 5,6,孩子链表表示法,-1 0 0 0 2 2 4,A,B,C,D,E,F,G,A B C E D F G,root,A B C E D F G,孩子兄弟表示法,孩子兄弟表示法,data,firstChild,nextSibling,森林与二叉树 的转换,B C D E F G H I J K,1森林中第一棵树的根结点,2森林中第一棵树的子树森林,3森林中其它树构成的森林,森林由三部分构成,森林转化成二叉树 的规则, 若F为空，即n = 0，则 对应的二叉树B为空二叉树 若F不空，则 对应二叉树B的根root(B)是F中第 一棵树T1的根root(T1)，其左子树为 B(T11, T12, , T1m)，其中，T11, T12, , T1m是root(T1)的子树；其右子 树为B(T2, T3, , Tn)，其中，T2, T3, , Tn是除T1外其它树构成的森林,二叉树转换为森林 的规则, 如果B为空，则对应的森林F也为空 如果B非空，则 F中第一棵树T1的根为root；T1的根 的子树森林(T11, T12, , T1m ) 是由 root的左子树LB转换而来，F 除了T1 之外其余的树组成的森林(T2, T3, , Tn )是由root的右子树RB转换而成的 森林,森林与二叉树的转换,树的先根遍历,若树为空，则空操作，结束；否则按如下规则遍历： （1）访问根结点； （2）分别先根遍历根的各棵子树。,树 的 遍 历,树的后根遍历,若树为空，则空操作，结束；否则按如下规则遍历： （1）分别后根遍历根的各棵子树； （2）访问根结点。,A B C D E F G H I J K,先根次序遍历,A B E F C D G H I J K,后根次序遍历,E F B C I J K H G D A,森林的先根遍历,若森林F为空, 返回 否则: 访问F的第一棵树的根结点 先根次序遍历第一棵树的子树森林 先根次序遍历其它树组成的森林,森 林 的 遍 历,森林的中根遍历,若森林F为空，返回 否则: 中根次序遍历第一棵树的子树森林 访问F的第一棵树的根结点 中根次序遍历其它树组成的森林,哈 夫 曼 树