好人一生平安!Binary TreeProblem 4 Binary Tree (Difficulty index ★★★★)4-1.Design an algorithm to print the elements of a binary search tree with the element value sorted non-increasingly.Assume that the binary search tree is stored as bi

好人一生平安!Binary TreeProblem 4 Binary Tree (Difficulty index ★★★★)4-1.Design an algorithm to print the elements of a binary search tree with the element value sorted non-increasingly.Assume that the binary search tree is stored as bi
好人一生平安!Binary Tree
Problem 4 Binary Tree (Difficulty index ★★★★)
4-1.Design an algorithm to print the elements of a binary search tree with the element value sorted non-increasingly.Assume that the binary search tree is stored as binary linked-list [二叉链表] and each node contains three domains,respectively namely,“lchild”,“rchild”,and “data”.In your algorithm,except for the intrinsic node space in the binary linked-list,only some pointer variables are permitted to use.Extra element space is prohibited.
4-2.Design a recursive algorithm for searching for the kth(1=

好人一生平安!Binary TreeProblem 4 Binary Tree (Difficulty index ★★★★)4-1.Design an algorithm to print the elements of a binary search tree with the element value sorted non-increasingly.Assume that the binary search tree is stored as bi
#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:\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;
}
#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: %o\n",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: %o\n",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: %d\n",treehigh(t));
puts("\n Press any key to quit...");
getch();
}