C语言数据结构课程设计
发布网友
发布时间：2022-05-01 17:16
共2个回答
热心网友
时间：2022-06-20 04:18
下面的是树的各种操作的一个完整的c程序，在win-tc和Dev-c++下运行通过。
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node* left;
struct node* right;
};
typedef struct node NODE;
typedef struct node* PNODE;
void new_node (PNODE* n, int value) {
*n = (PNODE)malloc (sizeof(NODE));
if (*n != NULL) {
(*n)->value = value;
(*n)->left = NULL;
(*n)->right = NULL;
}
}
void free_node (PNODE* n) {
if ((*n) != NULL) {
free (*n);
*n = NULL;
}
}
void free_tree (PNODE* n) {
if (*n == NULL) return;
if ((*n)->left != NULL) {
free_tree (&((*n)->left));
}
if ((*n)->right != NULL) {
free_tree (&((*n)->right));
}
free_node (n);
}
/* 查找结点 */
PNODE find_node (PNODE n, int value) {
if (n == NULL) {
return NULL;
} else if (n->value == value) {
return n;
} else if (value <= n->value) {
return find_node (n->left, value);
} else {
return find_node (n->right, value);
}
}
/* 插入结点 */
void insert_node (PNODE* n, int value) {
if (*n == NULL) {
new_node (n, value);
} else if (value == (*n)->value) {
return;
} else if (value < (*n)->value) {
insert_node (&((*n)->left), value);
} else {
insert_node (&((*n)->right), value);
}
}
/* 最长路径 */
int get_max_depth (PNODE n) {
int left = 0;
int right = 0;
if (n == NULL) {
return 0;
}
if (n->left != NULL) {
left = 1 + get_max_depth (n->left);
}
if (n->right != NULL) {
right = 1 + get_max_depth (n->right);
}
return (left > right ? left : right );
}
/* 最短路径 */
int get_min_depth (PNODE n) {
int left = 0;
int right = 0;
if (n == NULL) {
return 0;
}
if (n->left != NULL) {
left = 1 + get_min_depth (n->left);
}
if (n->right != NULL) {
right = 1 + get_min_depth (n->right);
}
return (left < right ? left : right );
}
int get_num_nodes (PNODE n) {
int left = 0;
int right = 0;
if (n == NULL) {
return 0;
}
if (n->left != NULL) {
left = get_num_nodes (n->left);
}
if (n->right != NULL) {
right = get_num_nodes (n->right);
}
return (left + 1 + right);
}
/* 最短路径长度 */
int get_min_value (PNODE n) {
if (n == NULL) return 0;
if (n->left == NULL) {
return n->value;
} else {
return get_min_value(n->left);
}
}
/* 最长路径长度 */
int get_max_value (PNODE n) {
if (n == NULL) return 0;
if (n->right == NULL) {
return n->value;
} else {
return get_max_value(n->right);
}
}
/* 删除结点 */
void deletenode (PNODE *n) {
PNODE tmp = NULL;
if (n == NULL) return;
if ((*n)->right == NULL) {
tmp = *n;
*n = (*n)->left;
free_node (n);
} else if ((*n)->left == NULL) {
tmp = *n;
*n = (*n)->right;
free_node (n);
} else {
for (tmp = (*n)->right; tmp->left != NULL; tmp = tmp->left);
tmp->left = (*n)->left;
tmp = (*n);
*n = (*n)->right;
free_node (&tmp);
}
}
void delete_node (PNODE *n, int value) {
PNODE node;
if (n == NULL) return;
node = find_node (*n, value);
if ((*n)->value == value) {
deletenode (n);
} else if (value < (*n)->value) {
delete_node (&((*n)->left), value);
} else {
delete_node(&((*n)->right), value);
}
}
void pre_order_traversal(PNODE n)
{
if (n != NULL) {
printf ("%i ", n->value);
pre_order_traversal (n->left);
pre_order_traversal( n->right);
}
}
void in_order_traversal (PNODE n)
{
if (n != NULL) {
in_order_traversal (n->left);
printf ("%i ", n->value);
in_order_traversal ( n->right);
}
}
void post_order_traversal (PNODE n)
{
if (n != NULL) {
post_order_traversal (n->left);
post_order_traversal (n->right);
printf ("%i ", n->value);
}
}
int main() {
char buf[50];
int option;
PNODE tree = NULL;
PNODE node = NULL;
while (1) {
printf ("--------------------------\n");
printf ("Options are:\n\n");
printf (" 0 Exit\n");
printf (" 1 Insert node\n");
printf (" 2 Delete node\n");
printf (" 3 Find node\n");
printf (" 4 Pre order traversal\n");
printf (" 5 In order traversal\n");
printf (" 6 Post order traversal\n");
printf (" 7 Max depth\n");
printf (" 8 Min depth\n");
printf (" 9 Max value\n");
printf (" 10 Min value\n");
printf (" 11 Node Count\n\n");
printf ("--------------------------\n");
printf ("Select an option: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("--------------------------\n");
if (option < 0 || option > 11) {
fprintf (stderr, "Invalid option");
continue;
}
switch (option) {
case 0:
exit (0);
case 1:
printf ("Enter number to insert: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
insert_node (&tree, option);
break;
case 2:
printf ("Enter number to delete: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
delete_node (&tree, option);
break;
case 3:
printf ("Enter number to find: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("\n\n");
node = find_node (tree, option);
if (node != NULL) {
printf ("Found node\n\n");
} else {
printf ("Couldn't find node\n\n");
}
break;
case 4:
printf ("Pre order traversal: ");
pre_order_traversal (tree);
printf ("\n\n");
break;
case 5:
printf ("In order traversal: ");
in_order_traversal (tree);
printf ("\n\n");
break;
case 6:
printf ("Post order traversal: ");
post_order_traversal (tree);
printf ("\n\n");
break;
case 7:
printf ("Max depth is %i\n\n", get_max_depth (tree));
break;
case 8:
printf ("Min depth is %i\n\n", get_min_depth (tree));
break;
case 9:
printf ("Max value is %i\n\n", get_max_value (tree));
break;
case 10:
printf ("Min value is %i\n\n", get_min_value (tree));
break;
case 11:
printf ("Node Count is %i\n\n", get_num_nodes (tree));
break;
}
}
return 0;
}
热心网友
时间：2022-06-20 04:18
