08数据结构第6章习题

数据结构计算机科学与技术学院Page22023/11/13基础知识题已知一棵树边的集合为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,

<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>}，请画出这棵树，并回答下列问题：哪个是根结点?哪些是叶子结点?哪个是结点G的双亲?哪些是结点G的祖先?哪些是结点G的孩子?哪些是结点E的子孙?哪些是结点E的兄弟?哪些是结点F的兄弟?结点B和N的层次号分别是什么?树的深度是多少?以结点C为根的子树的深度是多少?Page32023/11/13试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。试分别推导含n个结点和含n0

个叶子结点的完全三叉树的深度H。Page42023/11/13假设n和m为二叉树中两结点，用“1”、“0”或“ф”(分别表示肯定、恰恰相反或者不一定）填写下表：注：如果离a和b最近的共同祖先p存在；且a在p的

左子树中，b在p的右子树中，则称a在b的左方

(即b在a的右方)。Page52023/11/13找出所有满足下列条件的二叉树:它们在先序遍历和中序遍历时，得到的结点访问序列相同;它们在后序遍历和中序遍历时，得到的结点访问序列相同;它们在先序遍历和后序遍历时，得到的结点访问序列相同;将下列二叉链表改为先序线索链表。Page62023/11/13分别画出和下列树对应的各个二叉树，给出的各树的先根序列、后根序列。

Page72023/11/13将下列森林转换为相应的二叉树Page82023/11/13假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是令一种编码方案。对于上述实例，比较两种方案的优缺点。假设一棵二叉树的前序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。Page92023/11/13编程题本章练习题中的二叉树和树的二叉链表的类型定义如下：structBiTNode{//二叉树结点

ElemTypedata;

BiTLinklchild,rchild;

};typedefBiTLinkBiTree;//二叉树链表//树的二叉链表(孩子-兄弟）存储表示//typedefstructCSNode{

ElemTypedata;

structCSNode*firstchild,*nextsibling;

}CSNode,*CSTree;Page102023/11/13编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。

boolpre_Order_K(BiTreebt,intk,ElemType&x)

//已知bt为指向二叉链表(二叉树)的根指针，若k>0且不大于

//二叉树中的结点数，则以x带回该二叉树的先序序列中第k个

//数据元素并返回true，否则返回false编写递归算法，将二叉树中所有结点的左、右子树相互交换。

voidExchange(BiTree&bt)

//已知bt为指向二叉链表(二叉树)的根指针，

//本函数实现该二叉树上所有结点的左、右子树互换Page112023/11/13编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

voidReleaseX(BiTree&bt,ElemTypex)

//已知bt为指向二叉链表(二叉树)的根指针，若二叉树上存在其

//数据元素和x相同的结点，则均删除之。编写按层次顺序(同一层自左至右)遍历二叉树的算法。

voidLevelOrder(BiTreebt,charss[],int&n)