第-5章-树-数据结构课件.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自由树自由树：一棵自由树一棵自由树 Tf 可定义为一个二元组可定义为一个二元组 Tf=(V,E)其中其中V=v1,.,vn 是由是由 n(n0)个元素组成的个元素组成的有限

2、非空集合，称为顶点集合。有限非空集合，称为顶点集合。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 fall 2009DATA STRUCTURESu r 是一个特定的称为根

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

4、n=0时，时，T 称为空树；否则，称为空树；否则，T 是是非空树，记作非空树，记作 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES树的示意图树的示意图（P.187）Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES树的特点 每棵子树的根结点有且仅有一个直接前驱，每棵子树的根结点有且仅有一个直接前驱，但可以有但可以有0个或多个直接后继。个或多个直接后继。0

5、层1层3层2层height=3ACGBDEFKLHMIJ Department of Computer 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();BuildR

6、oot(const Type&value);position 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 2009DATA

7、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 of Computer Scie

8、nce&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 Computer Science&Technology,Nanjing Univ

9、ersity fall 2009DATA STRUCTURES 23-124-1 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES123485679 10 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES log2i+1123485679 10 Department of Computer Science&Technology,Nanjing Unive

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

11、BinTreeNode*LeftChild();/取左子女结点地址 BinTreeNode*RightChild();/取右子女结点地址 int Insert(const Type&item);/插入 int Find(const Type&item)const;/搜索 Type GetData()const;/取得结点数据 BinTreeNode*GetRoot()const;/取根结点地址 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES0 1 2 3 4 5 6 7

12、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 of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES02614300261430 Department of Computer Science&Technology,Na

13、njing University fall 2009DATA STRUCTURESleftChild data rightChilddataleftChildrightChild二叉链表二叉树的链表表示 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESleftChild data parent rightChildparentdataleftChildrightChild三叉链表 Department of Computer Science&Technology,Nanji

14、ng University fall 2009DATA STRUCTURESABCDFEroot AABBCCDDFFEErootroot 二叉链表 三叉链表 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESABCDFErootdata parent leftChild rightChild012345 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESt

15、emplate class BinaryTree;template Class BinTreeNode friend class BinaryTree;private:Type data;BinTreeNode*leftChild;BinTreeNode*rightChild;public:BinTreeNode():leftChild(NULL),rightChild(NULL)Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES BinTreeNode(Type item,

16、BinTreeNode*left=NULL,BinTreeNode*right=NULL):data(item),leftChild(left),rightChild (right)Type GetData()const return data;BinTreeNode*GetLeft()const return leftChild;BinTreeNode*GetRight()const return rightChild;void SetData(const Type&item)data=item;Department of Computer Science&Technology,Nanjin

17、g University fall 2009DATA STRUCTURES void SetLeft(BinTreeNode *L)leftChild=L;void SetRight(BinTreeNode *R)rightChild=R;template class BinaryTree private:BinTreeNode *root;Type RefValue;void CreateBinTree(ifstream&in,BinTreeNode*¤t);Department of Computer Science&Technology,Nanjing University

18、fall 2009DATA STRUCTURES BinTreeNode*Parent(BinTreeNode*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

19、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 of Computer Science&Technology,Nanjing Univer

20、sity fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate void BinaryTree :InOrder(BinTreeNode *subTree)if(subTree!=NULL)InOrder(subTree-leftChild);cout data;InOrder(subTree-rightChild);Department of Computer Science&Technology,Nanjin

21、g University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate void BinaryTree:PreOrder(BinTreeNode *subTree)if(subTree!=NULL)cout data;PreOrder(

22、subTree-leftChild);PreOrder(subTree-rightChild);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 STRUC

23、TUREStemplate void BinaryTree :PostOrder(BinTreeNode *subTree)if(subTree!=NULL)PostOrder(subTree-leftChild);PostOrder(subTree-rightChild);cout data;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate void BinaryTree:InOrder()InOrder(root);template void Binar

24、yTree:PreOrder()PreOrder(root);template void BinaryTree:PostOrder()PostOrder(root);Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES关于树的性质：关于树的性质：1.对于一棵具有对于一棵具有n个结点的树，该树中所个结点的树，该树中所有结点的度数之和为：有结点的度数之和为：2.假定一棵三叉树的结点个数为假定一棵三叉树的结点个数为50，则，则它的最小高度为它的最小高度为 ，最大高，最大高度为度为 。

25、3.在一棵二叉树中，假定度为在一棵二叉树中，假定度为2的结点有的结点有5个，度为个，度为1的结点有的结点有6个，则叶子结点数个，则叶子结点数有有 个个n-14496 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);Departme

26、nt of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES如图所示的二叉树的前序遍历顺序为如图所示的二叉树的前序遍历顺序为:A B C D E G F ABCDEGF Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTU

27、RES template void BinaryTree :CreateBinTree (ifstream&in,BinTreeNode*&subTree)/私有函数:以递归方式建立二叉树。/输入结点值的顺序必须对应二叉树结点前/序遍历的顺序。并约定以输入序列中不可/能出现的值作为空结点的值以结束递归,/此值在RefValue中。例如用“”或用“-1”/表示字符序列或正整数序列空结点。Type item;if(!in.eof()Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURE

28、S in item;/读入根结点的值 if(item!=RefValue)subTree=new BinTreeNode (item);/建立根结点 if(subTree=NULL)cerr “存储分配错!”leftChild);CreateBinTree(in,subTree-rightChild);else subTree=NULL;/封闭叶结点 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES二叉树遍历的非递归算法1 1）后序遍历的非递归算法）后序遍历的非递归算法st

29、ruct STKNode BinTreeNode *ptr;senun tagL,R;/tag=L,表示从左子树退回还要遍历右子树表示从左子树退回还要遍历右子树;/tag=R，表示从右子树退回要访问根结点。，表示从右子树退回要访问根结点。Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES算法思想：算法思想：将栈将栈s初始化，然后令指针初始化，然后令指针p指向二叉树的根结点，指向二叉树的根结点，即即p=T.如果指向根结点的指针不为空，先将如果指向根结点的指针不为空，先将tag置

30、置L；再；再将将tag和根结点一起送入栈中；然后将指针指向该和根结点一起送入栈中；然后将指针指向该结点的左子树根结点；继续遍历。结点的左子树根结点；继续遍历。如果指向根结点的指针为空，则将栈顶存放的数如果指向根结点的指针为空，则将栈顶存放的数据项出栈，有两种情况：据项出栈，有两种情况：若若tag=L,则改变则改变tag的值，将的值，将tag置置R；再把；再把tag和弹出的结点重新入栈和弹出的结点重新入栈；然后将指针指向该结；然后将指针指向该结点的右子树根结点，继续遍历。点的右子树根结点，继续遍历。若若tag=R，则访问弹出的结点，并将弹出的指，则访问弹出的结点，并将弹出的指针置为空针置为空 直

31、到栈为空并且指针为空时，遍历结束。直到栈为空并且指针为空时，遍历结束。Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate void BinaryTree:PostOrder(void(*visit)(BinTreeNode*p)StackstkNode S;stkNode w;BinTreeNode*p=root;/p是遍历指针是遍历指针 do while(p!=NULL)w.ptr=p;w.tag=L;S.Push(w);p=p-leftChild;int

32、continue1=1;/继续循环标记继续循环标记,用于用于R while(continue1&!S.IsEmpty()S.Pop(w);p=w.ptr;switch(w.tag)/判断栈顶的判断栈顶的tag标记标记 case L:w.tag=R;S.Push(w);continue1=0;p=p-rightChild;break;case R:visit(p);break;while(!S.IsEmpty();/继续遍历其他结点继续遍历其他结点 cout endl;Department of Computer Science&Technology,Nanjing University fal

33、l 2009DATA STRUCTURES另一版本实现另一版本实现:void postorder(BinTreeNode *T)stack STKNode s(10);STKNode Cnode;BinTreeNode *p=T;do while(p!=NULL)Cnode.ptr=p;Cnode.tag=L;s.push(Cnode);p=p-leftchild;Cnode=s.pop();p=Cnode.ptr;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESwhile

34、(Cnode.tag=R)coutdata;if(!s.IsEmpty()Cnode=s.pop();p=Cnode.ptr;else return;Cnode.tag=R;s.push(Cnode);p=p-rightchild;while(p!=NULL|!s.IsEmpty()Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaRabcde Department of C

35、omputer Science&Technology,Nanjing University fall 2009DATA STRUCTURESpostorder算法分析算法分析 时间复杂性时间复杂性入、出栈：入、出栈：O(n)访问结点：访问结点：O(n)总的时间复杂度：总的时间复杂度：O(n)空间复杂性空间复杂性O(k),k为树的高度为树的高度 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES二叉树遍历的非递归算法二叉树遍历的非递归算法(cont.)2 2）中序遍历的非递归算

36、法）中序遍历的非递归算法栈中：用以存放待访问的根结点指针栈中：用以存放待访问的根结点指针,以备在以备在访问该结点的左子树之后再访问该结点及其访问该结点的左子树之后再访问该结点及其右子树。右子树。Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES算法思想算法思想 将栈将栈s初始化，令指针初始化，令指针p指向二叉树的根结点，即指向二叉树的根结点，即p=T.如果指向根结点的指针不为空或栈非空，则：如果指向根结点的指针不为空或栈非空，则：(1)如果指向根结点的指针非空，则将根结点指针

37、如果指向根结点的指针非空，则将根结点指针进栈，然后将指针指向该结点的左子树根结点，继续进栈，然后将指针指向该结点的左子树根结点，继续遍历遍历(2)如果指向根结点的指针为空，则将栈顶存放的数如果指向根结点的指针为空，则将栈顶存放的数据项出栈，有两种情况：据项出栈，有两种情况：若从左子树返回，则应该访问当前层根结点，然若从左子树返回，则应该访问当前层根结点，然后将指针指向该结点的右子树根结点，继续遍历；后将指针指向该结点的右子树根结点，继续遍历；若从右子树返回，则表明当前层遍历结束，应该若从右子树返回，则表明当前层遍历结束，应该继续退栈。继续退栈。(3)当指针为空并且栈为空时，遍历结束。当指针为空

38、并且栈为空时，遍历结束。Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESvoid inorder(BinTreeNode *T)stack BinTreeNode*s(10);BinTreeNode *p=T;while(p|!s.IsEmpty()while(p!=NULL)s.push(p);p=p-leftchild;if(!s.IsEmpty()p=s.pop();coutdata;p=p-rightchild;else return;Department of C

39、omputer Science&Technology,Nanjing University fall 2009DATA STRUCTURESacdebaadaa左空左空 退栈退栈访问访问左空左空 退栈退栈访问访问退栈退栈访问访问左空左空ec退栈访问退栈访问cc右空右空 退栈访问退栈访问 栈空结束栈空结束abcde利用栈的中序遍历非递归算法利用栈的中序遍历非递归算法 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESinorder算法分析算法分析 时间复杂性时间复杂性入、出栈：

40、入、出栈：访问结点：访问结点：总的时间复杂度：总的时间复杂度：O(n)O(n)O(n)空间复杂性空间复杂性O(k),k为树的高度为树的高度 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES二叉树遍历的非递归算法二叉树遍历的非递归算法(cont.)3 3）前序遍历的非递归算法）前序遍历的非递归算法需要栈吗？需要栈吗？栈中结点的栈中结点的pop和和push Department of Computer Science&Technology,Nanjing University

41、fall 2009DATA STRUCTURES访问访问p-data后，将后，将p入栈，遍历左子树；遍入栈，遍历左子树；遍历完左子树返回时，栈顶元素历完左子树返回时，栈顶元素p出栈，再先序出栈，再先序遍历遍历p的右子树。的右子树。访问访问p-data后，将后，将p-rchild入栈，遍历左子入栈，遍历左子树；遍历完左子树返回时，栈顶元素树；遍历完左子树返回时，栈顶元素p-rchild出栈，遍历以该指针为根的子树。出栈，遍历以该指针为根的子树。算法思想算法思想两种方法：假设两种方法：假设p是要遍历树的根指针，若是要遍历树的根指针，若p!=NULL Department of Computer S

42、cience&Technology,Nanjing University fall 2009DATA STRUCTUREStemplate void BinaryTree:PreOrder(void(*visit)(BinTreeNode*t)stackBinTreeNode*S;BinTreeNode*p=root;S.Push(NULL);while(p!=NULL)visit(p);/访问结点访问结点 if(p-rightChild!=NULL)S.Push(p-rightChild);/预留右指针在栈中预留右指针在栈中 if(p-leftChild!=NULL)p=p-leftChil

43、d;/进左子树进左子树 else S.Pop(p);/左子树为空左子树为空 ;Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTUREScabcdedcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空栈空栈空结束结束利用栈的前序遍历非递归算法利用栈的前序遍历非递归算法 Department of Computer Science&Technology,Nanjing Universit

44、y fall 2009DATA STRUCTURES遍历顺序遍历顺序abcdef层次序遍历二叉树的算法层次序遍历二叉树的算法n层次序遍历二叉树就是从根结点开始，按层层次序遍历二叉树就是从根结点开始，按层次逐层遍历次逐层遍历 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURESn这种遍历需要使用一个这种遍历需要使用一个先进先出的队列先进先出的队列，在处理上一层时，将其下一层的结点直接在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历进到队列（的队尾）。在上一

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

46、njing 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-leftChild!=NULL)visit(p-leftChild);Q.EnQueue(p-leftChild);if(p-righ

47、tChild!=NULL)visit(p-rightChild);Q.EnQueue(p-rightChild);Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES二叉树的建立 通过算法递归地实现已知一棵二叉树的前序序列和中序序列，可以唯一地确定一棵二叉树；已知一棵二叉树的中序序列和后序序列，可以唯一地确定一棵二叉树；由广义表建立 Department of Computer Science&Technology,Nanjing University fall 2009DAT

48、A STRUCTURES由前序序列和中序序列，建立二叉树的递归算法由前序序列和中序序列，建立二叉树的递归算法private:BinTreeNode *CreateBT(string pres,ins)int Inpos;string Prestemp,Instemp;if(pres.length()=0)T=NULL;else temp=new BinTreeNode;temp-data=pres.ch0;Inspos=0;while(Ins.chInpos!=T-data)Inpos+;Department of Computer Science&Technology,Nanjing Uni

49、versity fall 2009DATA STRUCTURES prestemp=pres(1,Inpos);Instemp=ins(0,Inpos-1);temp-leftchild=CreateBT(prestemp,Instemp);prestemp=pres(Inpos+1,pres.length()-Inpos-1);Instemp=Ins(Inpos+1,pres.length()-Inpos-1);temp-rightchild=CreateBT(prestemp,Instemp);return temp;Department of Computer Science&Techn

50、ology,Nanjing University fall 2009DATA STRUCTURES由广义表建立二叉树由广义表建立二叉树A(B(C,F(H),D(E(,F)广义表广义表 Department of Computer Science&Technology,Nanjing University fall 2009DATA STRUCTURES二叉树对应的广义表有如下规定：二叉树对应的广义表有如下规定：每棵树的根结点作为由子树构成的表的名每棵树的根结点作为由子树构成的表的名字而放在表的前面；字而放在表的前面；每一个结点的左右子树用每一个结点的左右子树用“,”分开，若只分开，若只有右子树