二叉树——课上练（顺序存储结构）

#include <stdio.h>
#include <stdlib.h>
/*
定义顺序存储结构
 */
 struct seqTree
 {
   int n;
   char *root;
 };

/*辅助功能：逐个输出顺序表的元素，元素之间以空格为界*/
void printTree(struct seqTree *T)
{
 int i = 0;
 while(i!=T->n){
   printf("%c ",T->root[i]);
   i++;
 }
}

/*第一关*/
struct seqTree *createSeqTree()
{
 //此处编写代码实现二叉树的初始化，包括输入数据
 struct seqTree* tree = (struct seqTree*)malloc(sizeof(struct seqTree));
 tree -> n = 0;
 tree -> root = (char*)malloc(sizeof(char)*100);
 scanf("%c",&tree->root[tree->n]);
 while(tree->root[tree->n]!='\n'){
     tree->n++;
     scanf("%c",&tree->root[tree->n]);
 }
 return tree;
}

/*第二关，返回二叉树的根结点的值，若二叉树为空，则返回#*/
char root(struct seqTree *T)
{
 if(T==NULL)return '#';

 return T->root[0];

}

/*第二关，求二叉树T中指定结点ch的双亲结点，返回值是双亲结点的下标，若双亲不存在，则返回-1*/
int parent(struct seqTree *T ,char ch)
{
    for(int i=0;i<T->n;i++){
        if(T->root[i]==ch&&i!=0)return (i-1)/2;
    }
    
    return -1;
}

/*第二关，求二叉树T中指定结点ch的左孩子的下标，若左孩子不存在，则返回-1*/
int leftChild(struct seqTree *T ,char ch)
{
    if(T==NULL) return -1;
    
    
    for(int i=0;i<T->n;i++){
        int temp = 2*i+1;
        if(T->root[i]==ch&&T->root[temp]!=' ')
            return temp;
    }
    return -1;
}

/*第二关，求二叉树T中指定结点ch的右孩子的下标，若左孩子不存在，则返回-1*/
int rightChild(struct seqTree *T ,char ch)
{

    if(T==NULL)return -1;

    for(int i=0;i<T->n;i++){
        int temp = 2*i+2;
        if(T->root[i]==ch&&T->root[temp]!=' '){
            return temp;
        }
    }
    
    return -1;
}

/*第三关：层序遍历二叉树，输出遍历得到的结点，结点之间不需要空格*/
void levelOrder(struct seqTree *T )
{
    for(int i = 0;i<T->n;i++){
        if(T->root[i]!=' ')printf("%c",T->root[i]);
    }
}

///*第四关：先序遍历二叉树，输出遍历得到的结点，结点之间不需要空格*/
void MyPreOrder(struct seqTree *T,int index){
    if(T==NULL)return;
    
    if(T->root[index]!=' ')  printf("%c",T->root[index]);
   
    if(index<T->n){
        MyPreOrder(T, index*2+1);
        MyPreOrder(T, index*2+2);
    }
    
    
}

void preOrder(struct seqTree *T )
{
    MyPreOrder(T,0);
}


int main(void)
{
        struct seqTree *T = createSeqTree();
//printTree(T); //测评第一关时，把本行代码放开
/*        printf("%c\n",root(T)); //  测评第二关时，把该代码块放开
        printf("%d\n",leftChild(T,'A'));
        printf("%d\n",rightChild(T,'A'));
        printf("%d\n",parent(T,'A'));
*/


  //levelOrder(T); //测评第三关时，把本行代码放开
  preOrder(T); //测评第四关时，把本行代码放开

}


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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130