《软件技术基础》- 数据结构(树形结构)

1、讲 课 人：刘 伟 电子邮件：bme_liuwei bme.liuwei 电 话办 公 室：教二南楼328室,软件技术基础,数据结构 树形结构,本章基本内容与要求,基本内容 树的基本概念及存储结构 二叉树概念 二叉树的存储结构 二叉树的操作 二叉排序树,树形结构在日常生活和计算机科学中无处不在。,日常生活：家谱、机关结构图 计算机科学：目录树、计算机游戏（如 DOOM等射击类游戏）,一、树的基本概念,1.1 树的定义,1定义,树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则：,（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前

2、驱； （2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,树的基本概念及存储结构,西汉皇帝谱系树,程序调用自身的编程技巧称为递归（ recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常 把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解， 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地

3、 减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。 用递归思想写出的程序往往十分简洁易懂。 注意： (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。,A,A,B,C,D,I,H,G,F,E,J,K,L,M,a,）空树,b,）仅含有根结点的树,c,）,含有多个结点的树,图,4,-,1,树的示意图,树的基本概念及存储结构,在图4-1c中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图4-2，并且可以进一步分解T0，T1，T2 。,2树的逻辑结构描述,一棵树的逻辑结构可以用二元组描述为

4、： tree =(T,R) T=Ti1in;n0,Tielemtype R=r 其中，n为树中结点个数，若 n=0，则为一棵空树， n 0时称为一棵非空树，而关系 r 应满足下列条件：,（1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。,例如，对图4-1(c )的树结构,可以二元组表示为： T=A，B，C，D，E，F，G，H，I，J，K，L，M R=r r=(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(

5、H,M),1.2 基本术语,1. 结点 指树中的一个数据元素，一般用一个字母表示。 A,B,C,2. 度 一个结点包含子树的数目，称为该结点的度。A节点的度为3,3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结点。 图中4-1C中：J,K,L,F,G,M,4. 孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。 B、C、D是A节点孩子,5. 双亲结点 若结点X有子女Y，则X为Y的双亲结点。 A 是节点B、C、D双亲,6. 祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的祖先。 M的祖先有A，D ，H 。,7. 子孙结点 某一结点的子女及子

6、女的子女都为该结点子孙。,8. 兄弟结点 具有同一个双亲的结点，称为兄弟结点。 B、C、D为兄弟,9. 分枝结点 除叶子结点外的所有结点，为分枝结点，也叫非终端结点。 B,C,D,E,H为分枝节点,10层数 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。,11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。,12. 树的度 树中结点度的最大值称为树的度。,13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。,14. 无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。,

7、15森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,森林示例,图例,Property: (边数) = (结点数) - 1,为什么？,树中除了根结点外每个结点有且仅有一个父结点，子结点和父结点间有且仅有一条边。,1.3 树的存储结构,通常采用链式存储 eg.采用同构型存储，每个节点按照树的度定义指针域个数,二、二叉树,2.1 二叉树的定义,1二叉树的定义,和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个孩子，或者说，

8、在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图4-5 。,二叉树概念,(a) 空二叉树,A,A,B,A,B,A,C,B,(b) 根和空的左右子树,(c) 根和左子树,(d) 根和右子树,(e) 根和左右子树,图4.5 二叉树的5种形式,二叉树的5种基本形态，图(c) 和图（d）是不同的两棵二叉树。,1. 满二叉树 ：二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。,2. 完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全

9、二叉树。从完全二叉树定义可知：,2.2 两种特殊的二叉树,结点的排列顺序遵循从上到下、从左到右的规律。 满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。 满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。,深度为4的满二叉树和完全二叉树如图4-6所示。,非完全二叉树,2.3 二叉树的性质,性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k0）。 可以用数学归纳法证明之。,性质2 深度（高度）为k的二叉树最大结点数为2k-1（k0）。,证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大

10、结点数应为每一层最大结点数之和。既为 20+21+2k-1=2k-1。,性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。,证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，二叉树的孩子结点数为 n0*0+n1*1+n2*2 ，加上根结点后，总的结点数：n=n0*0+n1*1+n2*2+1，因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。,性质4 具有n个结点的完全二叉树高度为log2（n+1）。 (注意x表示对x取整。),证明：可根据性质2

11、推出。,性质5 如果对一棵有n个结点的满二叉树和完全二叉树按从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，对任一结点j（11，则其双亲是结点j/2。（取整是直接取整，舍去小数部分） 如果2jn，则结点j为分支结点，其左子结点是2j；否则，该结点为叶子结点，无左子树。 如果2j1n，则结点j为分支结点，其右子结点是结点2j1；否则，该结点为叶子结点，无右子树。,深度为5的二叉树至多有( )个结点。 A.16 B.32 C.31 D.10,【例题1】,【例题2】,2.4 树、森林和二叉树的转换,可以分为三步： （1）连线 指相邻兄弟之间连线。,（2）抹线 指抹掉双亲与除左孩子外其它

12、孩子之间的连线。,（3）旋转 只需将树作适当的旋转。（顺时针旋转45）,具体实现过程见图-25。,1树转换成二叉树,2森林转换成二叉树,（1） 将森林中每一棵树分别转换成二叉树（前2步）,（2）将各二叉树的根结点视为兄弟从左至右连在一起 (3)顺时针转45度,A,E,G,B,C,D,F,H,I,G,H,I,A,B,C,D,F,E,左孩子,右兄弟,【例题3】,【例题4】,三、 二叉树的存贮结构,3.1顺序存贮结构,将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图6-7给出了顺序存贮形式。,对于一棵二叉树,若采

13、用顺序存贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。因此，对于非完全二叉树，宜采用链式存储结构。,3.2二叉链表存贮结构,（1）二叉链表表示 将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。,二叉链表中一个结点可描述为:,对于图-7所示二叉树,用二叉链表形式描述见图4-8。,1. 概念 二叉树的遍历是指按照一定的次序访问树中所有结点，并且每个结点仅被访问一次。它是最基本的运算，是二叉树中其他所有运算的基础。在二叉树中，左子树和右子树是有严格区别的，因此在遍历一棵非空二叉树时，根据访问根结点，遍历左子树和遍历右子树之间

14、的先后关系，可以得到6种遍历方法。若按先左后右的原则，则通常使用下面三种遍历方法，见表4-1。,四、二叉树的操作,4.1 二叉树遍历,表4-1 遍历方法表,层次序遍历：按照结点的层次，依次遍历每一层次的所有结点。,a) b),4-11b： 先序遍历：ABCDEFG 中序遍历：CBDAEGF 后序遍历：CDBGFEA 层次遍历：ABECDFG,4-11a： 先序遍历：ABDC 中序遍历：BDAC 后序遍历：DBCA 层次遍历：ABCD,4.2.2 二叉树遍历算法的实现,2.算法实现 链式存储结构二叉树的定义： struct bitree elemtype data; / elemtype：结点数

15、据类型 bitree *lchild; bitree *rchild; ;,void preorde (bitree *root) if(root!=NULL) cout data lchild); preorde (root - rchild); ,（1）先序遍历二叉树算法,中序遍历也是一个递归过程，对于一棵二叉树，其过程为：1）中序遍历左子树，2）访问根结点，3）中序遍历右子树，直到二叉树为空时退出。 算法描述如下：,（2）中序遍历二叉树算法,void inorder(bitree *root) if(root != NULL) inorder(root - lchild); cout d

16、ata rchild); ,同样是一个递归过程，对于一棵二叉树，其过程为：1）后序遍历左子树，后序2）后序遍历右子树，3）访问根结点，直到二叉树为空时退出。 算法描述如下：,(3) 后序遍历,void postorder(bitree *root) if(root != NULL) postorder(root - lchild); postorder(root - rchild); cout data a; if(a!=0) bitree *q=new bitree; q-data=a; /生成根结点 q-lchild= createtree ( ); /构造左子树 q-rchild= cr

17、eatetree ( ); /构造右子树 return q; Else return NULL;,void main() bitree *head=NULL; head= createtree ( ); preorder (head); coutn; postorder(head); cout data ; /复制根结点 dest-lchild=copy(sour-lchild); /复制左子树 dest-rchild=copy(sour-rchild); /复制右子树 return dest; ,2. 确定树的高度,二叉树的高度为二叉树中结点层次的最大值，因此从上一层的根节点开始往下递推可得

18、到树的高度。算法如下：,void treehigh(bitree *p,int ,对二叉树进行遍历，判断被访问的结点是否叶子结点，若是叶子结点，则将叶子数加 1。算法如下：,3. 统计二叉树中叶子结点个数,/先序遍历法求叶子结点，count存储叶子结点个数 void countleaf(bitree *root,int ,void deletepostorder(bitree *root,int ,4. 删除整棵树,要删除一棵二叉树，需要删除其所有结点。可以通过后序遍历在访问一个结点时，将其删除。也就是说先删除左子树，然后右子树，最后删除根。,问题：能否采用先序或者中序的方法删除二叉树？,二叉

19、排序树或是一棵空树，或是一棵满足以下特征的非空二叉树： 1) 每个元素有一个关键值； 2) 根节点左子树的关键值（如果有的话）小于根节点的关键值； 3) 根节点右子树的关键值（如果有的话）大于或等于根节点的关键值； 4) 根节点的左右子树也都是二叉排序树。,5.1 定义,如果对二叉排序树进行中序遍历，可以得到一个由小到大的有序序列。如图二叉排序树得到的中序遍历为：10,12,13,18,22。,五、二叉排序树 二叉排序树是一种特殊的二叉树，可以作为排序和查找的方法之一。,算法思想： 对于一组关键字无序的记录，构造其相应的二叉排序树的方法是：从一棵空的二叉排序树开始，每当读入一个记录就生成一个结

20、点，然后按关键字值的大小插入到当前的二叉排序树之中；当所有记录的结点都已插入二叉排序树中时便构造完毕。,插入操作是构造二叉排序树的关键操作，要保证在一棵二叉排序树中插入一个结点之后，仍然满足二叉排序树的定义。,5.2 二叉排序树的生成操作,对任意的一组数据元素X1，X2，Xn，要生成一棵二叉排序树的过程为： 1）令X1为二叉排序树的根节点。 2）若X2data=a; q-lchild= NULL; q-rchild= NULL; else if (adata ) q-lchild= InsertTree (q-lchild,a); /插入左子树 else q-rchild= InsertTree (q-rchild,a); /插入右子树 return q; ,插入算法思想： 如果在 q 指向的二叉排序树中，插入数据 a 的算法如下： 如果 a 已在二叉排序树中，即检索成功就不必插入，否则插入结点作为新的叶结点，并成为检索路径上最后一个结点的左孩子或右孩子。为了实现这一插入过程，在二叉排序树非空时需要知道检索路径上的最后一个结点位置，才能够准确地把插入结点作为左孩子或右孩子插入二叉检索树中；为此，需要在检索过程中设一指针变量记下当前结点的前趋（即双亲）结点位置。,5.3 二叉排序树的查找,假设需要在二叉排序树上查找关键值为k的元素，先从根开始。 如