算法与数据结构考研试题精析-第６章算法设计题15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#define maxsize 20

typedef struct Node
{
    char data;
    struct Node *firstchild,*nextsibling;
}Node,*BiTree;

int CreateBiTree(BiTree *T);
int TreeHeightRecur(BiTree T);
int TreeHeightCycl(BiTree T);
int Max(int a,int b);
int main()
{
    BiTree *T;
    T=(BiTree *)malloc(sizeof(BiTree));

    CreateBiTree(T);
    int h1,h2;
    h1=TreeHeightRecur(*T);
    h2=TreeHeightCycl(*T);
    printf("%d %dn",h1,h2);
    return 0;
}
int CreateBiTree(BiTree *T)
{
    fflush(stdin);
    printf("please input the node data:");
    char ch;
    scanf("%c",&ch);

    *T=(BiTree)malloc(sizeof(Node));
	(*T)->data=ch;

	char c;
	fflush(stdin);
	printf("Dose %c has children(y--yes,n--no):",ch);
	scanf("%c",&c);
	if(c=='y')
		CreateBiTree(&(*T)->firstchild);
	else
		(*T)->firstchild=NULL;
	fflush(stdin);
    printf("Dose %c has siblings(y--yes,n--no):",ch);
	scanf("%c",&c);
	if(c=='y')
		CreateBiTree(&(*T)->nextsibling);
	else
		(*T)->nextsibling=NULL;
    return 0;
}
int TreeHeightRecur(BiTree T)
{
    if(!T)
        return 0;
    else if(!T->firstchild)
        return Max(1,TreeHeightRecur(T->nextsibling));
    else
    {
        int hc,hs;
        hc=TreeHeightRecur(T->firstchild);
        hs=TreeHeightRecur(T->nextsibling);
        if(hc+1>hs)
            return hc+1;
        else
            return hs;
    }
}
int Max(int a,int b)
{
    return a>b? a:b;
}
int TreeHeightCycl(BiTree T)
{
    BiTree t;
    t=T;

    BiTree Q[maxsize];
    int front,last,rear,h;
    front=h=0;
    last=rear=front+1;

    Q[front]=t;
    while(front!=last)
    {
        t=Q[front];
        front=(front+1)%maxsize;
        //层次遍历
        while(t!=NULL)
        {
            if(t->firstchild)
            {
                Q[rear]=t->firstchild;  //第一子女入队
                rear=(rear+1)%maxsize;
            }
            t=t->nextsibling;  //同层兄弟指针后移
        }
        //如果本层结束，则深度+１
        if(front==last)
        {
            h++;
            last=rear;  //last指针移到刚加入的子女层的最后一位
        }
    }
    return h;
}