好人一生平安!Binary Tree

#include
#include
struct node {
intvalue;
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 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:nn");
printf (" 0 Exitn");
printf (" 1 Insert noden");
printf (" 2 Delete noden");
printf (" 3 Find noden");
printf (" 4 Pre order traversaln");
printf (" 5 In order traversaln");
printf (" 6 Post order traversaln");
printf (" 7 Max depthn");
printf (" 8 Min depthn");
printf (" 9 Max valuen");
printf (" 10 Min valuen");
printf (" 11 Node Countnn");
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 ("nn");
insert_node (&tree, option);
break;
case 2:
printf ("Enter number to delete: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("nn");
delete_node (&tree, option);
break;
case 3:
printf ("Enter number to find: ");
fgets (buf, sizeof(buf), stdin);
sscanf (buf, "%i", &option);
printf ("nn");
node = find_node (tree, option);
if (node != NULL) {
printf ("Found nodenn");
} else {
printf ("Couldn't find nodenn");
}
break;
case 4:
printf ("Pre order traversal: ");
pre_order_traversal (tree);
printf ("nn");
break;
case 5:
printf ("In order traversal: ");
in_order_traversal (tree);
printf ("nn");
break;
case 6:
printf ("Post order traversal: ");
post_order_traversal (tree);
printf ("nn");
break;
case 7:
printf ("Max depth is %inn", get_max_depth (tree));
break;
case 8:
printf ("Min depth is %inn", get_min_depth (tree));
break;
case 9:
printf ("Max value is %inn", get_max_value (tree));
break;
case 10:
printf ("Min value is %inn", get_min_value (tree));
break;
case 11:
printf ("Node Count is %inn", get_num_nodes (tree));
break;
}
}
return 0;
}
#include
typedef struct bitnode
{
char data;
struct bitnode *lchild, *rchild;
}bitnode, *bitree;
void createbitree(t,n)
bitnode ** t;
int *n;
{
char x;
bitnode *q;
*n=*n+1;
printf(" Input %d DATA: ",*n);
x=getchar();
if(x!='n') getchar();
if (x=='^')
return;
q=(bitnode*)malloc(sizeof(bitnode));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
*t=q;
printf("This Address is:%o,Data is:%c, Left Pointer is:%o,Right Pointer is: %on",q,q->data,q->lchild,q->rchild);
createbitree(&q->lchild,n);
createbitree(&q->rchild,n);
return;
}
void visit(e)
bitnode *e;
{
printf(" Address: %o, Data: %c, Left Pointer: %o, Right Pointer: %on",e,e->data,e->lchild,e->rchild);
}
void preordertraverse(t)
bitnode *t;
{
if(t)
{
visit(t);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
return ;
}else return ;
}
void countleaf(t,c)
bitnode *t;
int *c;
{
if(t!=NULL)
{
if (t->lchild==NULL && t->rchild==NULL)
{
*c=*c+1;
}
countleaf(t->lchild,c);
countleaf(t->rchild,c);
}
return;
}
int treehigh(t)
bitnode *t;
{
int lh,rh,h;
if(t==NULL)
h=0;
else
{
lh=treehigh(t->lchild);
rh=treehigh(t->rchild);
h=(lh>rh ? lh:rh)+1;
}
return h;
}
main()
{
bitnode *t; int count=0;
int n=0;
clrscr();
printf("Please initialize the TREE!n");
createbitree(&t,&n);
printf("n This is TREE Struct:n");
preordertraverse(t);
countleaf(t,&count);
printf(" This TREE has %d leaves.",count);
printf("n High of The TREE is: %dn",treehigh(t));
puts("n Press any key to quit...");
getch();
}