江西师范大学 数据结构 树与二叉树的遍历 编程作业

1.

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define m 3
#define MAXLEN 100

typedef char datatype;
typedef struct node {
     datatype data;
     struct node *child[m];
} node;
typedef  node *tree;

tree  CreateTree(); /*按前序遍历顺序建立一棵3度树,返回树根地址  */
void LevelOrder(tree t);    /* t为指向树根结点的指针,输出树的层次遍历序列*/
void PreOrder(tree t);    /* t为指向树根结点的指针,输出树的前序遍历序列*/
void PostOrder(tree t); /* t为指向树根结点的指针,输出树的后序遍历序列*/
int main()
{
   tree t;
   t=CreateTree();
   printf("\nthe LevelOrder is:");
   LevelOrder(t);
   printf("\nthe PreOrder is:");
   PreOrder(t);
   printf("\nthe PostOrder is:");
   PostOrder(t);
   return 0;
}
tree  CreateTree()
 {
   int i;
   char ch;
   tree t;
   if ((ch=getchar())=='#')  t=NULL;
   else{
        t=(tree) malloc (sizeof(node));
        t->data=ch;
        for (i=0;i<m;++i)
            t->child[i]= CreateTree();
    }
   return t;
}

void PreOrder(tree t){
    int i;
    if(t!=NULL){
        printf("%c",t->data);
        for(i=0;i<m;i++){
            PreOrder(t->child[i]);
        }
    }
}

void PostOrder(tree t){
    int i;
    if(t!=NULL){
        for(i=0;i<m;i++){
            PostOrder(t->child[i]);
        }
        printf("%c",t->data);
    }
}

void LevelOrder(tree t){
    tree queue[100];
    int f,r,i;
    tree p;
    f=0,r=1;
    queue[0]=t;
    while(f<r){
        p=queue[f++];
        printf("%c",p->data);
        for(i=0;i<m;i++){
            if(p->child[i]){
                queue[r++]=p->child[i];
            }
        }
    }
}

2.

//c++
#include<iostream>
#include <stdlib.h>
#include <malloc.h>
#define m 3
#define MAXLEN 20

typedef char datatype;
typedef struct node {
     datatype data;
     struct node *child[m];
} node;
typedef  node *tree;

tree  CreateTree();
int LeafNodes(tree t);
int Level(tree t,datatype x,int h);
int sum = 0;

int main()
{
   int N,level;
   datatype ch;
   tree t;
   t=CreateTree();
   printf("\nthe LeafNodes is:%d\n",LeafNodes(t));
   scanf("%d",&N);getchar();
   while(N--){
        scanf("%c",&ch);getchar();
        level=Level(t,ch,1);
        if (level==0) printf("the node %c is not exist.\n",ch);
        else printf("the level of the node %c is %d\n",ch,level);
   }
   return 0;
}
int Level(tree t,datatype x,int h)
{
    int level;
    if(t == NULL){
        return 0;
    }
    else {
        if(t->data == x){
            return h;
        }
        else{
            for(int i=0;i<3;i++){
            level = Level(t->child[i],x,h+1);
            if(level != 0){
                return level;
            }
            }
        }
    }
    return 0;
}
int LeafNodes(tree t){
    if(t == NULL){
        return 0;
    }
    int temp = 1;
    if(t){
        for(int i=0; i<3;i++){
            if(t->child[i] != NULL){
                temp = 0;
                break;
            }
        }
        if(temp == 1){
            sum++;
        }
        for(int i=0; i<3;i++){
            if(t->child[i] != NULL){
            LeafNodes(t->child[i]);
        }
        }
    }
    return sum;
}
tree  CreateTree()
 {
   int i;
   char ch;
   tree t;
   if ((ch=getchar())=='#')  t=NULL;
   else{
        t=(tree) malloc (sizeof(node));
        t->data=ch;
        for (i=0;i<m;++i)
            t->child[i]= CreateTree();
    }
   return t;
}