数据结构课件树和叉树.ppt

树型结构不同与线性表、栈、队列、串和广义表结构，是一类重要的非线性数据结构，其中以树和二叉树最为常用。树形结构反映了元素之间的层次关系和分支关系，它非常类似于自然界中的树。;树(tree)结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。;树是由n(n≥0)个结点组成的有限集。在任意一棵非空树T中：;A;*;;*;二叉树(binarytree)是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。;二叉树是一个有限的结点的集合，该集合或者为空，或者由满足以下两个条件的树型结构组成

⑴每个结点的度都不大于2；

⑵每个结点的孩子结点次序不能任意颠倒。;①空二叉树；;1;性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。;性质2：深度为k的二叉树至多有2k－1个结点（k≥1）。;性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2+1。;为便于介绍下面两个二叉树性质，先了解满二叉树(fullbinarytree)和完全二叉树(completebinarytree)的概念。;1;1;如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至右。由此可以引出完全二叉树的定义。;1;1;性质4：具有n个结点的完全二叉树的深度为

?log2n?+1（?x?表示不大于x的最大整数）;性质5：如果对一棵有n个结点的完全二叉树（此二叉树的深度为?log2n?+1）的结点按照层次编号（从第1层到第?log2n?+1层，每层从左到右），那么对任一结点i（1≤i≤n），有;?i/2?;二叉树和其他数据结构一样也分顺序存储结构和链式存储结构；而链式存储结构又分二叉链表存储结构和三叉链表存储结构。;二叉树的顺序存储结构就是用一组地址连续的存储单元来存放一棵二叉树的所有结点元素。;A;1;1;;顺序存储结构仅适用于完全二叉树。如???存储一般二叉树，则会造成存储空间的浪费，这时就需要使用二叉树的链式存储结构。

二叉树的链式存储结构主要是设计结点结构。根据结点结构的不同，又可以分为二叉链表存储结构和三叉链表存储结构。;(1)二叉链表存储结构;A;A;(2)三叉链表存储结构;A;;在二叉树的很多应用中，常要求在二叉树中查找某些指定的结点或对二叉树中全部结点逐一进行某种操作，这就需要依次访问二叉树中的结点，即遍历二叉树。;遍历二叉树的操作定义;

设以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，若限定先左子树后右子树，则只有前三种方案，分别称之为先根（序）遍历DLR、中根（序）遍历LDR和后根（序）遍历LRD。遍历左子树和右子树的规律和遍历整个二叉树的规律相同，因而这三种遍历都具有递归性。;(1)先根（序）DLR遍历二叉树的操作定义;(2)中根（序）LDR遍历二叉树的操作定义;(3)后根（序）LRD遍历二叉树的操作定义;例;遍历二叉树可以根据二叉树的递归定义写出递归算法。分为：;1.先序遍历二叉树的递归算法;-;2.中序遍历二叉树的递归算法;-;3.后序遍历二叉树的递归算法;-;intPrintElement(DataTypee){

printf(e); //输出数据元素e的值

returnOK; //在实用时，再加上格式串

}//PrintElement;遍历二叉树是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，比如：对于一棵已知树可以求结点的双亲，求结点的孩子结点，判定结点所在的层次等；反之，给定一棵二叉树的遍历序列结点，可创建二叉树的存储结构。;例如，如果按照先序序列建立二叉树的二叉链表结构，对下图所示二叉树，可以按照“扩展先序遍历序列”读入字符，即可以