《数据结构树》PPT课件

《《数据结构树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第六章树重庆一中葛静树的基本概念空树：不含结点的树。非空树：至少含一个节点的树。只有一个根结点，其余结点分为m棵互不相交的子树，每棵子树又都是一棵树。（递归定义）ABCDEFGHIAABACBACBACBACBACBAGCBAFGCBAEFGCBADEFGCBADEFGCBADEFGCBAHDEFGCBAIHDEFGCBA树的二元组定义：Tree=(K,R)K={ki｜1<=i<=n,n>0,n为树中结点数目,ki∈elemptype}R={r}当n>0时，关系r满足下列条件：（1）有且仅有一个

2、结点没有前驱，即根结点。（2）其余每个结点有且仅有一个前驱结点。（3）包括树根结点在内的每个结点，可以有任意多个后继结点。树的二元组定义K={A,B,C,D,E,F,G,H,I}R={,,,,,,,}IHDEFGCBA例2、表达式树a*b+(c-d/e)*f/cab-f**+ed树的表示方法：1、树形图2、二元组3、目录结构4、集合图5、凹入表6、广义表树的基本术语结点的度：结点的儿子数（注意不包括孙子）树的度：树中所有结点的

3、度的最大值分支结点（非终端结点）：度大于0的结点叶子结点（终端结点）：度为0的结点孩子结点：某结点的后继叫该结点的孩子。双亲结点（父结点）：某结点的前驱叫该结点的父亲。显然，根结点没有双亲，叶结点没有孩子。结点的层数：根为第一层，其儿子为第二层，孙子为第三层，以此类推。树的深度（高度）：结点的最大层数。森林：互不相交的树的集合。对于每个分支结点，其子树的集合就是森林。IHDEFGCBA二叉树的定义树的度不超过2的有序树，非常重要的数据结构。IHDFGCBA二叉树的性质性质1：二叉树第i层上至多有2^(i-

4、1)个结点（i≥1）性质2：深度为h的二叉树至多有2^h-1个结点。满二叉树：各层结点均达到2^(i-1)完全二叉树：除最后一层外，其余各层均满，且最后一层的结点集中在左边。给完全二叉树的结点从上到下，从左到右依次标号，则完全二叉树的标号性质有：性质1：若i<=(ndiv2),则i为分支结点，否则为叶子结点。性质2：在N个结点的完全二叉树中，若ｎ为奇数，则，所有分支都有左右儿子，若ｎ为偶数，则n/2的结点只有左儿子，没有右儿子。其他结点有左右儿子。性质3：标号为i的结点，其左儿子为2i，右儿子为2i+1性

5、质4：若标号为i的结点有双亲，则i>1且其双亲结点为（idiv2）二叉树的性质完全二叉树的深度性质：N个结点的完全二叉树，其深度为trunc(log2n)+1证明见书上102页理想平衡树：二叉树中，除最后一层外，其余层都是满的，则称此树为理想平衡树。满二叉树是特殊的完全二叉树，完全二叉树是特殊的理想平衡树。FDEGCBADECBAEGCBA满二叉树完全二叉树理想平衡树完全二叉树理想平衡树理想平衡树二叉树的存储结构1、线性存储顺序存储二叉树，首先将二叉树按照完全二叉树中对应的位置进行标号，然后，以每个结点的

6、标号为下标，将对应的值存储到一个一维数组中。IHDFGCBAi1234567891011TABCDFGHI可见：完全二叉树用顺序存储极好，但一般二叉树容易造成空间浪费。二叉树的存储结构2、动态链接存储，三个域的节点：leftdataright或者再添加一个指向父亲的指针。Typepnode=^tnode;tnode=recorddata:elementtype;left,right:pnode;end;3、静态链接存储Typetnode=recorddata=elementtype;left,right:

7、integer;end;Vara:array[1..maxl]oftnode;IHDFGCBA12345678DIBDGAFCHL03002800R06007140存放的顺序是任意的由广义表生成二叉树该二叉树的广义表表示：A(B,C)A(B(D,F),C(,G))A(B(D,F(H,I)),C(,G))算法思想：1、依次输入广义表中每个字符。2、若遇到字母，则为其新建一个结点，若是第一个字母，则作为根节点，若是孩子节点，则将其连接到它的父节点上。3、若遇到左括号，则先将其前面字母的指针进栈，以便后面的结点

8、连接到父节点上。并记下将要插入节点的孩子为左孩子（k=1）4、若遇到逗号，则表明左子树以处理完，标记将要处理的子节点为右节点（k=2）.5、若遇到右括号，则表明子树处理完毕，则退栈。这样处理直至结束，通常用“@”表明广义表结束。IHDFGCBA算法伪代码：Procedurebuildtree;Begin输入一个字符chwhilech<>’@’dobegincasechof‘A’..’Z’:新建节点，值域赋为ch，左右子树指针置