资源描述
第第6章章 树和二叉树树和二叉树6.1 树的定义和基本术语树的定义和基本术语6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.6 赫夫曼树及其应用赫夫曼树及其应用学习要点学习要点1、树和森林的概念（树的定义，树的术语、性质及运算）、树和森林的概念（树的定义，树的术语、性质及运算）；2、二叉树的定义、性质及运算；、二叉树的定义、性质及运算；3、二叉树的存储结构（顺序、链式表示）；、二叉树的存储结构（顺序、链式表示）；4、遍历二叉树；、遍历二叉树；5、树的存储结构；树、森林与二叉树的转换；遍历树；、树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林；遍历森林；6、哈夫曼树、哈夫曼编码。、哈夫曼树、哈夫曼编码。一、判断对错题一、判断对错题1.树结构中每个结点最多只有一个直接前驱。（树结构中每个结点最多只有一个直接前驱。（）2.由树转成二叉树，其根节点的右子树一定为空。（由树转成二叉树，其根节点的右子树一定为空。（）3.在前序遍历二叉树的序列中，任何结点的子树的所有结点在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。（都是直接跟在该结点之后。（）4.在中序线索二叉树中，右线索若不为空，则一定指向其双在中序线索二叉树中，右线索若不为空，则一定指向其双亲。（亲。（）5.已知二叉树的前序遍历和后序遍历不能唯一确定这棵二叉已知二叉树的前序遍历和后序遍历不能唯一确定这棵二叉树，这是因为不知道根结点是哪一个。（树，这是因为不知道根结点是哪一个。（）二、单项选择题二、单项选择题1.树最适合用来表示树最适合用来表示_。A.有序数据元素有序数据元素 B.无序数据元素无序数据元素C.元素之间无联系的数据元素之间无联系的数据 D.元素之间有分支层次的关系元素之间有分支层次的关系2.一棵一棵n个结点的二叉树，其空指针域的个数为个结点的二叉树，其空指针域的个数为_。A.n B.n+1 C.n-1 D.不确定不确定3.根据树的定义，具有根据树的定义，具有3个结点的树有个结点的树有_种树形。种树形。A.2 B.3 C.4 D.5 DBA二、单项选择题二、单项选择题4.节点前序为节点前序为ABC的不同二叉树的不同二叉树_形态。形态。A.3 B.4 C.5 D.65.具有具有35个结点的完全二叉树的深度为个结点的完全二叉树的深度为_。A.5 B.6 C.7 D.8CB三、填空题三、填空题1.在树的定义中，结点的度是在树的定义中，结点的度是_；叶子结点是叶子结点是_；树的度是；树的度是_；树中结点的最大层次称为树；树中结点的最大层次称为树的的_。2.哈夫曼树的带权路径长度哈夫曼树的带权路径长度_的二叉树。的二叉树。3.某二叉树的前序遍历序列为某二叉树的前序遍历序列为DABEC，中序遍历序列为，中序遍历序列为DEBAC，则后序遍历序列为，则后序遍历序列为_。结点拥有子树个数结点拥有子树个数度为度为0的结点的结点树中所有结点的最大值树中所有结点的最大值深度深度/高度高度最短最短EBCAD三、填空题三、填空题4.有有20个结点的完全二叉树，编码为个结点的完全二叉树，编码为10的结点的父结点的结点的父结点的编号是的编号是_。5.在一棵二叉树中，度为在一棵二叉树中，度为2的结点有的结点有5个，度为个，度为1的结点有的结点有6个，则叶子结点数有个，则叶子结点数有_个。个。56四、简答题四、简答题1.一棵度为一棵度为2的树与一棵二叉树有何区别？的树与一棵二叉树有何区别？解：解：有序树和无序树的区别。有序树和无序树的区别。四、简答题四、简答题2.给定一个权集给定一个权集W=4,5,7,8,6,12,18，请画出相应的哈夫曼，请画出相应的哈夫曼树，并计算其带权路径长度树，并计算其带权路径长度WPL。60352517181312678945WPL=83+(4+5)4+182+122+(6+7)3=159树型不唯一，但最小树型不唯一，但最小WPL值是唯值是唯一的。一的。3.设在树中，结点设在树中，结点x是结点是结点y的双亲，用来表示边。已知一棵树的双亲，用来表示边。已知一棵树边的集合为：边的集合为：哪个是根结点？哪个是根结点？哪些是叶结点？哪些是叶结点？哪个是哪个是g g的双亲？的双亲？哪些是哪些是g g的祖先？的祖先？哪些是哪些是e e的子孙？的子孙？哪些是哪些是f f的兄弟？的兄弟？结点结点b b和和j j的层次各是多少？的层次各是多少？树的深度是多少？树的深度是多少？树的度数是多少？树的度数是多少？根结点：根结点：a；叶子结点：叶子结点：d,f,g,h,j,k；g的双亲：的双亲：c；g的祖先：的祖先：a,c；e的子孙：的子孙：i,j,k；f的兄弟：的兄弟：g,h；b的层次：的层次：2，j的层次：的层次：5；树的深度：树的深度：5；树的度：树的度：3。abcedgfhijk4.某某二二叉叉树树的的前前序序遍遍历历的的结结点点访访问问顺顺序序是是abdgcefh，而而中中序序遍历的结点访问顺序是遍历的结点访问顺序是dgbaechf，则：则：画出这棵树的形态。画出这棵树的形态。写出该树后序遍历的结点访问顺序。写出该树后序遍历的结点访问顺序。abdgcefh后序后序后序后序遍历：遍历：遍历：遍历：gdbehfca5.设树设树T的度为的度为4，其中度为，其中度为1，2，3，4的结点个数分别为的结点个数分别为4，2，1，1。问。问T中有多少个叶子结点？中有多少个叶子结点？利用树的性质利用树的性质利用树的性质利用树的性质：各结点射出的分支总数：各结点射出的分支总数：各结点射出的分支总数：各结点射出的分支总数+1=+1=总结点数总结点数总结点数总结点数 树树树树T T中，各个结点射出的分支总数：中，各个结点射出的分支总数：中，各个结点射出的分支总数：中，各个结点射出的分支总数：41+22+13+14=1541+22+13+14=15则树则树则树则树T T中的总结点数为：中的总结点数为：中的总结点数为：中的总结点数为：15+1=1615+1=16非叶子结点总数为：非叶子结点总数为：非叶子结点总数为：非叶子结点总数为：4+2+1+1=84+2+1+1=8叶子结点总数：叶子结点总数：叶子结点总数：叶子结点总数：16 8=816 8=86.设一棵完全二叉树具有设一棵完全二叉树具有1000个结点。问：个结点。问：该该完完全全二二叉叉树树有有多多少少个个叶叶子子结结点点？有有多多少少个个度度为为2的的结结点点？有多少个度为？有多少个度为1的结点？的结点？若完全二叉树有若完全二叉树有1001个结点，再回答上述问题，并说明理个结点，再回答上述问题，并说明理由。由。利用树的性质利用树的性质利用树的性质利用树的性质：对任何一棵二叉树：对任何一棵二叉树：对任何一棵二叉树：对任何一棵二叉树T T，如果其终端结点数为如果其终端结点数为如果其终端结点数为如果其终端结点数为n n0 0，度为，度为，度为，度为2 2的的的的结点数为结点数为结点数为结点数为n n2 2，则：则：则：则：n n0 0=n=n2 2+1+1。7.分别画出下图所示树的孩子链表（同构）和孩子兄弟链表。分别画出下图所示树的孩子链表（同构）和孩子兄弟链表。孩子链表孩子链表（同构）（同构）ABCDEFGHIJKL1234567891011孩子兄弟链表孩子兄弟链表ABECFGDKH JLI8.将下图所示的森林转换成二叉树。将下图所示的森林转换成二叉树。结果二叉树结果二叉树ABGCHJEDIKFLMN9.设某密码电文由设某密码电文由8个字母组成，每个字母在电文中的出现频个字母组成，每个字母在电文中的出现频率分别是率分别是7，19，2，6，32，3，21，10，试为这，试为这8个字母设个字母设计相应的赫夫曼编码。计相应的赫夫曼编码。分析：分析：1.首先建立赫夫曼树；首先建立赫夫曼树；2.然后根据左、右分支建立编码。然后根据左、右分支建立编码。赫夫曼赫夫曼赫夫曼赫夫曼编码：编码：编码：编码：1.2：10000；2.3：10001;3.6：1001；4.7：1010；5.10：10116.19：00；7.21：01；8.32：11。100194060281117521326710231111111000000010.编码编码00，01，10，11、0，1，00，11、0，10，110，111哪一组不是哪一组不是前缀编码前缀编码？前缀编码：前缀编码：字符串都字符串都互不为互不为前缀。前缀。结论：结论：0，1，00，11五、程序设计题五、程序设计题1.以二叉链表为存储结构，设二叉树以二叉链表为存储结构，设二叉树T结构为：结构为：typedef struct BINTNODE char data;BINTNODE*lchild;BINTNODE*rchild;BINTNODE；(1)求二叉树中度为求二叉树中度为0的结点个数。的结点个数。(2)交换二叉树各节点的左、右子树。交换二叉树各节点的左、右子树。请写出具体程序。请写出具体程序。分析：分析：分析：分析：采用递归算法，若结点的左、右子树都为空指针，采用递归算法，若结点的左、右子树都为空指针，则该结点是叶子；则该结点是叶子；子树根结点子树根结点的叶子数为左、右子树的叶的叶子数为左、右子树的叶子数之和。其递归模型：子数之和。其递归模型：int LeafCount(BitTree T)/求二叉树中叶结点的数目求二叉树中叶结点的数目 if(!T)return 0;/空树没有叶子空树没有叶子 else if(!T-lchild&!T-rchild)return 1;/叶结点叶结点 else return LeafCount(T-lchild)+LeafCount(T-rchild);2.已知二叉树以一维数组作为存储结构，试编写算法求下已知二叉树以一维数组作为存储结构，试编写算法求下标为标为i和和j的两个结点的最近共同祖先结点的值。的两个结点的最近共同祖先结点的值。分析：分析：分析：分析：根据二叉树的性质，使根据二叉树的性质，使i和和j交替追赶，直到相等，从交替追赶，直到相等，从而找到共同祖先。而找到共同祖先。ABCDEFGA B C 0 D E F G1 2 3 4 5 6 7 8 9 10 110 0 0ijijvoid parent(int A,int i,int j)/以一维数组作为存储结构求下标为以一维数组作为存储结构求下标为i和和j的两个结点的两个结点 /的最近共同祖先的最近共同祖先 if(Ai=0|Aj=0)printf(“错误错误”);else i=i/2;j=j/2;while(ij)if(idata=T2-data)/T1和和T2的数据域的值相等则判断它们的子树是否等价的数据域的值相等则判断它们的子树是否等价 return(Like(T1-lchild,T2-lchild)&Like(T1-rchild,T2-rchild)结束结束
展开阅读全文