[计算机软件及应用]数据结构06gj

《[计算机软件及应用]数据结构06gj》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树树的结构特点树型结构是以分支关系定义的层次结构，任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点为分为m个互不相交的有限集T1,T2,,,Tm,每一个子集本身也是一棵树。树型结构在编译程序中，可用来表示源程序的语法结构。在数据库系统中，树型结构也是信息的重要组织形式之一。6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用主要内容是一类重要的非线性结构,是以分支关系定义的层次结构。ABCDEFGHIJA(a)(b)(c)树的例

2、子:树型结构现实世界：如家谱、行政组织机构等。计算机领域：编译程序、数据库系统等。树(Tree)的定义：n个结点组成的有限集合。满足如下两个条件（非空树）：ABCDEFGHIJ6.1树的定义和基本术语(2)当n>1时，根结点以外的其它结点可分m(m>0)个互不相交的有限集合T1,T2,…Tm。其中Ti称为子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。(1)有且仅有一个特定的根(Root)结点；(A(B(E(K,L),F),C(G),D(H(M),I,J))嵌套括号表示法IJFKLGMCCDBEA嵌

3、套集合凹入表树形表示ABCDEFGHIJKLM树的表示方法结点结点的度叶子(终端结点)分枝结点(非终端结点)树的度孩子结点双亲结点兄弟结点祖先结点子孙结点层次树的高度(深度)有序树无序树森林(树林)ABCDEFGHIJKLM基本术语InitTree(&T)构造空树T。Root(T)求树T的根结点。Parent(T,x)求树T中值为x的结点的双亲。Child(T,x,i)求树T中值为x的结点的第i个孩子。AddChild(T,y,i,x)树T中将值为x的结点作为值y的结点的第i个孩子插入到树中。DelChild(T,x,i)

4、删除值为x的结点的第i个孩子。Traverse(T)遍历或访问树T。树的基本运算二叉树的定义每个结点至多只有两棵子树，并且，6.2二叉树二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的5种形式(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(e)左子树为空的二叉树(d)根和左右子树AABABACB二叉树的性质性质1：第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的二叉树至多有2k－1个结点性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2+1.性质4：具有n个结

5、点的完全二叉树的深度为└log2n┘＋1。二叉树的性质（续）性质5：n个结点的完全二叉树的结点按层序编号,则对任一结点i(1≤i≤n)，有：(1)如果i＝1，则结点i无双亲，是二叉树的根；果i>1，则其双亲是结点└i/2┘。(2)如果2i>n，则结点i为叶子结点，无左孩子；否则(即：2i≤n)，其左孩子是结点2i;(3)如果2i＋1>n，则结点i无右孩子；否则(即：2i+1≤n)，其右孩子是结点2i＋1。(a)满二叉树2453671(b)完全二叉树245361(c)非完全二叉树245371(d)非完全二叉树23671特殊形

6、态的二叉树二叉树的抽象定义ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=空集，R为空集，称为空二叉树；若D为非空，R为二元关系。基本操作P：……}ADTBinaryTreeInitBiTree(&T)构造空二叉树T。DestroyBiTree(&T)销毁二叉树T。Root(T)求T的根结点。Parent(T,e)求T中值为e的结点的双亲。LChild(T,e)/RChild(T,e)求T中值为e的结点的左/右孩子。LBrother(T,e)/RBrother(T,e)求T中值为

7、e的结点的左/右兄弟。二叉树的基本操作二叉树的基本操作（续）Traverse(T)遍历二叉树T。AddLChild(&T,x,y)/AddRChild(&T,x,y)在T中，将值为y的结点作为值为x的结点的左/右孩子插入。DelLChild(&T,x)/DelRChild(&t,x)在T中，删除值为x的结点的左/右孩子。1、顺序存储结构顺序存放到一个一维数组中。#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;abcdefgh

8、ijkllkjihgfedcba01234567891011完全二叉树二叉树的存储结构GFØØØØEDCBA一般二叉树Ø表示该处没有元素存在。ACBDØØEFGØØ存储特点：适用于完全二叉树;对于非完全二叉树，将浪费大量存贮单元;不适合需要经常插入、删除树中结点的操作。若该二叉树为非完全二叉树，则必须将