辛运帏全套配套课件数据结构与算法 DSChapter05.ppt

《辛运帏全套配套课件数据结构与算法 DSChapter05.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章树型结构5.1树5.2二叉树5.3树、森林与二叉树的关系5.1.1树的基本概念树一棵树（tree）T是由一个或一个以上的结点组成的有限集，其中有一个特定的结点R称为树T的根结点。在集合中除根结点R外，其余的结点可被划分为n个不相交的子集T1、T2、…、Tn，其中每个子集都是树，并且其相应的根结点R1、R2、…、Rn是R的子结点。子集Ti（i=1,2,…,n）称为树T的子树（subtree）。注意：定义中规定一棵树至少要有一个结点，若集合中只有一个结点，那么它就是只有根结点而没有任何子树的树。树的图形表示法如图5.2就表示一棵含有A、B

2、、C、D、E、F、G、H、I、J共10个结点的树。其中A为根结点，{B、E、F}，{C、G}和{D、H、I、J}构成根结点A的三棵子树，B、C、D分别是这三棵子树的根。图5.1树的图形表示树的凹入表示法这种表示法适合于将树型结构按行显示在屏幕上或打印在纸上。缩入最少的结点表示树根（如结点A），它的各子树的根结点缩入多些而且要对齐在同一列上（如结点B、C、D）。各结点后面的阴影部分表示可以放与该结点有关的信息。图5.2树的凹入表示法术语结点的度结点所拥有的子树的个数；叶结点（终端结点）树中度为0的结点；分支结点树中度不为0的结点，也即树中除叶

3、结点之外的所有结点；术语结点的孩子和双亲结点的子树的根称为结点的孩子；反过来，该结点称为孩子结点的双亲；兄弟结点同一个双亲的孩子彼此称为兄弟结点；结点的层次树的根结点为第一层，根的孩子为第二层，依此类推。术语树的深度（高度）树中结点的最大层次数。例如图5.2所示的树的深度为3，因为E、F、G、H、I、J等结点都在第三层，而没有第四层的结点。森林m(m≥0)棵互不相交的树的集合。对树中每个结点来说，其子树的集合即为森林。如在图5.2所示的树中，将根结点A砍掉，其三棵子树就构成一个含三棵树的森林。5.1.2树的抽象数据类型与线性表的定义类似，我

4、们先给出树中结点GTNode的定义，然后再定义树的类GenTree：classGTNode{public:GTNode(constELEM);~GTNode();ELEMvalue();boolisLeaf();GTNode*parent();GTNode*leftmost_child();GTNode*right_sibling();voidsetValue(ELEM);voidinsert_first(GTNode*n);voidinsert_next(GTNode*n);voidremove_first();voidr

5、emove_next();};classGenTree{public:GenTree();~GenTree();voidclear();GTNode*root();voidnewroot(ELEM,GTNode*,GTNode*);};5.2.1二叉树的定义及其主要特性二叉树（binarytree）由节点（node）的有限集合组成，这个集合或者为空，或者由一个根结点以及两棵不相交的、分别称为这个根的左子树和右子树的二叉树组成。这两棵树的根称为此二叉树根结点的子结点。根据左子树及右子树存在的不同状态，二叉树可以有五种基本形态，如图

6、5.4所示。(a)(b)(c)(d)(e)图5.3二叉树的五种基本形态(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树俱全的二叉树二叉树的性质性质1在二叉树第i层上至多有2i-1个结点(i≥1)。性质2深度为k的二叉树至多有2k-1个结点。性质3对任何一棵二叉树T，设n0、n2分别是叶结点的个数和度为2的结点的个数，则有n0=n2+1。以上三条性质是一般二叉树所共有的。下面我们先定义两种特殊的二叉树，然后指出它们特有的性质。满二叉树完全二叉树图5.4特殊的二叉树术语满二叉树一棵深度为k的二

7、叉树若有2k-1个结点，则此种二叉树称为满二叉树。完全二叉树(顺序二叉树)我们可以对满二叉树的结点进行连续编号，约定从根结点开始按层由左向右给出编号1，2，3，…。在进行这样的编号后，从编号为1的结点开始，由连续编号的任意多个结点组成的二叉树称为完全二叉树。二叉树的性质性质4具有n个结点的完全二叉树的深度为+1。性质5对于一棵有n个结点的完全二叉树，其任何一个编号为i的结点（1≤i≤n），都有以下结果：(1)若i=1，则结点i是根结点，无双亲；若i>1，则结点i的双亲是结点。(2)若2i≤n，则结点i的左孩子是2i；若2i>n，则结点i无左

8、孩子。(3)若2i+1≤n，则结点i的右孩子是2i+1；若2i+1>n，则结点i无右孩子。5.2.2二叉树的实现顺序存储结构对于完全二叉树（包括满二叉树），由于它有很好的性质，可