C语言实现树的动态查找实例代码

时间:2022-01-18 14:00:26

C语言实现树的动态查找实例代码

本例演示一种树数据结构存储记录集合时的动态查找方法。首先程序通过construct()函数,利用已经存在的结构体数组数据建立一个二叉树,建立树的过程中,要保证每个节点的值都大于它的左子树上节点的值而小于它右子树所有节点的值,该函数返回建立树的根指针;然后通过函数Search(root,name)查找,如果找到相应的数据,将其打印出来,如果没有找到,则用户可以选择是否将该数据插入到树中。 

具体代码如下:

?
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM 4
 
struct tree
{
  char name[20];
  char city[20];
  char sex[10];
  char age[10];
  char job[10];
  struct tree *left;
  struct tree *right;
};
 
struct tree Datas[NUM]=
{
  "Willing","Tianjing","Female","21","worker",NULL,NULL,
  "Tom","Beijing","Male","31","doctor",NULL,NULL,
  "Sun","Weifang","Male","24","student",NULL,NULL,
  "Marry","Shanghai","Female","19","techer",NULL,NULL
};
 
struct tree *construct(
  struct tree *root,
  struct tree *r,
  struct tree *Data)
{
  if(!r)
  {
    r = (struct tree *)malloc(sizeof(struct tree));
    if(!r)
    {
      printf("内存分配失败!");
      exit(0);
    }
    r->left = NULL;
    r->right = NULL;
    strcpy(r->name,Data->name);
    strcpy(r->city,Data->city);
    strcpy(r->sex,Data->sex);
    strcpy(r->age,Data->age);
    strcpy(r->job,Data->job);
    if(!root)
      return r;
    if(strcmp(Data->name,root->name)<0)
      root->left = r;
    else
      root->right = r;
    return r;
  }
  if(strcmp(Data->name,r->name)<0)
    construct(r,r->left,Data);
  else
    construct(r,r->right,Data);
 
  return root; 
}
 
struct tree *Search(root,name)
struct tree *root;
char name[];
{
  struct tree *p;
  if(root == NULL)
    printf("该树为空\n");
  p = root;
  while(strcmp(p->name,name)!=0)
  {
    if(strcmp(p->name,name)>0)
      p = p->left;
    else
      p = p->right;
    if(p == NULL)
      break;
  }
  return(p);
}
 
void print(struct tree *r)
{
  if(!r)
    return;
  print(r->left);
  printf("%s\n",r->name);
  print(r->right);
}
 
void print_currentData(struct tree *point)
{
  if(point == NULL)
    return;
  printf("  姓名:%s\n",point->name);
  printf("  城市:%s\n",point->city);
  printf("  性别:%s\n",point->sex);
  printf("  年龄:%s\n",point->age);
  printf("  工作:%s\n",point->job);
}
 
int main(void)
{
  int i;
  char c[10];
  char swap[20];
  char name[20];
  struct tree *root,*p;
  struct tree *temp;
  p = NULL;
  temp = NULL;
  root = NULL;
  for(i = 0;i<NUM;i++)
    root =construct(root,root,&Datas[i]);
  printf("现有人员资料:\n");
  print(root);
  printf("请输入要查找的人的名字\n");
  scanf("%s",name);
  p = Search(root,name);
  if(p == NULL)
  {
    printf("没有该人资料\n");
    printf("是否要插入该人资料[y/n]\n");
    scanf("%s",c);
    if(strcmp(c,"y")==0)
    {
      temp = (struct tree *)malloc(sizeof(struct tree));
      if(!temp)
      {
        printf("内存分配失败!");
        exit(0);
      }
      printf("请输入该人姓名:\n");
      scanf("%s",swap);
      strcpy(temp->name,swap);
      printf("请输入该人所在城市:\n");
      scanf("%s",swap);
      strcpy(temp->city,swap);
      printf("请输入该人性别[Male/Female]:\n");
      scanf("%s",swap);
      strcpy(temp->sex,swap);
      printf("请输入该人年龄:\n");
      scanf("%s",swap);
      strcpy(temp->age,swap);
      printf("请输入该人工作:\n");
      scanf("%s",swap);
      strcpy(temp->job,swap);
      temp->left = NULL;
      temp->right = NULL;
      root =construct(root,root,temp);
      print_currentData(temp);
      printf("现有人员资料:\n");
      root = root;
      print(root);
    }
    else
      return 0;
  }
  print_currentData(p);
  return 1;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://www.okbase.net/doc/details/4391