作业11-树与二叉树概念与基本操作

小鱼儿 2022-12-25 10:55 218阅读 0赞

1-3  
存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。(F)  
\[解析\]既然16个结点只有一个孩子,那么剩下的2000个要么没有孩子  
要么有两个孩子,又因为二叉树满足n0 = n2 + 1, 且 n0 + n2 = 2000  
联立求得呢n2不是个整数,所以不存在

2-1  
如果一棵非空k(k>=2)叉树T中每个非叶子结点都有k个孩子，  
则称T为正则k叉树。若T的高度为h(单结点的树h=1)，则T的结点数最多为：()  
A.(k^h−1)/(k−1)  
B.(k^(h−1)−1)/(k−1)  
C.(k^(h+1)−1)/(k−1)  
D.以上都不是  
\[解析\]第i层的节点数为 1 \* k^(n-1),符合 等比公式  
用前n项和求得,h层的树的节点数最多为a1 \* (1 - q ^n) / (1 - q)

2-2  
如果一棵非空k（k≥2）叉树T中每个非叶子结点  
都有k个孩子，则称T为正则k叉树。  
若T的高度为h(单结点的树h=1)，则T的结点数最少为：(D)  
A.(k^(h−1)−1)/(k−1)+1  
B.(k^h−1)/(k−1)−1  
C.kh  
D.k(h−1)+1  
\[解析\]非叶子结点只有最左侧的子节点有子树  
所以前h - 1 层有 k \* (h-1)个结点,最后还要加上叶子结点

2-7  
如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，  
则称T为正则k叉树。若T有m个非叶子结点，则T中的叶子结点个数为：©  
A.mk  
B.m(k−1)  
C.m(k−1)+1  
D.m(k−1)−1  
\[解析\]假设一个满足正则k叉树定义的树,结构为:非叶子结点  
只有最左子节点有子树,那么,一个非叶子结点就有 k - 1 个叶子结点  
最后一层的最左子节点没有子树,所以 要把它加上  
所以结果为m (k - 1) + 1

2-8  
有一个四叉树，度2的结点数为2，  
度3的结点数为3，度4的结点数为4。  
问该树的叶结点个数是多少？()  
A.10  
B.12  
C.20  
D.21  
\[解析\]  
树的度的定义:只计算出度  
n个结点,有n-1 条边, 有 (n - 1)个 出度  
2 \* 2 + 3 \* 3 + 4 \* 4 = ((x + 2 + 3 + 4) - 1)  
29 = (x + 8)  
x = 21

2-10  
按照二叉树的定义，具有3个结点的二叉树有几种？(5)  
A.3  
B.4  
C.5  
D.6

2-12  
二叉树中第5层(根的层号为1)上的结点个数最多为：©  
A.8  
B.15  
C.16  
D.32  
\[解析\]第k层的节点数为 2^(k-1)

2-14  
三叉树中，度为1的结点有5个，度为2的结点3个，  
度为3的结点2个，问该树含有几个叶结点？(A)  
A.8  
B.10  
C.12  
D.13  
\[解析\]1 \* 5 + 2 \* 3 + 3 \* 2 = (5 + 3 + 2 + x - 1)  
17 = 9 + x  
x = 8

2-17  
设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是(A)  
A.n在m左方  
B.n在m右方  
C.n是m祖先  
D.n是m子孙  
\[解析\]n是m的子孙,不一定正确,比如,n在m 的右子树上.序列中n就在m后面  
C和D差不多,也有两种情况

2-19  
设高为h的二叉树(规定叶子结点的高度为1)只有度为0和2的结点，  
则此类二叉树的最少结点数和最多结点数分别为：(B)  
A.2*h, 2^h−1  
B.2*h−1, 2^h−1  
C.2\*h−1, 2^(h−1)−1  
D.2^(h−1)+1, 2^h−1  
\[解析\]和刚才 正则k叉树差不多  
最少的节点数及 非叶子结点只有左子树 可以有子树  
画出来 就是 2 \*h - 1  
最多的话就是满二叉树了 k层的满二叉树 2^k - 1

2-11  
在一棵度为4的树T中，若有20个度为4的结点，  
,10 个度为3的结点，1个度为2的结点，10个度为1的结点，  
则树T的叶结点个数是：(B)  
A.41  
B.82  
C.113  
D.122  
\[解析\]20 \* 4 + 10 \* 3 + 1 \* 2 + 10 \* 1 = (20 + 10 + 1 + 10 + x - 1)  
122 = 40 + x  
x = 82

//头文件包含
    #include<stdlib.h>
    #include<stdio.h>
    #include<malloc.h>
    
    //函数状态码定义
    #define TRUE       1
    #define FALSE      0
    #define OK         1
    #define ERROR      0
    #define OVERFLOW   -1
    #define INFEASIBLE -2
    #define NULL  0
    typedef int Status;
    
    //二叉链表存储结构定义
    typedef int TElemType;
    typedef struct BiTNode{
        
        TElemType data;
        struct BiTNode  *lchild, *rchild; 
    } BiTNode, *BiTree;
    
    //创建二叉树各结点，输入零代表创建空树
    //采用递归的思想创建
    //递归边界：空树如何创建呢：直接输入0；
    //递归关系：非空树的创建问题，可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树。左右子树递归即可完成创建！
    
    Status CreateBiTree(BiTree &T){
        
       TElemType e;
       scanf("%d",&e);
       if(e==0)T=NULL;
       else{
        
         T=(BiTree)malloc(sizeof(BiTNode));
         if(!T)exit(OVERFLOW);
         T->data=e;
         CreateBiTree(T->lchild);
         CreateBiTree(T->rchild);
       }
       return OK;  
    }
    
    //下面是需要实现的函数的声明
    int GetDepthOfBiTree ( BiTree T)
    {
        
    	if (T == NULL) return 0;
    	else 
    	{
        
    		return 1 + max(GetDepthOfBiTree(T->lchild), GetDepthOfBiTree(T->rchild));
    	}
    }
    int LeafCount(BiTree T)
    {
        
    	if (T == NULL) return NULL;
    	else 
    	{
        
    		if (T->lchild == NULL && T->rchild == NULL) return 1;
    		else 
    		{
        
    			return LeafCount(T->rchild) + LeafCount(T->rchild);
    		}
    	}
    }
    	
    //下面是主函数
    int main()
    {
        
       BiTree T;
       int depth, numberOfLeaves;
       CreateBiTree(T);
       depth= GetDepthOfBiTree(T);
         numberOfLeaves=LeafCount(T);
       printf("%d %d\n",depth,numberOfLeaves);
       return 0;
    }
    
    /* 请在这里填写答案 */

//头文件包含
    #include<stdlib.h>
    #include<stdio.h>
    #include<malloc.h>
    
    //函数状态码定义
    #define TRUE       1
    #define FALSE      0
    #define OK         1
    #define ERROR      0
    #define OVERFLOW   -1
    #define INFEASIBLE -2
    
    typedef int Status;
    
    //二叉链表存储结构定义
    typedef int TElemType;
    typedef struct BiTNode{
        
        TElemType data;
        struct BiTNode  *lchild, *rchild; 
    } BiTNode, *BiTree;
    
    //创建二叉树各结点，输入0代表创建空树。
    //采用递归的思想创建
    //递归边界：空树如何创建呢：直接输入0；
    //递归关系：非空树的创建问题，可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树。左右子树递归即可完成创建！
    Status CreateBiTree(BiTree &T){
        
       TElemType e;
       scanf("%d",&e);
       if(e==0)T=NULL;
       else{
        
         T=(BiTree)malloc(sizeof(BiTNode));
         if(!T)exit(OVERFLOW);
         T->data=e;
         CreateBiTree(T->lchild);
         CreateBiTree(T->rchild);
       }
       return OK;  
    }
    
    //下面是需要实现的函数的声明
    int NodeCountOfBiTree ( BiTree T)
    {
        
    	if (T == NULL) return 0;
    	else 
    	{
        
    		return 1 + NodeCountOfBiTree(T->lchild) + NodeCountOfBiTree(T->rchild);
    	}
    }
    //下面是主函数
    int main()
    {
        
       BiTree T;
       int n;     
       CreateBiTree(T);  //先序递归创建二叉树     
       n= NodeCountOfBiTree(T);     
       printf("%d",n);
         return 0;
    }
    
    /* 请在这里填写答案 */