d树和森林的概念ppt课件

1、 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES第第 5章章 树树 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES树和森林的概念u两种树：自在树与有根树。两种树：自在树与有根树。 u自在树：自在树：u 一棵自在树一棵自在树 Tf 可定义为一个二元组可定义为一个二元组u Tf = (V, E) u其中其中V = v1, ., vn 是由是由

2、 n (n0) 个元素组个元素组成的有限非空集合，称为顶点集合。成的有限非空集合，称为顶点集合。E = (vi, vj) | vi, vj V, 1i, jn 是是n-1个序对的集合，称为边个序对的集合，称为边集合，集合，E 中的元素中的元素 (vi, vj称为边或分支。称为边或分支。 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES自在树 Department of Computer Science & Technology, Nanjing University

3、fall 2009DATA STRUCTURESu r 是一个特定的称为根(root)的结点，它只需直接后继，但没有直接前驱；u根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树。u每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。00n,T,.,T,Tr,n,Tm21u有根树：有根树：u一棵有根树一棵有根树 T，简称为树，它是，简称为树，它是n (n0) 个结个结点的有限集合。当点的有限集合。当n = 0时，时，T 称为空树；否那么，称为空树；否那么，T 是非空树，记作是非空树，记作 Departmen

4、t of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES树的表示图树的表示图P.187 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES树的特点 每棵子树的根结点有且仅有一个直接前驱，每棵子树的根结点有且仅有一个直接前驱，但可以有但可以有0个或多个直接后继。个或多个直接后继。0层1层3层2层height= 3ACGBDEFKLHMIJ Department of Co

5、mputer Science & Technology, Nanjing University fall 2009DATA STRUCTURES0层层1层层3层层2层层height= 3ACGBDEFKLHMIJ术语术语 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTUREStemplate class Tree public: Tree ( ); Tree ( ); position Root ( ); BuildRoot ( const Type& value ); p

6、osition FirstChild ( position p ); position NextSibling ( position p ); position Parent ( position p ); Type GetData ( position p ); int InsertChild ( const position p, const Type &value ); int DeleteChild ( position p, int i ); Department of Computer Science & Technology, Nanjing University fall 20

7、09DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESLLRR Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department

8、of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES满二叉树满二叉树 完全二叉树完全二叉树 层次层次h，叶结点仅在，叶结点仅在 两层出两层出现现 对任一结点，假设其右子树的高度对任一结点，假设其右子树的高度为为k，那么其左子树的高度是，那么其左子树的高度是 h和和h-1 k or k+1 Department of C

9、omputer Science & Technology, Nanjing University fall 2009DATA STRUCTURES23-124-1 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES123485679 10 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES123485679 10 Department of Co

10、mputer Science & Technology, Nanjing University fall 2009DATA STRUCTUREStemplate class BinaryTree public: BinaryTree ( ); /构造函数构造函数 BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); /构造以构造以item为根，为根，lch和和rch为左、为左、右右 /子树的二叉树子树的二叉树 int IsEmpty ( ); /判二叉树空否？判二叉树空否？ BinTreeNode * Parent (

11、); /双亲双亲 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES BinTreeNode * LeftChild ( ); /取左子女结点地址 BinTreeNode * RightChild ( ); /取右子女结点地址 int Insert ( const Type& item ); /插入 int Find ( const Type &item ) const; /搜索 Type GetData ( ) const; /获得结点数据 BinTreeNode *

12、GetRoot ( ) const; /取根结点地址 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES0 1 2 3 4 5 6 7 8 9 完全二叉树0137894562 顺序表示 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES0 1 2 3 5 6 7 8 9 11 13普通二叉树的顺序表示130265378111 Department

13、 of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES02614300261430 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESleftChild data rightChilddataleftChildrightChild二叉链表二叉树的链表表示 Department of Computer Science & Technology, Nanjing Unive

14、rsity fall 2009DATA STRUCTURESleftChild data parent rightChildparentdataleftChildrightChild三叉链表 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCDFEroot AABBCCDDFFEErootroot 二叉链表 三叉链表 Department of Computer Science & Technology, Nanjing University fall 2009D

15、ATA STRUCTURESABCDFErootdata parent leftChild rightChild012345 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTUREStemplate class BinaryTree;template Class BinTreeNode friend class BinaryTree;private: Type data; BinTreeNode * leftChild; BinTreeNode * rightChild; p

16、ublic: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES BinTreeNode ( Type item, BinTreeNode *left = NULL, BinTreeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) Type GetData ( ) co

17、nst return data; BinTreeNode * GetLeft ( ) const return leftChild; BinTreeNode * GetRight ( ) const return rightChild; void SetData ( const Type& item ) data = item; Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES void SetLeft ( BinTreeNode * L ) leftChild =

18、L; void SetRight ( BinTreeNode * R ) rightChild = R; ;template class BinaryTree private: BinTreeNode *root; Type RefValue; void CreateBinTree ( ifstream& in, BinTreeNode * & current ); Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES BinTreeNode * Parent ( Bin

19、TreeNode * subTree, BinTreeNode * current); int Insert (BinTreeNode * & subTree, const Type &item); /插入 void Traverse (BinTreeNode *subTree, ostream &out) const /遍历 int Find (BinTreeNode *subTree, const Type &item) const/搜索 void destroy (BinTreeNode * subTree); /删除 Department of Computer Science & T

20、echnology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fal

21、l 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department

22、of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES LRV Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technol

23、ogy, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTUREStemplate void BinaryTree : InOrder ( ) InOrder ( root );template void BinaryTree : PreOrder ( ) PreOrder ( root );template void BinaryTree : PostOrder ( ) PostOrde

24、r ( root ); Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES关于树的性质：关于树的性质：1. 对于一棵具有对于一棵具有n个结点的树，该树中一个结点的树，该树中一切结点的度数之和为：切结点的度数之和为： 2. 假定一棵三叉树的结点个数为假定一棵三叉树的结点个数为50，那，那么它的最小高度为么它的最小高度为 ，最大，最大高度为高度为 。3. 在一棵二叉树中，假定度为在一棵二叉树中，假定度为2的结点有的结点有5个，度为个，度为1的结点有的结点有6个，那么叶子结点

25、个，那么叶子结点数有数有 个个n-14496 n2+1=n0 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTUREStemplate int BinaryTree : Count ( BinTreeNode * t ) const if ( t = NULL ) return 0; else return 1 + Count ( t-leftChild ) + Count ( t-rightChild ); Department of Computer Science &

26、Technology, Nanjing University fall 2009DATA STRUCTURES遍历顺序遍历顺序abcdef层次序遍历二叉树的算法层次序遍历二叉树的算法n层次序遍历二叉树就是从根结点开场，按层层次序遍历二叉树就是从根结点开场，按层次逐层遍历次逐层遍历 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESn这种遍历需求运用一个先进先出的队列，这种遍历需求运用一个先进先出的队列，在处置上一层时，将其下一层的结点直接在处置上一层时，将其下一层的结点

27、直接进到队列的队尾。在上一层结点遍历进到队列的队尾。在上一层结点遍历完后，下一层结点正益处于队列的队头，完后，下一层结点正益处于队列的队头，可以继续访问它们。可以继续访问它们。n算法是非递归的。算法是非递归的。 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESabcdeQa访问访问a, 进队进队Qa出队出队访问访问b, 进队进队访问访问c, 进队进队bcQb出队出队访问访问d, 进队进队cdQc出队出队访问访问e, 进队进队deQd出队出队eQe出队出队 Depart

28、ment of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES层次序遍历的非递归算法template void BinaryTree:levelOrder (void (*visit) (BinTreeNode *t) if (root = NULL) return; QueueBinTreeNode * Q; BinTreeNode *p = root; visit (p); Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if (p-l

29、eftChild != NULL) visit (p-leftChild); Q.EnQueue (p-leftChild); if (p-rightChild != NULL) visit (p-rightChild); Q.EnQueue (p-rightChild); ; Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES二叉树的建立 经过算法递归地实现 知一棵二叉树的前序序列和中序序列，可以独一地确定一棵二叉树； 知一棵二叉树的中序序列和后序序列，可以独一地确定

30、一棵二叉树； Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES5.5 线索二叉树 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES两种方法：两种方法：1原有二叉树的构

31、造中，添加两个链域；原有二叉树的构造中，添加两个链域；2利用空链域利用空链域 假设结点有左孩子，那么其假设结点有左孩子，那么其leftchild指示其左孩子；否那么指指示其左孩子；否那么指示其前驱示其前驱假设结点有右孩子，那么其假设结点有右孩子，那么其rightchild指示其右孩子；否那么指示其右孩子；否那么指示其后继指示其后继设置两个标志：设置两个标志：LeftThread RightThread Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Departme

32、nt of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES中序线索化二叉树的例子中序线索化二叉树的例子 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES原来的原来的线索化线索化二叉树二叉树成为表成为表头结点头结点的左子的左子树树 Department of Computer Science & Technology, Nanjing University fall 2

33、009DATA STRUCTUREStemplate class ThreadNode friend class ThreadTree;private: int leftThread, rightThread; ThreadNode *leftChild, *rightChild; Type data;public: ThreadNode ( const Type item ) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) ;template class ThreadTre

34、e; Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTUREStemplate class ThreadTree private: ThreadNode * root; /根根 InThread ( ThreadNode * current, ThreadNode * &pre ); /建树建树public: ThreadTree ( ) : root (NULL) ; /构造函数构造函数 ThreadNode * First ( ThreadNode * current )

35、; ThreadNode * Last ( ThreadNode * current ); Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES ThreadNode * Next ( ThreadNode * current ); ThreadNode * Prior ( ThreadNode * current ); Department of Computer Science & Technology, Nanjing University fall 2009DAT

36、A STRUCTURESif (current-rightThread =1) 后继为后继为current-rightChildelse /current-rightThread != 1 后继为当前结点右子树后继为当前结点右子树 的中序下的第一个结点的中序下的第一个结点 最左下最左下ABDECFHIKGJ Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES if (current-leftThread=1) 前驱为前驱为current-leftChild else /

37、current-leftThread=0 前驱为当前结点左子树前驱为当前结点左子树 中序下的最后一个结点中序下的最后一个结点 最右下最右下 ABDECFHIKGJL Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCDEFG叶叶结结点点分支结点分支结点根根结结点点广义表广义表原子结点原子结点子表结点子表结点表头结点表头结点 Department of Computer Science & Technology, Nanjing University fall 20

38、09DATA STRUCTURESABCDEFGdataparentA B C D E F G-1 0 0 0 1 1 3-1 0 0 0 1 1 30 1 2 3 4 5 6 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCDEFGABCDEFG 每个结点包含的指针个数相等，等于树的度每个结点包含的指针个数相等，等于树的度degree data child1child2 child3childd Department of Computer Science &

39、 Technology, Nanjing University fall 2009DATA STRUCTURESn子女链表表示 无序树情形链表中各结点顺序恣意，有序树必需自左向右链接各个子女结点。ABCDEFG123456ABCDEFG0123456 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES datafirstChild nextSiblingABCDEFGABCDGFE Department of Computer Science & Technology,

40、 Nanjing University fall 2009DATA STRUCTURES对于一棵树，按照以下规那么构造相应的二叉树：对于一棵树，按照以下规那么构造相应的二叉树：加线：各兄弟之间加一连线加线：各兄弟之间加一连线抹线：对任何结点，除了最左子树外，抹线：对任何结点，除了最左子树外，抹掉该结点与其他子树之间的抹掉该结点与其他子树之间的“父子关系父子关系调整：以树的根结点作为二叉树的根结调整：以树的根结点作为二叉树的根结点，树根与最左子树之间的关系点，树根与最左子树之间的关系“父左子，结父左子，结点按层次陈列点按层次陈列转换后的二叉树是独一的，并且：转换后的二叉树是独一的，并且：根结点只

41、需左子树根结点只需左子树左子女是原树中的最左的孩子，右孩子是它左子女是原树中的最左的孩子，右孩子是它在原来树中的下一个兄弟在原来树中的下一个兄弟树与二叉树的转换 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES森林：森林：树的有限集合树的有限集合 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTUREST1 T2 T3AFHBC DGIJEK3 棵树

42、的森林棵树的森林T1 T2 T3AFBCDEGHIKJ各棵树的二叉树表示ABCEDHIKJFG森林的二叉树表示 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCDEFG Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCDEFGABCEDGF树的先根次序遍历 Department of Computer Science & Tech

43、nology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCDEFGABCEDGF树的后根次序遍历 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nan

44、jing University fall 2009DATA STRUCTURESABCEDGFABCDEFG Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES current = Qu.getFront( ); Qu.DeQueue ( ); visit ( ); /队列中取一个并访问之 cu

45、rrent = current -firstChild ;/待访问结点的子女结点进队列 while ( current != NULL ) Qu.EnQueue ( current ); current = current-nextSibling; current = p; /恢复算法开场的当前指针 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES森林的先序遍历森林的先序遍历等价于它转换成等价于它转换成的二叉树的先序的二叉树的先序遍历。遍历。 森林的遍历 Depart

46、ment of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES(2)后根次序遍历的规那么假设森林 F = ，前往；否那么后根遍历森林 F 第一棵树的根结点的子树森林T11, , T1k；访问森林的根结点 r1；后根遍历森林中除第一棵树外其他树组成的森林T2, ., Tm。 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCEDHIKJFG 对应二叉树中序遍历的结果

47、。T1 T2 T3AFHBC DGIJEK森林的后根次序遍历结果森林的后根次序遍历结果:BCEDA GF KIJH Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURESABCEDHIKJFGAFHBCDGIJEKT1 T2 T3AFHBC DGIJEK Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES5.7 堆 ( Heap ) Departme

48、nt of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES090987877878454565653131532323531717 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES关于堆关于堆完全二叉树完全二叉树:一切非叶结点的值均不大于一切非叶结点的值均不大于(或不或不小于小于)其左、右孩子结点的值其左、右孩子结点的值 Department of Computer

49、Science & Technology, Nanjing University fall 2009DATA STRUCTURES 判别以下序列能否是堆？ 100,90,80,60,85,75,20,25,10,70,65,50 int MaxHeapSize; /最多允许元最多允许元素个数素个数 void FilterDown ( int i, int m ); /从从 i 到到m自顶向下进展调整成为最自顶向下进展调整成为最小堆小堆 void FilterUp ( int i ); /从从 i 到到0自底向上进展调整成为最小堆自底向上进展调整成为最小堆public: MinHeap ( in

50、t sz ); /构造函数构造函数 : 建立空堆建立空堆 MinHeap ( Type arr , int n ); /构造函构造函数数 MinHeap ( const MinHeap& R ); MinHeap ( ) delete heap; int Insert ( const Type& x ); /插入插入 int Remove ( Type& x ); /删除删除 int IsEmpty ( ) const /判堆空否判堆空否 return CurrentSize = 0; int IsFull ( ) const /判堆满否判堆满否 return CurrentSize = Ma

51、xHeapSize; void MakeEmpty ( ) CurrentSize = 0; Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES堆的建立建立空堆建立空堆根据给定数组中的数据和大小根据给定数组中的数据和大小,建立堆对象建立堆对象template MinHeap :MinHeap ( int maxSize ) /根据给定大小根据给定大小maxSize,建立堆对象建立堆对象MaxHeapSize = DefaultSize maxSize ? maxSize

52、 : DefaultSize; /确定堆的大小确定堆的大小 heap = new Type MaxHeapSize; if ( heap = NULL ) cerr “存储分配错存储分配错! endl; exit(1); CurrentSize = 0; 建建立立空空堆堆 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES 根据给定数组中的数据和大小根据给定数组中的数据和大小, ,建立堆对象建立堆对象 template MinHeap : template MinHea

53、p : MinHeap ( Type arr , int n ) MinHeap ( Type arr , int n ) MaxHeapSize = DefaultSize n ? n : DefaultSize; heap = new Type MaxHeapSize; if ( heap = NULL ) cerr “存储分配错! endl; exit(1); for ( int i = 0; i = 0 ) /从下到上逐渐扩展从下到上逐渐扩展,构成堆构成堆 FilterDown ( currentPos, CurrentSize-1 ); /从从currentPos开场开场,到到Cur

54、rentSize止止, /调整调整 currentPos-; i5317780923456587 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES5317780923456587icurrentPos = i = 3 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES根本算法思想：根本算法思想： FilterDown ( int i, int

55、n) 假设结点假设结点i左子女的关键码小于右子女的关键左子女的关键码小于右子女的关键码，那么沿码，那么沿i的左分支进展调整，否那么沿的左分支进展调整，否那么沿i的的右分支进展调整，令右分支进展调整，令j为参与调整的子女；为参与调整的子女； 假设假设Ri.keyRj.key,那么两结点对调位置，那么两结点对调位置，把关键码小的结点上浮，把关键码小的结点上浮，i=j,j=2i+1假设假设Ri.key=Rj.key,那么算法终止那么算法终止 Department of Computer Science & Technology, Nanjing University fall 2009DATA ST

56、RUCTURES5317780923456587icurrentPos = i = 3currentPos = i = 2i53177809234565875317780923456587icurrentPos = i = 15317780923456587i5317780923456587icurrentPos = i = 05317780923456587i095317780923456587i5317780923456587i17 Department of Computer Science & Technology, Nanjing University fall 2009DATA S

57、TRUCTUREStemplate void MinHeap : FilterDown ( int start, int EndOfHeap ) int i = start, j = 2*i+1; / j 是是 i 的左子女的左子女 Type temp = heapi; while ( j = EndOfHeap ) if ( j heapj+1 ) j+; /两子女中选小两子女中选小者者 if ( temp = heapj ) break; else heapi = heapj; /下面的上浮下面的上浮 i = j; j = 2*j+1; /向下滑动向下滑动 heapi = temp; De

58、partment of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES 最小堆的插入1778092345658711在堆中插入新元素1153ij53177809234565871123ji Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES1778094565871153ji2317531178092345658723ji Department of Computer

59、Science & Technology, Nanjing University fall 2009DATA STRUCTURES/在堆中插入新元素 x if ( CurrentSize = MaxHeapSize ) /堆满 cerr 堆已满 endl; return 0; heapCurrentSize = x; /插在表尾 FilterUp (CurrentSize); /向上调整为堆 CurrentSize+; /堆元素增一 return 1;template int MinHeap : Insert ( const Type &x ) Department of Computer S