数据结构树的练习题

2018-08-01 16:42:00 wydyd110 阅读数 3028

《数据结构树之切腹攻略》

目录

华文课后题

王道课后题


华文课后题

1、给出一棵树的逻辑结构T=(N,R),其中:

N={A,B,C,D,E,F,G,H,I,J,K} 

R={r} 

r={(A,B),(B,E),(B,F),(F,G),(F,H),(A,C),(C,I),(C,J),(J,K),(A,D)}

试回答下列问题:

(1)哪个是F的父结点?

(2)哪些是B的子孙?

(3)以结点C为根的子树的深度是多少?

(注:根的层数为0,独根树深度为0,高度为1,其他题目同样如此) 

解析

2-1-1.png

答案: B EFGH 2

2、将下图的二叉树转换为对应的森林,按照后根次序列出其结点。

解析:

转化后的森林如下所示:

参考:

后根深度优先遍历森林 = 按中序法遍历对应的二叉树(左根右)

后根次序列 :EBFCDAIJKHGL

3、对于以下等价类,采用“加权合并规则”(也称“重量权衡合并规则”),进行并查运算,给出最后父节点索引序列。

8-9 3-2 7-4 5-9 6-1 8-6 7-3 2-5 8-0 //右指向左

注意:当合并大小相同的两棵树的时候,将第二棵树的根指向第一棵树的根;根节点的索引是它本身;数字之间用空格隔开。

解析:(合并时,结点数少的指向结点数多的)

13.png

答案: 8 6 3 7 7 8 8 8 8 8

4、若一个具有N个顶点K条边的无向图是一个森林(N>K且2K>=N),则该森林有多少棵树?

解析:

在一棵树中,结点比边多一个,即结点比边多几个就有几棵树。

答案: N-K

5、一棵完全三叉树,下标为121的结点在第几层?(注:下标号从0开始,根的层数为0)

解析:

第h层的下标是从(3^h-1)/2到(3^(h+1)-1)/2-1,

第5层的下标是从121到363。   

答案: 5

王道课后题

1、

2、

3、

4、

解析:

5

解析:

结点最少

结点最多

6

解析:该树为一棵完全三叉树,设高度为h,

1(高度1) + 3(高度2) + 9(高度3) + 27(高度4) + 10(高度5) = 50

7(2010年计算机联考真题)

解析:

树中的结点数 = 20 *4 + 10 *3 + 1*2 + 10 *1 + 1= 123

叶子结点数(度为0) = 123 - 20 - 10 -1 - 10 = 82

8

 

9

 

10

 

11

 

12

 

13

 

14

 

15

 

16

 

17

 

18

 

19

 

20

2020-04-07 12:00:57 danansheng 阅读数 67


持续更新中…
所有题目均来自PTA

原文链接=.=

题目总览

  1. 树的同构
  2. List Leaves
  3. Tree Traversals Again
  4. 是否同一棵二叉搜索树
  5. Root of AVL Tree
  6. Complete Binary Search Tree
  7. 堆中的路径
  8. File Transfer
  9. Huffman Codes
2019-10-15 14:23:48 shiliang97 阅读数 30696

4-1

某二叉树的前序和后序遍历序列正好相反,则该二叉树一定是 (4分)

  1. 空或只有一个结点
  2. 高度等于其结点数
  3. 任一结点无左孩子
  4. 任一结点无右孩子

作者: DS课程组

单位: 浙江大学

 

4-2

已知一棵二叉树的先序遍历结果是ABC,则以下哪个序列是不可能的中序遍历结果: (4分)

  1. ABC
  2. BAC
  3. CBA
  4. CAB

作者: DS课程组

单位: 浙江大学

4-3

如果二叉树的后序遍历结果是FDEBGCA,中序遍历结果是FDBEACG,那么该二叉树的前序遍历结果是什么? (4分)

  1. ABCDEFG
  2. ABDFEGC
  3. ABDFECG
  4. ABDEFCG

作者: DS课程组

单位: 浙江大学

4-4

给定二叉树如下图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4,则其遍历方式是: (4分)

  1. NRL
  2. RNL
  3. LRN
  4. RLN

作者: DS课程组

单位: 浙江大学

4-5

在下述结论中,正确的是: (4分)

①只有一个结点的二叉树的度为0;

②二叉树的度为2;

③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

  1. ①④
  2. ②④
  3. ①②③
  4. ②③④

作者: DS课程组

单位: 浙江大学

4-6

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序 (4分)

  1. 发生改变
  2. 不发生改变
  3. 不能确定
  4. 以上都不对

作者: DS课程组

单位: 浙江大学

4-7

按照二叉树的定义,具有3个结点的二叉树有几种? (4分)

  1. 3
  2. 4
  3. 5
  4. 6

作者: DS课程组

单位: 浙江大学

4-8

下面的函数PreOrderPrintLeaves(BinTree BT)按前序遍历的顺序打印出二叉树BT的所有叶子结点。则下列哪条表达式应被填在空中?(4分)

void PreOrderPrintLeaves( BinTree BT )
{  if (BT)  {
      if (___________________)  printf("  %d", BT->Data);
      PreOrderPrintLeaves( BT->Left  );
      PreOrderPrintLeaves( BT->Right );
   }
}
  1. BT->Data != 0
  2. !BT->Right
  3. !BT->Left
  4. !(BT->Left || BT->Right)

作者: 何钦铭

单位: 浙江大学

4-9

要使一棵非空二叉树的先序序列与中序序列相同,其所有非叶结点须满足的条件是:(4分)

  1. 只有左子树
  2. 只有右子树
  3. 结点的度均为1
  4. 结点的度均为2

作者: 考研试卷

单位: 浙江大学

4-10

若将一棵树 T 转化为对应的二叉树 BT,则下列对 BT 的遍历中,其遍历序列与 T 的后根遍历序列相同的是:(4分)

  1. 先序遍历
  2. 中序遍历
  3. 后序遍历
  4. 按层遍历

作者: 考研真题

单位: 浙江大学

2020-02-26 16:20:58 weixin_43400053 阅读数 83

1.问题描述:

 二叉树结点值为大写字母,输入二叉树的前序遍历和中序遍历序列,生成此二叉树,输出该二叉树的后序遍历和按层次遍历序列。输入某结点值,在二叉树中查找该结点,若该结点存在,则输出从根到该结点的路径,否则给出不存在信息。

2.算法思路:

  树的创建:将树的前序序列和中序序列分别存入两个数组中,前序序列的第一个值为树的根节点,在中序序列里找到该值,便可知道根节点的左子树的结点数和右子树的结点数。根据左子树的结点数和右子树的结点数可以将这两个数组分割为左子树部分和右子树部分,继续分别创建树。采用递归便可完成。(注:为方便后续使用,树的结点有左孩,右孩,父母三个指针。)

  后序遍历:用递归即可实现,注意为空的情况。

  层次遍历:采用队列进行层次遍历。先将树根入队列,然后进入循环。每出队列中的一个节点,就将该节点的左孩,右孩先后入队列,直到队列中没有节点为止。

  查找结点:用前序递归遍历树,每遍历一个结点就对该结点值与查找值进行比对,一旦相同则返回该结点指针,否则继续遍历,没有则返回空。

  输出树根到结点的路径:根据结点指针,沿它的父母指针向上递归遍历,出口为根节点的父母指针为空。先遍历祖先,再输出结点值,便可以得到从树根到结点的路径。

3.算法描述:

 1.结点的结构体中除了字符数据,还有它的左孩子,右孩子,父母的指针。

 2.creat(树的创建函数):

    传入:树的前序序列数组pre[],树的中序序列数组in[],树的前序序列数组的起始点a和结束点b,树的中序序列数组的起始点c和结束点d.

    返回:树的根节点的指针(node *)

    函数内容:

         动态申请根节点空间,赋根植,若前序数组中只有一个值,即该树只有根节点,将根结点的左右孩子均赋为空,返回根节点。在中序序列里找到根节点并记录其位置,就可以得到左子树的结点数和右子树的结点数,然后将数组划分为左子树和右子树部分。如果左子树为空,则根节点左孩子赋为空,否则继续调用本函数,根据左子树的结点数对数组界限进行修改,将返回值赋即左子树的根结点指针赋给根结点的左孩子,并且赋根结点的值给左孩子的父母指针。右边类似。

 3.levelorder(按层次遍历函数):

    需要传入:树的根结点指针(node  *),无返回值

    函数内容:建立队列,并将根节点入队列。进入循环(出一个队列中的元素,并将其输出,然后将该元素的左孩子,右孩子先后入队列),出口条件为队列为空。

 4.postorder(后序遍历函数):

    需要传入:树的根结点指针(node  *)   ,void

    函数内容:根结点不为空时,递归调用本函数后序遍历左子树,继续调用本函数后序遍历右子树,然后输出根结点值。

 5.search(查找结点函数):
    
    需要传入:树的根结点指针(node *) ,返回:找到结点的指针(node  *),没有则返回空(NULL)

    函数内容:若根结点为空则返回空。根结点不为空时判断根结点是否为待找结点,是则返回。若不是则继续调用本函数查找左子树,若返回值不为空则返回该返回值,否则继续调用本函数查找右子树,并将返回值返回。

 6.path(输出根到结点的路径函数):

       需要传入:结点指针(node  *)    无返回值

       函数内容:结点指针不为空时,调用该函数以输出该结点的父母指针的路径,然后输出该结点的值。



7.主函数:将树的前序序列和中序序列读入并存入字符数组中,依次调用creat(创建树函数),display(输出树函数),postorder(后序遍历树函数),levelorder(层次遍历树函数),search(查找节点函数),path(输出从根到结点的路径函数),完成该程序。

4.源程序:



#include<head.h>

node *creat(char pre[maxnode],char in[maxnode],int
a,int b,int c,int d){

        node *ptr;

        int i;

        

        ptr=(node
*)malloc(sizeof(node));

        if(!ptr)
exit(1);

        

        ptr->data=pre[a];

        

        if(a==b){

             ptr->lc=NULL;

             ptr->rc=NULL;

             return
ptr;

        }

        

        for(i=c;in[i]!=pre[a];i++);

             

        if(i!=c){

             ptr->lc=creat(pre,in,a+1,a+i-c,c,i-1);

             ptr->lc->parent=ptr;

        }

        else
ptr->lc=NULL;

             

        if(i!=d){

             ptr->rc=creat(pre,in,a+i-c+1,b,i+1,d);

             ptr->rc->parent=ptr;

        }

        else
ptr->rc=NULL;

        

        return
ptr;

} //创建树

 

void display(node *ptr,int level){

        if(ptr){

             int
i;

             

             display(ptr->rc,level+1);

             

             for(i=0;i<2*level;i++)
printf(" ");

             printf("%c\n",ptr->data);

             

             display(ptr->lc,level+1);

        }

}//输出树

 

 

void postorder(node *ptr){

        if(ptr){

             postorder(ptr->lc);

             postorder(ptr->rc);

             printf("%c
",ptr->data);

        }

} //后序遍历树

 

void initqueue(queue &s){

        s.head=NULL;

        s.tail=NULL;

} //初始化队列

 

void enqueue(queue &s,node *ptr){

        if(ptr){

             if(!s.head){

             s.head=(queuenode
*)malloc(sizeof(queuenode));

             s.tail=s.head;

             s.head->ptr1=ptr;

             s.head->ptr2=NULL;

            }

            else{

                  s.tail->ptr2=(queuenode
*)malloc(sizeof(queuenode));

                 s.tail=s.tail->ptr2;

                 s.tail->ptr1=ptr;

                 s.tail->ptr2=NULL;

          }

        }

} //入队列

 

node * dequeue(queue &s){

        node *ptr;

        queuenode
*queueptr;

        ptr=s.head->ptr1;

        queueptr=s.head;

        s.head=s.head->ptr2;

        free(queueptr);

        return
ptr;

}//出队列

 

void levelorder(node *ptr){

        queue s;

        node *p;

        

        initqueue(s);

        enqueue(s,ptr);

        while(s.head){

             p=dequeue(s);

             printf("%c
",p->data);

             enqueue(s,p->lc);

             enqueue(s,p->rc);

        }     

} //层次遍历

 

node *search(node *ptr,char c){

        if(ptr){

             node
*p;

             if(ptr->data==c)
return ptr;

             p=search(ptr->lc,c);

             if(p)
return p;

             p=search(ptr->rc,c);

             return
p;

        }

        else
return NULL;

} //查找结点 

 

void path(node *ptr){

        if(ptr){

             printfnode(ptr->parent);

             printf("%c
",ptr->data);

        }

} //输出根到节点的路径

 

int main(){

        int
nodenum,i,j;

        char
pre[maxnode],in[maxnode],c;

        node
*tree,*temp;

        

        printf("请输入节点数\n");

        scanf("%d",&nodenum);

        getchar();


        printf("请输入树的前序序列\n"); 

   
for(i=0;i<nodenum;i++) scanf("%c",&pre[i]);

    getchar();

    printf("请输入树的中序序列\n");

        for(i=0;i<nodenum;i++)
scanf("%c",&in[i]);

         

        tree=creat(pre,in,0,nodenum-1,0,nodenum-1);

        tree->parent=NULL;

        

        printf("树为:\n");

        display(tree,0);

        

        printf("该树的后序序列为:\n"); 

        postorder(tree);

        printf("\n");

        

        printf("该树的层次遍历为: \n");

        levelorder(tree);

        printf("\n");

        

        printf("请输入待查找节点\n");

        getchar();


        scanf("%c",&c);

        temp=search(tree,c);

        if(!temp)
printf("没有此节点\n");

        else {

             printf("从根到该结点的路径为:");

             path(temp);


             printf("\n");

        }

        

        return 0;

} 

5.结果分析:

  基本实现程序要求功能,对树为空,只有一个结点等问题都具有健壮性

6.心得体会:

1.scanf之前要使用getchar除去之前输入时遗留在缓冲区内的\n,使得正确读入。

2.对于树的递归创建,最后要专门给根结点指针的父母指针赋为空。

3.对于有关树的函数,都是在树根非空的基础上进行操作,故一进函数就对根结点进行判断,不为空时才有后序操作。

4.用前序递归法创建树最简单。

5.若要将二叉树的前序遍历改为逆前序,中序遍历改为逆中序,后序遍历改为逆后序,只需将左右孩子指针的引用次序调换即可。

6.除了用父母指针得到根到某一结点的路径,还可以用查找递归的方法实现,即判断结点左右子树中是否有待查找结点,将有结点的孩子指针插入路径中,不断递归即可,但是效率较为低下。
2011-11-12 11:27:55 jj12345jj198999 阅读数 1271
 

已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2^h-1]中,请写一非递归算法产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。

设计思想:采用队列结构,先建立根结点入队。当队列不空时循环执行以下步骤:队头结点出队,如果有左孩子,则建立左孩子结点并入队,如果有右孩子,则建立右孩子结点并入队。

代码:

 

typedef struct 
{
	BiTree bt;
	int num;
}tnode
tnode Q[maxsize];
void creat(BiTree T,ElemType BT[], int h)
{
	tnode tq;
	int len=pow(2,h)-1;
	T=(BiTree)malloc(sizeof(BiNode));
	T->data=BT[1];
	tq.bt=T;
	tq.num=1;
	Q[1]=tq;
	front=0;
	rear=1;
	while(front!=rear)
	{
		front=(front+1)%maxsize;
		tq=Q[front];
		p=tq.bt;
		i=tq.num;
		if(BT[2*i]=='#'||2*i>len)
		{
			p->lchild=NULL;
		}
		else
		{	
			p->lchild=(BiTree)malloc(sizeof(BiNode));
			p->lchild->data=BT[2*i];
			tq.bt=p->lchild;
			tq.num=2*i;
			rear=(rear+1)%maxsize;
			Q[rear]=tq;
		}
		if(BT[2*i+1]=='#')
		{
			p->rchild=NULL;
		}
		else
		{
			p->rchild=(BiTree)malloc(sizeof(BiNode));
			p->rchild->data=BT[2*i+1];
			tq.bt=p->child;
			tq.num=2*i+1;
			rear=(rear+1)%maxsize;
			Q[rear]=tq;
		}
	}
}