c数据结构,二叉树DS5-BinaryTree(new).ppt

第五章 二叉树,主要内容,5.1 定义与主要特性 5.2 二叉树的实现 5.3 遍历二叉树及线索化 5.4 二叉搜索树 5.5 AVL树 5.6 堆 5.7 霍夫曼编码树,2,5.1 定义与特性,5.1.1 定义和术语 5.1.2 二叉树的性质,3,5.1.1定义和术语,一、树的定义,5,定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点； （2）其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree) 这是一个递归定义。,二、二叉树的定义,6,定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树,三、相关术语,7,结点的度 树的度 叶结点 分支结点 左孩子、右孩子、双亲 路径、路径长度 祖先、子孙 结点的深度 树的高度,5.1.2二叉树的性质,9,9,一、二叉树的定义和特点,1、定义：二叉树是有限个结点的集合，它或者是空，或者是由一个根结点加上两棵分别称为左子树和右子树、互不相交的二叉树组成。,2、特点,每个结点最多只有两个孩子结点，即结点的度不大于2。 子树有左右之别，子树的次序（位置）不能颠倒。,3、基本形态,空,只有根结点,根的右子 树为空,根的左子 树为空,根的左右子 树都不空,10,10,二、二叉树的性质,11,如果二叉树中每一个结点，或者是叶节点，或者是分支节点且恰有两个非空子结点。,2,4,5,3,6,7,1,图 满二叉树,三、满二叉树,12,1,2,3,4,5,6,1,2,3,4,5,7,1,2,3,6,7,(a)完全二叉树,(b)非完全二叉树,( c)非完全二叉树,图 完全二叉树,四、完全二叉树,一棵高度为d的二叉树除了d-1层以外每一层都是满的，并且每一层都是从左到右填充,13,定理1：非空满二叉树的叶结点数等于其分支结点数加1,四、满二叉树定理,定理2：一棵非空二叉树空子树的数目等于其结点数目加1,14,如图5.11所示为完全二叉树上结点及其 左右孩子结点之间的关系。,i/2,i,i+1,2i,2i+1,2(i+1),2i+3,i+1/2,i+1,2(i+1),2i+3,i,2i,2i+1,图5.11 完全二叉树中结点I和i+1,(a)I和i+1结点在同一层,(b)I和i+1结点不在同一层,5.2 二叉树的实现,5.2.1 二叉树抽象数据类型 5.2.2 使用指针实现 5.2.3 使用数组实现,15,16,5.2.1二叉树的抽象数据类型,二叉树结点的ADT template class BinNode public: virtual Elem /判断是否为叶结点 ,16,17,5.2.2 使用指针实现,结点结构和示例,18,二叉树的二叉链表存储表示 template class BinaryTree; template class BinTreeNode firend class BinaryTree; private: Elem data;/数据域 BinTreeNode * lchild; /左子结点指针域 BinTreeNode * rchild; /右子结点指针域 public: BinTreeNode()lchild=rchild=NULL; BinTreeNode(Elem e,BinNodePtr*l=NULL, BinNodePtr*r=NULL) data=e; lchild=l; rchild=r; BinTreeNode(),链式存储的特点,动态建立，灵活性高 结构性开销大,19,20,5.2.3 使用数组实现,a,b,c,d,e,f,g,h,i,j,k,l,1 2 3 4 5 6 7 8 9 10 11 12,21,一般二叉树, 表示该处没有元素存在仅仅为了好理解,数组存储的特点,对于完全二叉树空间利用率很高 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费 在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好,22,5.3 二叉树的遍历及线索化,5.3.1 遍历二叉树 5.3.2 线索化二叉树,23,24,5.3.1 遍历二叉树（Traversal Binary Tree）,一、TBT概述,1、定义,按某种次序，访问所有结点，使每个节点都被访问且尽访问一次的运算叫TBT。 “访问”包括输出结点值，修改值，统计等以不破坏BT的结构为原则。 TBT是对二叉树进行运算的基础性操作。,25,一、TBT概述,2、次序（V根，L左子树，R右子树）,先序遍历 中序遍历 后序遍历 先右后左： VRL RVL RLV 先左后右： VLR LVR LRV,VLR输出序列：A B D E G HI J C F LVR输出序列：D B G EI H J A C F LRV输出序列：D G I JH E B F C A,26,二、TBT的递归算法,1、中序遍历（ inorder traversal）,template void BinaryTree : InOrder ( ) InOrder (root); /公共函数，调用私有函数完成遍历 template void BinaryTree : InOrder (BinTreeNode *current) if (current != NULL) /当current = = NULL，则递归终结 InOrder (current - leftChild); /中序遍历左子树 cout data; /访问根结点 InOrder (current - rightChild); /中序遍历右子树,对 a+b*(c-d)-e/f 表达式的语法树，中序遍历得到其中缀表示： a + b * c d e / f,27,2、先序遍历（ preorder Traversal）,template void BinaryTree : PreOrder (BinTreeNode *current) /私有函数 if (current != NULL) cout data; PreOrder (current - leftChild); PreOrder (current - rightChild); ,对表达式a+b*(c-d)-e/f 的语法树进行先序遍历得到其前缀表示： + a * b c d / e f,二、TBT的递归算法,28,3、后序遍历（ postorder traversal）,template void BinaryTree : PostOrder (BinTreeNode *current) /私有函数 if (current != NULL) PostOrder (current - leftChild); PostOrder (current - rightChild); cout data; ,二、TBT的递归算法,对表达式 a+b*(c-d)-e/f 的语法树进行后序遍历得到其后缀表示： a b c d * + e f / ,29,二、TBT的递归算法,4、TBT递归算法的简化,traversal (BinTreeNode *current) if (current != NULL) traversal (current - leftChild); cout data; traversal (current - rightChild); ,30,三、TBT的非递归算法,1、递归算法中栈的使用,执行过程中栈的情况和current的变化举例,当左向递归则current的值进栈 若current = = NULL，则出栈，current以栈顶值去执行右向递归 直到栈空（top = -1）和current = = NULL为止,31,2、利用栈的前序和中序遍历非递归算法,template void BinaryTree : PreOrder ( ) stack * st; BinTreeNode *p = root; do while (p != NULL) cout data; st. Push (p); p = p -leftChild; if ( St. length()!=0) st. pop (p ); p = p - rightChild; while (p != NULL | | st.length ( )!=0);,算法描述 p不空则p进栈，沿左子树方向传递指针 若p空但栈不空，出栈，p以栈顶值沿右子树方向传递指针 循环下去，直到p和栈都空为止 执行中栈的情况和指针的变化与递归程序相同,三、TBT的非递归算法,对于中序遍历只需调整输出语句位置即可,32,3、层次遍历,三、TBT的非递归算法,33,3、层次遍历,template void BinaryTree : LevelOrder ( ) queue * qu; BinTreeNode *p = root; qu.Enqueue(p); while (qu.DeQueue (p ) cout data leftChild != NULL) qu.EnQueue (p - leftChild); if (p - rightChild != NULL) qu.EnQueue (p - rightChild);,三、TBT的非递归算法,34,层次遍历是指直上至下，从左到右访问结点 只有采用队列来存放结点地址才能实现层次遍历,3、层次遍历示例,ad1,ad2,ad3,ad4,ad5,ad6,35,5.3.2 线索化二叉树,一、概述,1、问题提出,遍历是二叉树最基本的运算，为避免再次遍历的麻烦，可将首次遍历得到的信息存于一个线性结构中。 具有n个结点的链式存贮的二叉树中，有n+1个链域是空的，能否充分利用这些空的链域来存放结点的前趋指针和后继指针呢？,36,一、概述,2、实现策略,结点中增加两个标记域,两标记域取值范围是0，1。各只占一个二进制位，只增加很少的额外空间开销。,37,3、线索二叉树,指向前驱和指向后继的指针叫做线索（Thread）。 具有线索的二叉树叫做线索二叉树。 因遍历的次序有三种，所以线索二叉树也分前、中、后序这三种。 中序遍历线索二叉树结构示例,若根的左子树不空，则其最左下角的结点为中序遍历的第一个结点，否则根为中序遍历的第一个结点。 若根的右子树不空，则其最右下角的结点为中序遍历的最后一个结点，否则根为中序遍历的最后一个结点。,38,二、中序线索二叉树的类定义,1、类声明,template class ThreadTree; template class ThreadNode friend class ThreadTree ; private: int leftThread, rightThread; ThreadNode * leftChild, rightChild; Elem data; public: ThreadNode (const Elem item) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) Elem getData ( ) const return data;,39,template class ThreadTree private : ThreadNode *root; InThread (ThreadNode *current, ThreadNode *pre); public : ThreadTree( ) : root(NULL) ; ThreadNode *First(ThreadNode *current); ThreadNode *Last(ThreadNode * current); ThreadNode *Next(ThreadNode *current); ThreadNode *Prior(ThreadNode *current); void Inorder( ); /从第一个结点开始沿着后继方向遍历二叉树 ,40,5.4 二叉搜索树（Binary Search Tree）,一、基本概念,1、定义或是空、或是具有下列性质的二叉树：,每个结点有一个作为搜索依据的关键码（Key）。 左子树上所有关键码小于根结点关键码。 右子树上所有关键码大于根结点关键码。,2、举例,中序遍历结果： 09，17，23，45，53，65，78，81，87，94 显然是有序的，故又称二叉排序树。,41,一、基本概念,3、BST是基于二叉树的动态搜索结构，其删除和插入结点可能要改变树的结构。,4、BST类定义特点,类定义基于二叉链存贮表示 与一般二叉树类定义十分相似 可以继承一般二叉树类的定义 基本运算Find, Insert 和 Remove 都用递归实现所以在类定义中包括私有和公用两种性质的声明,42,二叉查找树的C+类说明,template class BST: public Dictionary private: BinTreeNode * root; Elem RefValue int nodecount; void clearhelp(BinTreeNode*); BinTreeNode* inserthelp(BinTreeNode*,const Elem,43,public: BST( ) root=NULL; nodecount=0; BST()clearhelp(root); void clear()clearhelp(root); root=NULL; nodecount=0; bool insert(const Elem,44,bool find(counst Key,45,二、BST上的搜索,1、基本方法,从根开始将给定值 x 与结点值进行比较 若 x 小，沿着左子树继续搜索 若 x 大，沿着右子树继续搜索 若与 x 等则成功返回结点地址，若为空则失败,2、举例, x = 23,成功，比较次数为4, x = 88,失败，比较次数为4, 比较次数不大于 h + 1,46,3、递归算法,template bool BST: findHelp (BinNode*subroot, constKey ,该算法的递归调用语句都于程序的最尾，称为尾递归 返回时返回到上一层调用处的下条语句去执行 因为是最尾语句，程序结束，不必用栈保存返回地址和局部变量的值 该算法可以不用栈，采用迭代方法改写成非递归程序,二、BST上的搜索,47,4、迭代算法,template bool BST: findHelp (BinTreeNode*subroot, constKey ,一般对尾递归或单向递归的情形，都可利用迭代方法，不使用栈将递归过程改为非递归过程,二、BST上的搜索,48,三、BST中的插入,1、方法,先搜索BST中有无该结点，只有无才插入 插入是作为叶子插入，插入后仍满足BST 插入位置应是搜索操作停止（指针ptr为空）的地方,2、算法,template BinNode* BST: inserthelp(BinNode* subroot, const Elem ,49,3、建BST,逐次输入关键码序列建一棵BST，是从空开始逐步插入结点 每次从根开始搜索插入位置，然后将新结点作为叶子插入 关键码集合相同但输入序列不同得到的BST也不同,若输入次序：,81, 65, 78, 94, 87, 88, 23, 45 ,09, 17, 53,81,87,17,23,78,09,65,94,45,53,88,三、BST中的插入,50,四、BST中的结点删除,1、原则,删除结点所断开的链要重新接起来 删除链接后仍是BST 重新链接后树的高度不增加,2、方法,被删结点为叶子，只需将双亲结点的相应指针置为空 被删结点无右子树，拿左孩子结点顶替它的位置 被删结点无左子树，拿右孩子结点顶替它的位置 被删结点左右子树都有，在右子树中找中序遍历第一个结点，用它的值填补到被删结点，然后再来删这个结点 结点删除是一个递归的过程,51,3、有左右子树的结点删除举例,删除关键码78的结点,右子树中序第一结点是81,81复盖78,81结点无左子树，用右孩 子88顶替,81,四、BST中的结点删除,81,88,BST中deletemin函数的实现,deletemin(BinTreeNode*subroot,BinTreeNode* ,52,53,removehelp(BinTreeNode*subroot, constKey ,BST中removehelp函数的实现,思考：,BST树平衡性如何？能不能保证平衡？,54,55,5.5 AVL树,一、AVL树（高度平衡的BST）概念,1、定义AVL或是空树，或是具有下列性质的BST： 它的左、右子树都是AVL树，且左右子树的高度之差的绝对值不超过1。,2、举例,是二叉搜索树 树和所有子树的左右子树高度之差绝对值不超过1 属AVL树,3、平衡因子（balance factor）,结点右子树高度减去左子树高度所得高度差 AVL树中所有结点的平衡因子只能取0，1，1 AVL树的ASL可保持在O(log2n),56,二、平衡化旋转,1、向AVL树插入结点可能造成不平衡，此时要调整树的结构使之重新达到平衡,2、平衡化旋转方法,从插入位置沿通向根的路径回溯检查各结点的平衡因子 若发现不平衡结点，则从该结点起沿刚才回溯路径取直接下两层结点 若三个结点在一条直线上，则采用单旋转进行平衡化；若三结点在一条折线上，则采用双旋转进行平衡化,57,3、平衡化旋转示例,左单旋转,二、平衡化旋转,58,右单旋转,3、平衡化旋转示例,二、平衡化旋转,59,先左后右双旋转,3、平衡化旋转示例,二、平衡化旋转,60,Copyright 2004 by Li Rui,60,先右后左旋转,3、平衡化旋转示例,二、平衡化旋转,61,三、AVL树的建立,对于一组关键码的输入序列，从空开始不断插入结点，最后构成AVL树 每插入一个结点后就应判断从该结点到根的路径上有无结点发生不平衡 如有不平衡问题，利用旋转方法进行树的调整，使之平衡化 建AVL树过程是不断插入结点和必要时进行平衡化的过程,62,BST、AVL树在Mini数据库中的应用,63,Copyright 2004 by Li Rui,63,64,5.6 堆（Heap）,一、堆的定义,1、什么是堆？,若有n个关键字的集合K=k0,k1,k2, ,kn-1将其所有元素按完全二叉树的顺序存贮方式存于一个一维数组中，并且满足以下条件，则该集合称为最小堆（或最大堆）。 kik2i+1和kik2i+2 或 kik2i+1和kik2i+2 (其中，i = 0,1, (n 2) / 2 ),举例,65,2、最小堆的类声明,template class MinHeap private : Elem * heap; /存放堆元素的数组 int n; /堆当前元素个数 int size; /堆最多允许元素个数 void siftdown (int i) public : MinHeap (Elem* h, int num ,int max) /构造堆 Heap=h; n=num; size=max; buildHeap(); int heapsize() const return n; MinHeap( ) delete heap;,66,bool Insert (const Elem ,67,二、堆的建立,1、自下向上逐步调整建堆的举例,68,二、堆的建立,1、自下向上逐步调整建堆的举例,69,二、堆的建立,1、自下向上逐步调整建堆的举例,70,二、堆的建立,1、自下向上逐步调整建堆的举例,对第i个关键字进行筛选的要点：,在第（2 i + 1）和（2 i + 2）中选小者定为第j,若第i大于第j则交换,向下继续：i = j，j = 2 i + 1，重复、，直到j(n 1),71,向下筛选的算法,template void MinHeap :siftDown(int pos) while(!isLeaf(pos) int j=leftchild(pos); int rc=rightchild(pos); if(rcn) ,72,三、堆的插入与删除,1、插入,插入是插到最小堆的后面，这样整体可能不是堆了。 为了再成堆，要从插入元素的双亲开始逐层向上筛选。 向上筛选举例,73, template bool MinHeap : Insert(const Elem ,三、堆的插入与删除,1、插入,74,2、删除最小元素,删除是指删除最小关键字者，即堆顶元素，也就是数组中的0号元素。 删除之后常将堆底元素，即原来的第（n 1）号关键字置于堆顶处，然后元素个数减1。 删除处理后，新的序列常常不是堆了，为此要调整重建堆。 因为原来已是堆，而现在变更的只是0号位上的元素，所以只需对0号位由上往下进行筛选就可以重建堆。 删除算法,三、堆的插入与删除,删除最小节点,templat bool MinHeap : RemoveMin(Elem ,75,76,template bool MinHeap: remove(int pos,Elem ,删除某一个节点,77,5.7 霍夫曼树,一、树的路径长度（PL）,1、PL是指从根到其它各结点的路径长度（分支数）之和,78,2、具有n个结点的路径长度分析,完全二叉树各结点的路径长度分别是数列 0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4, 的前n项之和，具有最小值,若n个结点的高度为h的二叉树，从根到 h 1 层都有最多结点数 2h 1 ，其余结点分布在第 h 层的任意位置上，也具有最小 PL ，这种树称为理想平衡二叉树。,一、树的路径长度（PL）,79,二、霍夫曼树,1、树的带权（Weighted）路径长度 WPL,带权的叶子结点又名外结点，具有外结点的树叫扩充二叉树 具有n个外结点，其中任意结点的权值为Wi，到根的路径长度为 li ，则该扩充二叉树的带权路径长度为： 具有最小 WPL 的扩充二叉树叫霍夫曼树,80,2、霍夫曼树的构造方法,将n个权值视为具有n棵扩充二叉树的森林F，然后重复以下步骤，直到F中只有一棵树为止：,在F中选根的权值最小的两棵作为左右子树构造一棵新的二叉树，其根的权为左右子树根的权值之和。,在F中删除那两棵树，并把新的二叉树加入。,二、霍夫曼树,81,三、Huffman树的实现,templateclass HuffNode public: virtual int weight()=0; virtual bool isLeaf()=0; virtual HuffNode* left() const=0; virtual void setLeft(HuffNode*)=0; virtual HuffNode* right() const=0; virtual void setRight(HuffNode*)=0; ;,抽象基类,82,template class LeafNode:public HuffNode private: FreqPair* it; public: LeafNode(const Elem virtual void setLeft(HuffNode*) virtual HuffNode*right()constreturn NULL: virtual void setRight(HuffNode*) ；,三、Huffman树的实现,叶结点类,83,template class IntlNode:public HuffNode private: HuffNode* lc; HuffNode* rc; int wgt; public: IntlNode(HuffNode* l,HuffNode* r) wgt=l-weight()+r-weight(); lc=l,rc=r; int weight()return wgt; bool isLeaf()return false; HuffNode* left()constreturn lc; void setLeft(HuffNode*b) lc=(HuffNode*)b; HuffNode*right()constreturn rc: void setRight(HuffNode*b) rc=(HuffNode*)b; ;,三、Huffman树的实现,内部结点类,84,template class FreqPair private: Elem it; int freq; public: FreqPair(const Elem,三、Huffman树的实现,元素/频率对的类,85