发布时间 : 星期一 文章数据结构习题集1'更新完毕开始阅读
2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是________。 3.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是________。
4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有________个空指针域。
5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列________。 6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列________。 7.找出满足下列条件的二叉树
1）先序和中序遍历，得到的结点访问顺序一样。________。 2）后序和中序遍历，得到的结点访问顺序一样。________。 3）先序和后序遍历，得到的结点访问顺序一样。________。
8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？________。
9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有________个。
10.含有100个结点的树有________条边。 四、问答题
1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:
(1)第k层结点数(1≤k≤h)。 (2)整棵树结点数。
(3)编号为i的结点的双亲结点的编号。
(4)编号为i的结点的第j个孩子结点(若有)的编号。
2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系： n0=（k-1）n1+1
3.已知一组元素为(50,28,78,65,23,36,13,42,71）,请完成以下操作: (1)画出按元素排列顺序逐点插入所生成的二叉排序树BT。
(2)分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数。 (3)画出在BT中删除(23〉后的二叉树。
4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数。
5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。
(1)试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权)。 (2)求出每个字符的晗夫曼编码。 (3)求出传送电文的总长度。
(4)并译出编码系列1100011100010101的相应电文。 五、算法设计
已知一棵具有n个结点的完全二叉树被顺序存储在一维数组A[n]中,试编写一个算法输出A[i]结点的双亲和所有孩子。
二叉树其他运算的算法（只作参考） #include \#include \typedef struct node {
char data;
struct node *lchild,*rchild;
11
}NODE; NODE *T;
void create(NODE **T) //创建二叉树 { char ch;
ch=getchar();
if(ch==' ') *T=NULL; else
{ *T=(NODE *)malloc(sizeof(NODE)); (*T)->data=ch;
create(&((*T)->lchild));
create(&((*T)->rchild)); } }
void inorder(NODE *p) //中序编历二叉树 { if(p!=NULL)
{ inorder(p->lchild); printf(\
inorder(p->rchild); } } int num=0;
void count(NODE *p) //统计出二叉树中单孩子的结点数方法1 {
if(p!=NULL) {
count(p->lchild);
if(p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL) num++;
count(p->rchild); } }
void count1(NODE *p,int *num1) {
if(p!=NULL) {
count1(p->lchild,num1);
if(p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL) (*num1)++;
count1(p->rchild,num1); } }
int onechild(NODE *t) //统计出二叉树中单孩子的结点数方法2 {
int num1,num2;
if(t==NULL) return(0);
else if(t->lchild==NULL&&t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL) return(onechild(t->lchild)+onechild(t->rchild)+1); else {
12
num1=onechild(t->lchild); num2=onechild(t->rchild); return(num1+num2); } }
int sum(NODE *t) //统计出二叉树中所有结点数 {if(t==NULL) return(0); else
return(sum(t->lchild)+sum(t->rchild)+1); }
int leaf(NODE *t) //统计出二叉树中叶子结点数 {
if(t==NULL) return(0); else
if(t->lchild==NULL&&t->rchild==NULL) return(leaf(t->lchild)+leaf(t->rchild)+1); else
return(leaf(t->lchild)+leaf(t->rchild)); }
void preorder1(NODE *root) //非递归二叉树前序编历 { NODE *p,*s[100],*q; //q为p的双亲结点 int top=0; //top为栈顶指针 p=root;q=p;
while((p!=NULL)||(top>0)) { while(p!=NULL) {printf(\s[++top]=p; p=p->lchild; } p=s[top--]; p=p->rchild; }}
void delk(NODE **root,char k) //删去并释放数据值为k的叶结点 { NODE *p,*s[100],*q; //q为p的双亲结点 int top=0; //top为栈顶指针 if((*root)==NULL)return;
if((*root)->lchild==NULL &&(*root)->rchild==NULL&&(*root)->data==k) {*root=NULL;return;}
p=*root;q=p;
while((p!=NULL)||(top>0)) {
while(p!=NULL) {
if(p->lchild==NULL&&p->rchild==NULL &&p->data==k) {if(q->lchild==p) q->lchild=NULL; else q->rchild=NULL; free(p); return; }
13
s[++top]=p; q=p; p=p->lchild; } p=s[top--]; q=p;p=p->rchild; }}
void lev_traverse(NODE *T) //按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息
{NODE *q[100],*p; int head,tail;
q[0]=T;head=0;tail=1; while(head printf(\ if(p->rchild!=NULL) q[tail++]=p->rchild; if(p->lchild!=NULL) q[tail++]=p->lchild; }} int depth(NODE *t) //求二叉树的深度 { int num1,num2; if(t==NULL) return(0); if(t->lchild ==NULL&&t->rchild ==NULL) return(1); else { num1=depth(t->lchild ); num2=depth(t->rchild ); if(num1>num2) return(num1+1); else return(num2+1); } } int onechild3(NODE *root) //非递归统计出二叉树共有多少个度为1的结点 { NODE *p,*s[100]; int top=0,num=0; //top为栈顶指针 p=root; while((p!=NULL)||(top>0)) { while(p!=NULL) {if(p->lchild!=NULL&&p->rchild==NULL ||p->lchild==NULL&&p->rchild!=NULL) num++; s[++top]=p; p=p->lchild; } p=s[top--]; p=p->rchild; } return num; } int like(NODE *t1,NODE *t2) //判定两颗二叉树是否相似 { int like1,like2; 14