数据结构（c语言描述） 教学课件 作者 库波 第6章 树.ppt

数据结构(C#)主编: (Tree)是n(n≥0)个有限数据元素的集合。当n=0时,称这棵树为空树。在一棵非树T中:(1)有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。(2)若n>1,除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。2相关术语在二叉树中介绍的有关概念在树中仍然适用。除此之外,再介绍两个关于树的术语。(1)有序树和无序树。如果一棵树中结点的各子树丛左到右是有次序的,即若交换了某结点各子树的相对位置,则构成不同的树,称这棵树为有序树;反之,则称为无序树。(2)森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念,但在数据结构中,树和森林只有很小的差别。任何一棵树,删去根结点就变成了森林。:1、Root():求树的根结点,如果树非空,返回根结点,否则返回空;2、Parent(t):求结点t的双亲结点。如果t的双亲结点存在,返回双亲结点,否则返回空;3、Child(t,i):求结点t的第i个子结点。如果存在,返回第i个子结点,否则返回空;4、RightSibling(t):求结点t第一个右边兄弟结点。如果存在,返回第一个右边兄弟结点,否则返回空;5、Insert(s,t,i):把树s插入到树中作为结点t的第i棵子树。成功返回true,否则返回false;6、Delete(t,i):删除结点t的第i棵子树。成功返回第i棵子树的根结点,否则返回空;7、Traverse(TraverseType):按某种方式遍历树;8、Clear():清空树;9、IsEmpty():判断树是否为空树。如果是空树,返回true,否则返回false;10、GetDepth():求树的深度。如果树不为空,返回树的层次,否则返回0。(BinaryTree)是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。二叉树的性质性质1一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。性质2一棵深度为k的二叉树中,最多具有2k-1个结点。性质3对于一棵非空的二叉树,如果叶子结点数为n0,度数为2的结点数为n2,则有:n0=n2+1。性质4具有n个结点的完全二叉树的深度k为[log2n]+1。性质5对于具有n个结点的完全二叉树,如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号,则对于任意的序号为i的结点,有:(1)如果i>1,则序号为i的结点的双亲结点的序号为i/2(“/”表示整除);如果i=1,则序号为i的结点是根结点,无双亲结点。(2)如果2i≤n,则序号为i的结点的左孩子结点的序号为2i;如果2i>n,则序号为i的结点无左孩子。(3)如果2i+1≤n,则序号为i的结点的右孩子结点的序号为2i+1;如果2i+1>n,则序号为i的结点无右孩子。