数据结构中的树.ppt

《数据结构中的树.ppt》由会员分享，可在线阅读，更多相关《数据结构中的树.ppt（102页珍藏版）》请在课桌文档上搜索。

1、1,树与二叉树,2,树和森林的概念,两种树：自由树与有根树。自由树：一棵自由树 Tf 可定义为一个二元组Tf=(V,E)其中V=v1,.,vn 是由 n(n0)个元素组成的有限非空集合，称为顶点集合。E=(vi,vj)|vi,vj V,1i,jn 是n-1个序对的集合，称为边集合，E 中的元素(vi,vj）称为边或分支。,3,自由树,有根树：一棵有根树 T，简称为树，它是n(n0)个结点的有限集合。当n=0时，T 称为空树；否则，T 是非空树，记作,4,r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为 m(m 0)个互不相交的有限集合T1,T2,T

2、m，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,5,树的基本术语,子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。,6,兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都是该结点的子孙。,7,结点的层次：规定根结点在第一层，其子女结点的层次等于它的层

3、次加一。以下类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。,8,高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。有序树：树中结点的各棵子树 T0,T1,是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m0）棵树的集合。,9,树的抽象数据类型,template class Tree/对象:树是由n(0)个结点组成的有限集合。在/类界面中的 position 是树中结点的地址。在顺序/存储方式下是下标型,在链表存储方式下是指针/型。T 是树结点中存放数据的类型,要求所有结/点的数据类型都是一致的。pub

4、lic:Tree();Tree();,10,BuildRoot(const T/在结点 p 下插入值为 value 的新子女,若插/入失败,函数返回false,否则返回true,11,bool DeleteChild(position p,int i);/删除结点 p 的第 i 个子女及其全部子孙结/点,若删除失败,则返回false,否则返回true void DeleteSubTree(position t);/删除以 t 为根结点的子树 bool IsEmpty();/判树空否,若空则返回true,否则返回false void Traversal(position p);/遍历以 p 为根

5、的子树;,12,二叉树的五种不同形态,L,L,R,R,二叉树(Binary Tree),二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,13,二叉树的性质,性质1 若二叉树结点的层次从 1 开始,则在二叉树的第 i 层最多有 2i-1 个结点。(i1)证明用数学归纳法性质2 深度为 k 的二叉树最少有 k 个结点，最多有 2k-1个结点。(k1)因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1：用求等比级数前k项和的公式20+21+22+2k-1=2k-1,14,性质3 对任何一棵

6、二叉树，如果其叶结点有 n0 个,度为 2 的非叶结点有 n2 个,则有n0n21 若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2 e=2n2+n1=n-1 因此，有 2n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1,15,定义1 满二叉树(Full Binary Tree)定义2 完全二叉树(Complete Binary Tree)若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层(1k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。,16,性质4 具有 n(n0)个结点的完

7、全二叉树的深度为 log2(n+1)设完全二叉树的深度为k，则有 2k-1-1 n 2k-1 变形 2k-1 n+12k 取对数 k-1 log2(n+1)k 有 log2(n+1)=k,上面k-1层结点数,包括第k层的最大结点数,23-1,24-1,17,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,n，则有以下关系：若i=1,则 i 无双亲若i 1,则 i 的双亲为i2若2*i=n,则 i 的左子女为 2*i，若2*i+1=n,则 i 的右子女为2*i+1若 i 为奇数,且i!=1,则其左兄弟为i-1,若若 i 为偶数,且i!=n,则其右兄弟为i+1,

8、18,二叉树的抽象数据类型,template class BinaryTree/对象:结点的有限集合,二叉树是有序树public:BinaryTree();/构造函数 BinaryTree(BinTreeNode*lch,BinTreeNode*rch,T item);/构造函数,以item为根,lch和rch为左、右子/树构造一棵二叉树 int Depth();/求树深度 int Size();/求树中结点个数,19,bool IsEmpty();/判二叉树空否？BinTreeNode*Parent(BinTreeNode*t);/求结点 t 的双亲 BinTreeNode*LeftChil

9、d(BinTreeNode*t);/求结点 t 的左子女 BinTreeNode*RightChild(BinTreeNode*t);/求结点 t 的右子女 bool Insert(T item);/在树中插入新元素 bool Remove(T item);/在树中删除元素 bool Find(T/取得结点数据,20,BinTreeNode*getRoot();/取根 void preOrder(void(*visit)(BinTreeNode*t);/前序遍历,visit是访问函数 void inOrder(void(*visit)(BinTreeNode*t);/中序遍历,visit是访问

10、函数 void postOrder(void(*visit)(BinTreeNode*t);/后序遍历,(*visit)是访问函数 void levelOrder(void(*visit)(BinTreeNode*t);/层次序遍历,visit是访问函数;,21,完全二叉树 一般二叉树的顺序表示 的顺序表示,二叉树的顺序表示,22,极端情形:只有右单支的二叉树,23,二叉树结点定义：每个结点有3个数据成员，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针。,二叉链表,二叉树的链表表示,24,三叉链表,二叉树的链表表示,每个结点增加一个指向双亲的指

11、针parent，使得查找双亲也很方便。,25,二叉树链表表示的示例,26,二叉树遍历,二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,27,中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果 a+b*c-d-e/f,中序遍历(Inorder Traversal),-,-,/,+,*,a,b,c,d,e,f,28,二叉树递归

12、的中序遍历算法,template void BinaryTree:InOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)if(subTree!=NULL)InOrder(subTree-leftChild,visit);/遍历左子树 visit(subTree);/访问根结点 InOrder(subTree-rightChild,visit);/遍历右子树;,29,前序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。遍历结果-+a*b-c d/e f,前序遍历(Preord

13、er Traversal),-,-,/,+,*,a,b,c,d,e,f,30,二叉树递归的前序遍历算法,template void BinaryTree:PreOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)if(subTree!=NULL)visit(subTree);/访问根结点PreOrder(subTree-leftChild,visit);/遍历左子树PreOrder(subTree-rightChild,visit);/遍历右子树;,31,后序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历

14、右子树(R)；访问根结点(V)。遍历结果 a b c d-*+e f/-,后序遍历(Postorder Traversal),-,-,/,+,*,a,b,c,d,e,f,32,二叉树递归的后序遍历算法,template void BinaryTree:PostOrder(BinTreeNode*subTree,void(*visit)(BinTreeNode*t)if(subTree!=NULL)PostOrder(subTree-leftChild,visit);/遍历左子树PostOrder(subTree-rightChild,visit);/遍历右子树visit(subTree);/访

15、问根结点;,33,template int BinaryTree:Size(BinTreeNode*subTree)const/私有函数：利用二叉树后序遍历算法计算二叉/树的结点个数 if(subTree=NULL)return 0;/空树 else return 1+Size(subTree-leftChild)+Size(subTree-rightChild);,应用二叉树遍历的事例,34,template int BinaryTree:Height(BinTreeNode*subTree)const/私有函数：利用二叉树后序遍历算法计算二叉/树的高度或深度 if(subTree=NULL

16、)return 0;/空树高度为0 else int i=Height(subTree-leftChild);int j=Height(subTree-rightChild);return(i j)?j+1:i+1;,35,利用二叉树前序遍历建立二叉树,以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归,此值在RefValue中。例如用“”或用“-1”表示字符序列或正整数序列空结点。,36,层次序遍历二叉树就是从根结点开始，按层次逐层遍历，如图：,遍历顺序,层次序遍历二叉树的算法,37,这种遍历需要使用一个先进先出的

17、队列，在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续访问它们。算法是非递归的。,38,a,访问a,进队,a出队访问b,进队访问c,进队,b,c,b出队访问d,进队,c,d,c出队访问e,进队,d,e,d出队,e,e出队,39,层次序遍历的（非递归）算法,template void BinaryTree:levelOrder(void(*visit)(BinTreeNode*t)if(root=NULL)return;Queue*Q;BinTreeNode*p=root;visit(p);Q.EnQueue(p);while(

18、!Q.IsEmpty()Q.DeQueue(p);if(p-leftChild!=NULL),40,visit(p-leftChild);Q.EnQueue(p-leftChild);if(p-rightChild!=NULL)visit(p-rightChild);Q.EnQueue(p-rightChild);,41,由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例,前序序列 A B H F D E C K G 和中序序列 H B D F A E K C G,构造二叉树过程如下：,42,前序序列 A B H F D E C K G,43,如果前序序列固定不变，给出不同的中序序列，可得

19、到不同的二叉树。固定前序排列，选择所有可能的中序排列，可能构造多少种不同的二叉树？,44,例如,有 3 个数据 1,2,3，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321，231，213，132，123。前序序列为 123，中序序列为 312 的二叉树不存在。,45,线索化二叉树(Threaded Binary Tree),又称为穿线树。通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以

20、高效地找出某结点的前驱、后继。,46,线索(Thread),增加前驱Pred指针和后继Succ指针的二叉树,47,这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。改造树结点，将 pred 指针和 succ 指针压缩到 leftChild 和 rightChild 的空闲指针中，并增设两个标志 ltag 和 rtag，指明指针是指示子女还是前驱后继。后者称为线索。ltag(或rtag)=0，表示相应指针指示左子女（或右子女结点）；当ltag(或rtag)=1,表示相应指针为前驱（或后继）线索。,48,线索化二叉树及其链表表示,49,线索化二叉树的类定义,template str

21、uct ThreadNode/线索二叉树的结点类 int ltag,rtag;/线索标志 ThreadNode*leftChild,*rightChild;/线索或子女指针 T data;/结点数据 ThreadNode(const T item)/构造函数:data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0);,50,template class ThreadTree/线索化二叉树类protected:ThreadNode*root;/树的根指针 void createInThread(ThreadNode*current,T

22、hreadNode*/寻找结点t的双亲结点public:ThreadTree():root(NULL)/构造函数,51,void createInThread();/建立中序线索二叉树 ThreadNode*First(ThreadNode*current);/寻找中序下第一个结点 ThreadNode*Last(ThreadNode*current);/寻找中序下最后一个结点 ThreadNode*Next(ThreadNode*current);/寻找结点在中序下的后继结点 ThreadNode*Prior(ThreadNode*current);/寻找结点在中序下的前驱结点;,52,通过

23、中序遍历建立中序线索化二叉树,53,0 A 0,1 B 0,0 C 0,0 D 0,0 E 0,root,pre=NULL,current,54,0 A 0,1 B 0,0 C 0,1 D 0,0 E 0,root,pre,current,55,0 A 0,1 B 0,0 C 0,1 D 1,0 E 0,root,pre,current,56,0 A 0,1 B 0,0 C 0,1 D 1,1 E 0,root,pre,current,57,0 A 0,1 B 0,0 C 0,1 D 1,1 E 1,root,pre,current,58,0 A 0,1 B 0,0 C 1,1 D 1,1 E

24、 1,root,pre,后处理,59,树的存储表示,A(B(E,F),C,D(G)结点的utype域没有画出,1、广义表表示,60,2、双亲表示,树中结点的存放顺序一般不做特殊要求，但为了操作实现的方便，有时也会规定结点的存放顺序。例如，可以规定按树的前序次序存放树中的各个结点，或规定按树的层次次序安排所有结点。,61,3、子女链表表示,无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。,62,4、子女指针表示,一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。为此，设置等长的结点，每个结点包含的指针个数

25、相等，等于树的度（degree）。这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。,63,等数量的链域,空链域2n+1个,64,5、子女-兄弟表示,也称为树的二叉树表示。结点构造为：firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。若想找某结点的所有子女，可先找firstChild,再反复用 nextSibling 沿链扫描。,65,树的子女-兄弟表示,66,堆(Heap),template class MinPQ/最小优先级队列类的定义pu

26、blic:Virtual bool Insert(E,优先级队列每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。,67,最小堆完全二叉树顺序表示 KiK2i+1&KiK2i+2,最大堆完全二叉树顺序表示KiK2i+1&KiK2i+2,堆的定义,68,堆的元素下标计算,由于堆存储在下标从 0 开始计数的一维数组中，因此在堆中给定下标为 i 的结点时 如果 i=0，结点 i 是根结点，无双亲；否则结点 i 的父结点为结点(i-1)/2)；如果 2i+1n-1，则结点 i 无左子女；否则结点 i 的左子女为结点 2i+1；如果 2i+2n-1，则结点 i 无右子女；否则结点 i 的

27、右子女为结点 2i+2。,69,自下向上逐步调整为最小堆,currentPos=i=3,currentPos=i=2,将一组用数组存放的任意数据调整成堆,70,currentPos=i=1,71,currentPos=i=0,72,73,树的应用例子-决策树,74,树的应用例子-文件系统,搜索树,75,76,二叉搜索树(Binary Search Tree),定义 二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为搜索依据的关键码(Key)，所有结点的关键码互不相同。左子树（如果非空）上所有结点的关键码都小于根结点的关键码。右子树（如果非空）上所有结点的关键码都大于根结

28、点的关键码。左子树和右子树也是二叉搜索树。,77,二叉搜索树例,结点左子树上所有关键码小于结点关键码；右子树上所有关键码大于结点关键码；,注意：若从根结点到某个叶结点有一条路径，路径左边的结点的关键码不一定小于路径上的结点的关键码。,78,如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树。二叉搜索树的类定义#include#include template struct BSTNode/二叉树结点类 E data;/数据域 BSTNode*left,*right;/左子女和右子女,79,BSTNode()left=NULL;righ

29、t=NULL;/构造函数 BSTNode(const E d,BSTNode*L=NULL,BSTNode*R=NULL)data=d;left=L;right=R;/构造函数 BSTNode()/析构函数 void setData(E d)data=d;/修改 E GetData()return data;/提取 bool operator(const E,80,bool operator(const E/析构函数,81,bool Search(const K x)const/搜索 return Search(x,root)!=NULL;BST,82,bool Remove(const K

30、x)return Remove(x,root);/删除含x的结点private:BSTNode*root;/根指针 K RefValue;/输入停止标志 BSTNode*/递归：搜索 Search(const K x,BSTNode*ptr);void makeEmpty(BSTNode*,83,BSTNode*Min(BSTNode*ptr);/递归：求最小 BSTNode*Max(BSTNode*ptr);/递归：求最大 bool Insert(const E二叉搜索树的类定义用二叉链表作为它的存储表示，许多操作的实现与二叉树类似。,84,二叉搜索树的搜索算法,在二叉搜索树上进行搜索，是一

31、个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为 x 的元素，搜索过程从根结点开始。如果根指针为NULL，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较：若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。,85,若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子树。,搜索45搜索成功,搜索28搜索失败,86,搜索过程是从根结点开始，沿某条路径自上而下逐层比较判等的过程。搜索成功，搜索指针将停留在树上某个结点；搜索不成功，搜索指针将走到树上某个结点的空子树。设树

32、的高度为h，最多比较次数不超过h。,87,二叉搜索树的插入算法,为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。,88,插入新结点28,二叉搜索树的插入,每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。,89,输入数据 53,78,65,17,87,09,81,15,90,二叉搜索树的删除算法,在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链

33、表重新链接起来，同时确保二叉搜索树的性质不会失去。为保证在删除后树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。,91,被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。,53,78,65,17,87,09,23,45,删除45,右子树空,用左子女顶替,53,78,65,17,87,09,23,92,88,53,

34、78,88,17,94,09,23,删除78,左子树空,用右子女顶替,53,94,88,17,09,23,53,78,81,17,94,09,45,删除78,在右子树上找中序下第一个结点填补,23,65,53,81,88,17,94,09,45,23,65,93,二叉搜索树性能分析,对于有 n 个关键码的集合，其关键码有 n!种不同排列，可构成不同二叉搜索树有(棵),2,1,3 1,2,3 1,3,2 2,3,1 3,1,2 3,2,1,94,同样 3 个数据 1,2,3，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。如果输入序列选得不好，会建立起一棵单支树

35、，使得二叉搜索树的高度达到最大。用树的搜索效率来评价这些二叉搜索树。为此，在二叉搜索树中加入外结点，形成判定树。外结点表示失败结点，内结点表示搜索树中已有的数据。这样的判定树即为扩充的二叉搜索树。,95,AVL树 高度平衡的二叉搜索树,AVL 树的定义 一棵 AVL 树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是 AVL 树，且左子树和右子树的高度之差的绝对值不超过1。,96,红黑树（Red-Black Tree）,红黑树是一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。其特性描述如下：特性1：根结点和所有

36、外部结点的颜色是黑色。特性2：从根结点到外部结点的途中没有连续两个结点的颜色是红色。特性3：所有从根到外部结点的路径上都有相同数目的黑色结点。,97,从红黑树中任一结点 x 出发(不包括结点 x)，到达一个外部结点的任一路径上的黑结点个数叫做结点 x 的黑高度，称为结点的阶(rank)，记作 bh(x)。红黑树的黑高度定义为其根结点的黑高度。,红色结点,黑色结点,外部结点,98,另一种等价的定义是看结点指针的颜色。从父结点到黑色子女结点的指针为黑色的，从父结点到红色子女结点的指针为红色的。,此外，搜索树还包括：B树B+树B*树K-D树,99,搜索树的性能,100,STL中的搜索树容器set和map,/有序集合，元素内容为Key，以Key建立搜索树#include/有序字典，元素内容为(Key-Value)键值对，以Key建立搜索树#include using namespace std;set a;map b;内部是使用红黑搜索树实现的，可进行高效的元素增删找操作。,101,set使用范例-点此-点此-,102,