数据结构第七周作业（二叉树、霍夫曼树、度、层次）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

1.

(1)

(2)

叶子节点：N,K,M,H,I,J,E,F,P,C
分支节点：L,G,D,A,B

(3)

各节点的度：

树的度：4

(4)

各节点的层次

树的高度：5

(5)

2.

3.

#include <stdio.h>
#include <stdlib.h>

struct Treenode{   
    int Data;
    struct Treenode *Lchild, *Rchild;
};
void Setuptree(struct Treenode **T, int b, struct Treenode *p, int tag){    
    printf("%d ",b);
    struct Treenode *x;
    x=(struct Treenode *) malloc(sizeof(struct Treenode));
    x->Data = b; x->Lchild = 0;  x->Rchild = 0;
    if ((*T)==0) (*T)=x;
    else if(p != 0){  
        if (tag==0) { x->Lchild = p->Lchild;  p->Lchild = x; } 
        else {x->Rchild = p->Rchild; p->Rchild = x;}
    }else if(tag==0){  
        p = (*T);
        while (p->Lchild !=0) p=p->Lchild;
        p->Lchild = x;
    }else{ 
        p = (*T); 
        while (p->Rchild !=0) p=p->Rchild;
        p->Rchild = x;
    }
}
/*递归方法
//统计叶子节点个数
int Leaf(struct Treenode *T){
   int count;
   if(T==NULL){
      return 0;
   }
   if(T->Lchild==NULL && T->Rchild==NULL){
      count++;
   }
   LeafCount(T->Lchild);
   LeafCount(T->Rchild);
   return count;
}
//统计度数为1的节点个数
int Degree1(struct Treenode *T){
   int count;
   if(T==NULL){
      return 0;
   }
   if((T->Lchild==NULL && T->Rchild!=NULL)||(T->Lchild!=NULL && T->Rchild==NULL)){
      count++;
   }
   Nodenumber1(T->Lchild);
   Nodenumber1(T->Rchild);
   return count;
}
//统计度数为2节点个数
int Degree2(struct Treenode *T){
   int count;
   if(T==NULL){
      return 0;
   }
   if(T->Lchild!=NULL && T->Rchild!=NULL){
      count++;
   }
   Nodenumber2(T->Lchild);
   Nodenumber2(T->Rchild);
   return count;
}*/
//非递归方法
int Leaf(struct Treenode *T){
    int count=0;
    if(T!=NULL)
    {
        Leaf(T->Lchild);
        Leaf(T->Rchild);
        if(T->Lchild==NULL && T->Rchild==NULL)
        {
            count++;   //统计叶子结点数目
        }
    }
    return count;
} 
int Degree1(struct Treenode *T){
    int count=0;
    if(T!=NULL){
        Degree1(T->Lchild);
        Degree1(T->Rchild);
        if((T->Lchild==NULL && T->Rchild!=NULL)||(T->Lchild!=NULL && T->Rchild==NULL)){
            count++;   //统计度为1的结点数目
        }
    }
    return count;
} 
int Degree2(struct Treenode *T){
    int count=0;
    if(T!=NULL){
        Degree2(T->Lchild);
        Degree2(T->Rchild);
        if(T->Lchild!=NULL && T->Rchild!=NULL){
            count++;   //统计度为2的结点数目
        }
    }
    return count;
} 
int main(){
    struct Treenode *T=0,*p, *(Q[20]);
    int A[]={45, 23, 76, 32, 66, 78, 52, 18, 90, 75};  
    int i=0;
    int n=sizeof(A)/sizeof(A[0]);
    Setuptree(&T, A[i++], p, 0);    // 二叉树根结点  //
    while (i<n){
        int Front=0; int Rear=0; Q[++Rear] = T;
        while (Front<Rear){ 
            p = Q[++Front];
            if (p->Lchild!=0) Q[++Rear] = p->Lchild;        // 左子树 //
            else {if (i<n) Setuptree(&T, A[i++], p, 0); }
            if (p->Rchild!=0) Q[++Rear] = p->Rchild;       // 右子树 //
            else {if (i<n) Setuptree(&T, A[i++], p, 1); }
        }
    }
    printf("度为0的结点数：%d\n",Leaf(T));
    printf("度为1的结点数：%d\n",Degree1(T));
    printf("度为2的结点数：%d\n",Degree2(T));

    return 0;
}

4.

设叶子节点为,则有总结点数 = 总度数+1

即

叶子节点

分支节点

5.

6.

7.

#include <stdio.h>
#include <stdlib.h>

struct Treenode{   
    int Data;
    struct Treenode *Lchild, *Rchild;
};
void BuildTree(struct Treenode **T,int x){
    struct Treenode *r, *p, *q;
    r = (struct Treenode *)malloc(sizeof(struct Treenode));
    r->Data = x; r->Lchild = 0; r->Rchild = 0; // 申请新结点 
    if ((*T) == 0) (*T) = r;    // 新结点作为某子树的根结点 //
    else{
        p= *T;
        while (p != 0){
            q = p;
            if (x < p->Data) p=p->Lchild;  else p=p->Rchild;
        }  // 查找位置 //
        if (x < q->Data) q->Lchild=r; else q->Rchild=r;   // 添加结点 //
    }  
}
//建分类树
void SortTree(struct Treenode **T, int A[], int n){     
    int i;  *T = 0;
    for (i=0; i<n; i++) BuildTree(&(*T), A[i]);
}
//搜索
struct Treenode *Nodesearch(struct Treenode *T, int key){
    struct Treenode *p=T;
    while(p!=0){
        if (p->Data==key) 
            return p;
        else if (p->Data>key)
            p=p->Lchild; 
        else 
            p=p->Rchild;
    }
    return 0;
}
int main(){
    struct Treenode *T=0,*p;
    int A[]={45, 23, 76, 32, 66, 78, 52, 18, 90, 75};  
    int n = sizeof(A)/sizeof(A[0]);
    int key;
    printf("enter the key:");
    scanf("%d",&key);

    SortTree(&T,A,n);
    printf("%d",Nodesearch(T,key));
    return 0;
}

在这里插入图片描述