数据结构预算法第七章树

第七章树和二叉树树形结构是一种重要的非线性结构，在计算机科学中有着广泛的应用。7.1树的定义和术语7.1.1树的定义树（tree）是n(n≥0)个结点的有限集。在一棵非空树中：（1）有且仅有一个特定的结点,称为根（root）（根结点无前驱结点）;（2）当n1时，除根结点之外的其余结点可分为m(m0)个互不相交的有限集（T1,T2,…Tm），其中每一集合本身又是一棵树，并且称为根的子树（subtree）。举例例7．1（a）只有根结点的树（b）一般的树（b）中A为根结点，其余结点分成三个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J}而T1，T2，T3本身又都是只有一个根结点的树。ALKEFGHIJDCBAM7.1.2基本术语：（1）结点：包含一个数据元素及若干指向其子树的分支（2）结点的度：结点拥有子树数目称为结点的度。如图7-1-1的（b）中，A的度为3；C的度为1；M的度为0。（3）叶子（或终端）结点：度为零的结点。（4）分支结点（或非终端结点）：除根结点外度不为零的结点，也称为内部结点。（5）树的度：树内各结点的度的最大值。（6）孩子：结点的子树的根称为该结点的孩子。如图7-1-1的（b）中，D为A的子树T3的根，则D是A的孩子。（7）双亲：和孩子定义相应地该结点称为孩子的双亲。如图7-1-1的（b）中，A为D的双亲。（8）兄弟：同一个双亲的孩子之间互称兄弟。如图7-1-1的（b）中的H，I，J。（9）祖先：从根到该结点所经过分支上的所有结点。如：M的祖先为A，D，H（10）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如图7-1-1的（b）中B的子孙为E，F，K，L（11）层次：从根开始定义为第一层，根的孩子为第二层，依次例推。（12）深度（或高度）：树中结点的最大层次。（13）有序树：将树中结点的各子树看成从左到右是有序的。有序树中最左边的子树的根称第一个孩子，最右边的称为最后一个孩子。（14）无序树：树中结点的各子树没有次序的。（15）森林：是m(m≥0)棵互不相交的树的集合，对树中每个结点而言，其子树的集合即为森林。该树的根结点为：a，分支结点为：b、c、e；叶子结点为d、f、g、h、i、j；该树的度为3，高度为4；第一层有结点：a，第二层有结点：b、c；第三层有结点d、e、f、g、h，第四层有结点：i、j。abcdeigjhf7.2二叉树7.2.1二叉树的定义和性质：1、定义：二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。2、如图所示二叉树的五种基本形态（a）(b)(c)(d)(e)7.2.2二叉树的性质(1)性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。(2)性质2：深度为k的二叉树的最大结点数为2k-1(k≥1)。(3)性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1（4）一棵深度为k且有2k-1个结点的二叉树称满二叉树。特点：每层上的结点数都为最大结点数，除终端结点外，每个结点都有两棵子树。（5）完全二叉树：如深度为k，有N个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到N的结点一一对时，称之为完全二叉树。特点：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上。显然一棵满二叉树一定是完全二叉树，但一棵完全二叉树不一定是满二叉树。（6）完全二叉树的两个特性：性质4：具有n个结点的完全二叉树的深度为└Log2n┘+1。性质5：如果对一棵有n个结点的完全二叉树（其深度为└Log2n┘+1）的结点按顺序编号，则任一结点i(1≤i≤n)有：①若i=1,则结点i是二叉树的根结点，若i1，则i的双亲结点为结点┗i/2┛;②若2i≤n，则i的左孩子是结点2i，否则无左孩子；③若2i+1≤n，则i的右孩子是结点2i+1,否则无右孩子。7.2.3二叉树的存储结构1.顺序存储结构用一组连续的存储单元存储二叉树的数据元素，按满二叉树的结点顺序编号依次存放二叉树中数据元素。012345T(6)图7-3完全二叉树ABCDEFABCDEF2.链式存储结构链表的结点至少包含：数据域和左右指针域的链有时还需增一指向双亲的指针域，有两个指针域的链表称为二叉链表，有三个指针域的链表称为三叉链表，如图5-5所示：例7-3分别画出二叉树链式存储结构7.3遍历二叉树7.3.1二叉树遍历遍历二叉树：是指如何按某条搜索路径巡访树中每个结点使得每个结点均被访问一次，而且仅被访问一次。简言之，以一定规则将二叉树中结点排列成一个线性序列。二叉树的遍历有三种方法：前序遍历、中序遍历、后序遍历。1.先序遍历：按先序遍历根结点；访问根结点的左子树；访问根结点的右子树；2.中序遍历：按中序遍历根结点的左子树；访问根结点；按中序遍历根结点的右子树；3.后序遍历：按后序遍历根结点的左子树；按后序遍历根结点的右子树；访问根结点；4.层次遍历：按照自上而下（从根结点开始），从左到右（同一层）的顺序逐层访问二叉树上的所有结点，这样的遍历方法称为层次遍历。例7．4用三种不同方法遍历图5-9所示的二叉树得：前序遍历结果为：124753689中序遍历结果为：742513869后序遍历结果为：745289631层次遍历结果为：123456789前序遍历的序列为：abdgcefh中序遍历的序列为：dgbaechf后序遍历的序列为：gdbehfca层次遍历的序列为：abcdefghabcdgefh如下图所示的一棵二叉树，写出其前序遍历、中序遍历、后序遍历的系列：举例：如图的一棵二叉树：1、写出先序遍历、中序遍历和后序遍历的结果；2、写出结点c的双亲结点、其左右孩子。eadcbjfghi先序遍历序列：eadcbjfghi中序遍历序列：abcdjefhgi后序遍历序列：bcjdahigfec的双亲结点是e，左孩子为b，没有右孩子。eadcbjfghi7.3.2恢复二叉树1.由前序和中序恢复二叉树（1）根据前序序列确定树的根(第一个根),根据中序确定左子树和右子树。（2）分别找出左子树和右子树的根结点，并把左、右子树的根结点连到父结点上去。（3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2结点或空为止。2.由后序和中序恢复二叉树（1）根据后序序列确定树的根(最后一个),根据中序确定左子树和右子树。（2）分别找出左子树和右子树的根结点，并把左、右子树的根结点连到父结点上去。（3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2结点或空为止。7.4二叉树的转换7.4.1一般树转换为二叉树1.连线---连接树中所有相邻的兄弟结点。2.删线---保留父亲结点与长子的连线，打断父亲结点和非长子之间的连线。3.旋转---以根结点为轴心，将整棵树顺时针旋转一定角度，使之层次分明。转换后的结论：（1）在转换产生的二叉树中，左分支上的各结点在原来的树中是父子关系；而右分支上的各结点在原来的树中是兄弟关系。（2）由于树的根结点无兄弟，所以转换后的二叉树的根结点必定无右子树。（3）一棵树采用长子、兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。（4）一般树转换为二叉树以后，将使树的深度增加。7.4.2森林转换成二叉树方法：（1）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作前一棵二叉树根结点的右子树，直到把最后一棵二叉树的根结点作其前一棵二叉树的右子树为止。7.4.3二叉树转换成森林方法：（1）若某结点是其父结点连起来的左孩子，则把该结点的右孩子、右孩子的右孩子、直到最后一个右孩子都与该结点的父结点连接起来。（2）删除原二叉树中的所有的父结点与右孩子结点的连线。（3）整理（1）、（2）的结果，使之层次分明，显示出树或森林的形状。7.5二叉树的应用7.5.2标识符树与表达式将算术表达式用二叉树来表示,称为标识符树,又称为二叉表示树。1.标识符树的特点（1）运算对象（标识符）都是叶子结点。（2）运算符都是根结点。2.从表达式产生标识符树的方法：（1）读入表达式的一部分产生相应的二叉树后，再读入运算符时，运算符与二叉树根结点的运算符比较优先级的高低；（2）遇到括号，先使括号内的表达式产生一棵二叉树，再把它的根结点连到前面已产生的二叉树根结点的右子树上去。（3）单目运算+、-，加运算对象θ（表示0）。7.6哈夫曼树及其应用7.6.1哈夫曼树的引入哈夫曼树又称最优树，是一类带权路径长度最短的树。1.几个术语（1）路径：从树中一结点到另一结点之间的分支构成这两点之间的路径。（2）路径长度：路径上的分支数目称做路径长度。（3）树的路径长度：是从树根到每一结点的路径长度之和，路径长度最短的二叉树是完全二叉树。（4）结点的带权路径长度：为从该结点到树根之间的路径长度与结点上权的乘积。（5）树的带权路径长度：树中所有叶子结点的带权路径长度之和，称为树的带权路径长度。（6）最优二叉树：带权路径长度最小的二叉树，称为最优二叉树。2.求树的带权路径长度见书153页例7-11例：有三棵二叉树都有4个叶子结点a,b,c,d,分别带权7,5,2,4它们带权路径长度分别是多少？a)WPL=7*2+5*2+2*2+4*2=36b)WPL=4*2+2*1+7*3+5*3=46c)WPL=7*1+5*2+2*3+4*3=35由图5-22可得：权值越大的叶子离根越近时，则二叉树的带权路径长度越小，所以图5-22中（c）图即为哈夫曼树。7.6.2哈夫曼树的构造哈夫曼算法步骤如下：（1）根据给定的n个权值{W1,W2，…Wn}构成n棵二叉树的集合F={T1，T2，…Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的要结点的权值为其左、右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新得的二叉树加入F（4）重复（2）和（3），直到F中只含一棵树为止。例：有a~h8个叶结点的权值分别为:13,8,6,25,36,5,2,19求哈夫曼树？7.6.3哈夫曼编码哈夫曼编码约定：左分支字符‘0’，右分支表示字符‘1’，则可从根结点到叶结点的路径上分支组成字符串作为该叶子结点的字符编码。举例1、以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为__，其带权路径长度为__。并写出各个结点的哈夫曼编码。623725191391810124567分析：哈夫曼树为：带权路径长度为：(4+5)*4+(10+6+7)*3+(18+12)*2=165典型例题1.深度为6的二叉树最多有()个结点。A)64B)63C)32D)31[分析]由二叉树的性质2知，最多结点个数26-1=64-1=63。[答案]B)2.任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置()。A)肯定发生变化B)有时发生变化C)肯定不发生变化D)无法确定[分析]由于在三种遍历中总是先遍历左子数，后遍历右子数，所以二叉树的叶子结点在三种遍历序列中的相对位置不好发生变化。[答案]C)。3.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少()个。A)k+1B)2kC)2k-1D)2k+1[分析]因为不存在度为1的结点，所以二叉树上除根结点外，每增加一层，至少要增加2个结点，如图5-25所示。典型例题图5-25因此当h=1时，结点总数为1(2*1-1=1)，它是根结点；当h=2时，结点总数为3(2*2-1=3)；当h=2时，结点总数为5(2*3-1=5);…当b=k时，结点总数为2*k-1