数据结构 教学课件作者 戴敏6

数据结构数据结构 (DATA STRUCTURE)第六章第六章 树与二叉树树与二叉树n n树的定义与基本术语树的定义与基本术语n n二叉树二叉树n n二叉树遍历二叉树遍历n n线索化二叉树线索化二叉树n n森林与二叉树的转换森林与二叉树的转换n n树与森林的遍历树与森林的遍历n n哈夫曼树哈夫曼树(Huffman Tree)26.1 树的基本概念树的基本概念6.1.1 6.1.1 树的定义及相关术语树的定义及相关术语1)1)树的定义树的定义定义：定义：定义：定义：树是由树是由树是由树是由 n n(n n0)0)个结点组成的有限集合。个结点组成的有限集合。个结点组成的有限集合。个结点组成的有限集合。其中其中其中其中 有且仅有一个特定的称之为有且仅有一个特定的称之为有且仅有一个特定的称之为有且仅有一个特定的称之为根根根根(root)(root)的结点；的结点；的结点；的结点；n n11时时时时,除根外的其余结点被划分为除根外的其余结点被划分为除根外的其余结点被划分为除根外的其余结点被划分为 mm(mm0)0)个互不相交的有限集合个互不相交的有限集合个互不相交的有限集合个互不相交的有限集合T T1 1,T T2 2,T Tmm，每个集合每个集合每个集合每个集合本身本身本身本身又是一棵树又是一棵树又是一棵树又是一棵树，称之为根的，称之为根的，称之为根的，称之为根的子树子树子树子树(subTreesubTree)。特点：特点：特点：特点：树中至少有一个结点树中至少有一个结点树中至少有一个结点树中至少有一个结点根根根根 树中各子树是互不相交的集合树中各子树是互不相交的集合树中各子树是互不相交的集合树中各子树是互不相交的集合32)2)基本术语基本术语n n结点结点结点结点(node):(node):表示树中的元素表示树中的元素表示树中的元素表示树中的元素,包括数据项及若干指向其子树的分包括数据项及若干指向其子树的分包括数据项及若干指向其子树的分包括数据项及若干指向其子树的分支支支支n n结点的度结点的度结点的度结点的度(degree)(degree)：一个结点拥有子树的个数一个结点拥有子树的个数一个结点拥有子树的个数一个结点拥有子树的个数n n树的度树的度树的度树的度(degree)(degree)：一棵树中结点的最大度数一棵树中结点的最大度数一棵树中结点的最大度数一棵树中结点的最大度数n n叶子叶子叶子叶子(leaf)(leaf)结点：度为结点：度为结点：度为结点：度为0 0的结点的结点的结点的结点n n分支分支分支分支(branch)(branch)结点：度不为结点：度不为结点：度不为结点：度不为0 0的结点的结点的结点的结点n n孩子孩子孩子孩子/子女子女子女子女(child)(child)结点：某结点子树的根结点：某结点子树的根结点：某结点子树的根结点：某结点子树的根n n双亲双亲双亲双亲(parent)(parent)结点结点结点结点:某个结点是其子树根的双亲某个结点是其子树根的双亲某个结点是其子树根的双亲某个结点是其子树根的双亲4 兄弟兄弟兄弟兄弟(sibling)(sibling)结点：具有同一双亲的所有结点结点：具有同一双亲的所有结点结点：具有同一双亲的所有结点结点：具有同一双亲的所有结点 祖先祖先祖先祖先(ancestor)(ancestor)结点：结点：结点：结点：子孙子孙子孙子孙(descendant)(descendant)结点：结点：结点：结点：结点的层数结点的层数结点的层数结点的层数(level)(level)：规定根结点层数为规定根结点层数为规定根结点层数为规定根结点层数为1 1，其余结点层，其余结点层，其余结点层，其余结点层数等于其双亲结点层数加数等于其双亲结点层数加数等于其双亲结点层数加数等于其双亲结点层数加1 1 树的高度树的高度树的高度树的高度/深度深度深度深度(depth)(depth)：树中结点的最大层次树中结点的最大层次树中结点的最大层次树中结点的最大层次 有序树：树中每个结点的各个子树从左到右是有次序的有序树：树中每个结点的各个子树从左到右是有次序的有序树：树中每个结点的各个子树从左到右是有次序的有序树：树中每个结点的各个子树从左到右是有次序的（不能互换）（不能互换）（不能互换）（不能互换）无序树：子树的次序可以互换无序树：子树的次序可以互换无序树：子树的次序可以互换无序树：子树的次序可以互换 路径：若树中存在一个结点序列路径：若树中存在一个结点序列路径：若树中存在一个结点序列路径：若树中存在一个结点序列k k1 1,k,k2 2k kj j,使得使得使得使得k ki i是是是是k ki+1i+1(1ij)(1ij)的双亲，则称该序列是的双亲，则称该序列是的双亲，则称该序列是的双亲，则称该序列是k k1 1到到到到k kj j的路径的路径的路径的路径 森林：是森林：是森林：是森林：是m(m(mm 0)0)棵互不相交的树的集合。棵互不相交的树的集合。棵互不相交的树的集合。棵互不相交的树的集合。2)2)基本术语基本术语5ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点H的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F,G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先6 树形图树形图树形图树形图文氏图文氏图文氏图文氏图bacghdefijijdfg habce 凹入表表示凹入表表示凹入表表示凹入表表示 括号表示法括号表示法括号表示法括号表示法a(b(d,e(i,j),f),c(g,h)6.1.2 树的表示方法树的表示方法7 证证明明：根根据据树树的的定定义义，在在一一棵棵树树中中，除除根根结结点点以以外外，每每个个结结点点有有且且仅仅有有一一个个父父结结点点，也也就就是是说说，每每个个结结点点与与指指向向它它的的一一个个分分支支一一一一对对应应，所所以以，除除根根结结点点以以外外的的结结点点数数等等于于所所有有结结点点的的分分支支数数（即即度度数数），而而根根结结点点无无父父结结点点，因因此，树中的结点数等于分支数加此，树中的结点数等于分支数加1 1。性质性质性质性质2 2 度为度为度为度为 kk的树中第的树中第的树中第的树中第 i i层上最多有层上最多有层上最多有层上最多有k ki-1i-1个结点个结点个结点个结点(i1)(i1)证证明明：（归归纳纳法法）对对于于i=1i=1，显显然然成成立立；假假设设对对于于 i-1 i-1 层层，上上述述条条件件成成立立，即即第第i-1i-1层层最最多多有有k ki-2i-2个个结结点点，对对于于第第 i i 层层，结结点点数数最最多多为为第第 i-1 i-1 层层结结点点数数的的k k倍倍(因因为为度度为为k k)，故第故第 i i 层的结点数为层的结点数为 k ki-2i-2k k=k ki-1i-1。性质性质性质性质1 1 树中的结点数等于分支数加树中的结点数等于分支数加树中的结点数等于分支数加树中的结点数等于分支数加 1 16.1.3 树的性质树的性质8性质性质性质性质3 3 高度为高度为高度为高度为hh的的的的 kk叉树最多有叉树最多有叉树最多有叉树最多有个结点。个结点。个结点。个结点。证明：由性质证明：由性质2 2可知，若每一层的结点数最多，则整个可知，若每一层的结点数最多，则整个k k叉叉树树结结点点数数最最多多，共共有有k k0 0+k k1 1+k kh h-1-1=个个结结点点 。当当当当一一一一棵棵棵棵 kk叉叉叉叉树树树树上上上上的的的的结结结结点点点点数数数数达达达达到到到到 时时时时，称称称称为为为为满满k k叉树叉树。9性质性质性质性质4 4 具有具有具有具有 nn个结点的个结点的个结点的个结点的 kk叉树的最小高度为叉树的最小高度为叉树的最小高度为叉树的最小高度为 logk(n(k-1)+1)证证明明：设设具具有有n n 个个结结点点的的k k 叉叉树树的的高高度度为为h h，当当该该树树的的前前面面h-1h-1层层都都是是满满的的，即即每每一一层层的的结结点点数数等等于于k ki-1i-1个个(1ih-1)(1ih-1)，第第 h h 层层(即即最最后后一一层层)的的结结点点数数可可能能满满，也也可可能能不不满满，这这时时，该该树树具具有有最最小小的的高高度度。由由性性质质3 3 知知道道，结结点点数数 n n 应应满满足下面条件：足下面条件：n n ，通过转换为：通过转换为：k kh-1h-1 n n(k k-1)+1-1)+1k kh h，再再取取以以k k为为底底的的对对数数,可可以以得得到到:h h-1log-1logk k(n n(k k-1)+1)-1)+1)h h，即即有有:log:logk k(n n(k k-1)+1)-1)+1)h h log-带双亲的孩子链表带双亲的孩子链表带双亲的孩子链表带双亲的孩子链表为每个结点建立一个孩子链表（把每个结点的为每个结点建立一个孩子链表（把每个结点的为每个结点建立一个孩子链表（把每个结点的为每个结点建立一个孩子链表（把每个结点的孩子结点排列起来，链成一个单链表孩子结点排列起来，链成一个单链表孩子结点排列起来，链成一个单链表孩子结点排列起来，链成一个单链表 用含用含用含用含 nn个元素的结构数组指向每个孩子链表个元素的结构数组指向每个孩子链表个元素的结构数组指向每个孩子链表个元素的结构数组指向每个孩子链表2)2)2)2)孩子表示法孩子表示法孩子表示法孩子表示法:每个结点设多个指针指向各个孩子每个结点设多个指针指向各个孩子每个结点设多个指针指向各个孩子每个结点设多个指针指向各个孩子12树的孩子树的孩子树的孩子树的孩子-兄弟表示兄弟表示兄弟表示兄弟表示 datafirstChildnextSibling3)3)孩子兄弟表示法孩子兄弟表示法(二叉树二叉树二叉树二叉树/二叉链表表示法二叉链表表示法二叉链表表示法二叉链表表示法)每个结点结构同二叉链表每个结点结构同二叉链表每个结点结构同二叉链表每个结点结构同二叉链表 两个链域分别指向该结点的两个链域分别指向该结点的两个链域分别指向该结点的两个链域分别指向该结点的第一个孩子第一个孩子第一个孩子第一个孩子和和和和下一个兄下一个兄下一个兄下一个兄弟结点弟结点弟结点弟结点abcdefhgiabcdefghi136.2 二叉树二叉树 (BinaryTree)6.2.1 二叉树的定义二叉树的定义定义：是定义：是n n(n n 0)0)个结点的有限集合，该个结点的有限集合，该集合或者为空，或者是由一个根结点加上两集合或者为空，或者是由一个根结点加上两棵分别称为棵分别称为左子树左子树和和右子树右子树的、互不相交的的、互不相交的二叉树组成。二叉树组成。特点：特点：每个结点至多有二棵子树每个结点至多有二棵子树每个结点至多有二棵子树每个结点至多有二棵子树 二叉树的子树有左、右之分，其次序不能任意二叉树的子树有左、右之分，其次序不能任意二叉树的子树有左、右之分，其次序不能任意二叉树的子树有左、右之分，其次序不能任意颠倒颠倒颠倒颠倒14 二叉树的五种基本形态二叉树的五种基本形态156.2.2 二叉树的性质二叉树的性质性质性质性质性质1 1 若二叉树的层次从若二叉树的层次从若二叉树的层次从若二叉树的层次从1 1开始，开始，开始，开始，二叉树的第二叉树的第二叉树的第二叉树的第 i i 层最层最层最层最多有多有多有多有 2 2i-1 i-1 个结点。个结点。个结点。个结点。(i(i 1)1)证明用数学归纳法证明用数学归纳法证明用数学归纳法证明用数学归纳法 证明：证明：证明：证明：i=1i=1时，有时，有时，有时，有 2