第1章-数据结构1.5.ppt

《第1章-数据结构1.5.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3非线性结构3.1树结构3.2二叉树结构3.3图1树的定义和基本操作2二叉树3遍历二叉树4哈夫曼树及其应用3.1树结构一树的定义和基本操作树是一类重要的非线性数据结构，是以分支关系定义的层次结构树是由n（n≥0）个节点组成的有限集合。若n=0，称为空树；若n>0，则:（1）有一个特定的称为根（root）的节点。它只有直接后继，但没有直接前驱；（2）除根节点以外的其它节点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树(subTree

2、)，每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。一）树的定义例1:树根：A子树：T1={B,E,F}T2={C,I}T3={D,G,H,J}ABDCJGHIFE节点节点的度叶子（终端节点）分支节点孩子双亲(父节点)兄弟　　堂兄弟　祖先子孙层次深度森林二）树的基本术语和表示1、基本术语父节点：每一个节点只有一个前件，称为父节点。子节点：每一个节点可以有多个后件，都称为该节点的子节点。根节点：没有前件的节点只有一个，称为树的根节

3、点。叶子节点：没有后件的节点称为叶子节点。节点的度：一个节点所拥有的后件个数称为该节点的度。度树的度：所有节点中的最大度称为树的度。树的深度：树的最大层次称为树的深度。子树:在树中，以某节点的一个子节点为根构成的树称为该节点的一棵子树。ABCDEFGHIJKLM节点A的度：3节点B的度：2节点M的度：0叶子：K，L，F，G，M，I，J节点A的孩子：B，C，D节点B的孩子：E，F节点I的双亲：D节点L的双亲：E节点B，C，D为兄弟节点K，L为兄弟树的度：3节点A的层次：1节点M的层次：4树的深度：4节点F，G为堂兄

4、弟节点A是节点F，G的祖先树形结构表示法嵌套集合表示法：凹入法表示法：广义表表示法：（A（B（E（K，L），F），C（G），D（H（M），I，J）））2、表示方法ABCDEFGHIJKLM(1)树形结构表示法(2)嵌套集合表示法(3)凹入法表示法树的应用树的应用二、二叉树和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个节点的有限集，它或者是空集（n=0），或者由一个根节点及两棵不相交的左子树和右子树组成。特点：(1)二叉树的特点是每个节点最多有两个孩子，或者说，在二叉树中不存在度大于2的节

5、点，(2)二叉树是有序树，其子树的顺序不能颠倒。因此，二叉树有五种不同的形态。一、二叉树的定义A只有根节点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空ABCDEFGHIJKLM123456二、二叉树思考题任意三个节点可构造多少种树?多少种二叉树?二、二叉树具有3个节点的树和二叉树的所有不同形态。(1)具有3个节点的树有2种不同的形态，(2)具有3个节点的二叉树有5种不同的形态，树和二叉树的区别主要是二叉树的节点的子树要区分左子树和右子树。即使在节点只有一个子树的情况下，也要明确指出该子树是

6、左子树还是右子树。性质1：在二叉树的第i层上至多有2i-1个节点（i>=1）。证明：数学归纳法二、二叉树的性质i=1时，只有一个根节点，假设对所有j(1j=1)。证明：由性质1，可得深度为k的二叉树最大节点数是二、二叉树证明：设n1为二叉树T中度为1的节点数因为：二叉树中所有节点的度均小于或等于2所以：其节点总数

7、n=n0+n1+n2又二叉树中，除根节点外，其余节点都只有一个分支进入设B为分支总数，则n=B+1又：分支由度为1和度为2的节点发出，B=n1+2*n2于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1性质3：对任何一棵非空二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。二、二叉树几种特殊形式的二叉树(1)满二叉树定义：特点：每一层上的节点数都是最大节点数1231145891213671014151234567二、二叉树(2)完全二叉树定义：深度为k，有n个节点的二叉

8、树当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称为~特点叶子节点只可能在层次最大的两层上出现对任一节点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1123114589126710123456二、二叉树(3)二叉排序树特点左子树上所有节点的关键字均小于根节点的关键字；右子树上所有节点的关键字均大于等于根节点的关键字左