代码: 全选
// Tree Structure | Binary Tree
// linked storage form
// Last Modified: 2008-06-16
// Last Modified: 2008-07-05
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
char data;
struct node *left, *right;
} node, *tree;
void create(tree *t);
void preorder_traverse(tree t);
void inorder_traverse(tree t);
void postorder_traverse(tree t);
int get_depth(tree t);
void get_leaf(tree t);
int leaves = 0;
void create(tree *t)
{
int key = getchar();
if (key != '.')
{
*t = (tree)malloc(sizeof(node));
if (*t == NULL)
printf("\n overflow ");
(*t)->data = key;
create(&((*t)->left));
create(&((*t)->right));
}
else
{
*t = NULL;
}
}
void preorder_traverse(tree t)
{
if (t)
{
printf("\n %c ", t->data);
preorder_traverse(t->left);
preorder_traverse(t->right);
}
}
void inorder_traverse(tree t)
{
if (t)
{
inorder_traverse(t->left);
printf("\n %c ", t->data);
inorder_traverse(t->right);
}
}
void postorder_traverse(tree t)
{
if (t)
{
postorder_traverse(t->left);
postorder_traverse(t->right);
printf("\n %c ", t->data);
}
}
int get_depth(tree t)
{
int hl, hr, depth;
if (t != NULL)
{
hl = get_depth(t->left);
hr = get_depth(t->right);
depth = (hl > hr) ? hl : hr;
return depth + 1;
}
else
{
return 0;
}
}
void get_leaf(tree t)
{
if (t)
{
if (!t->left && !t->right)
{
printf("\n leaf = %c ", t->data);
leaves++;
}
get_leaf(t->left);
get_leaf(t->right);
}
}
int main()
{
tree t;
printf("\n");
printf("\n Create Tree ");
printf("\n");
printf("\n 1234567890");
printf("\n ");
create(&t);
printf("\n");
printf("\n Preorder Traverse Tree ");
printf("\n");
preorder_traverse(t);
printf("\n");
printf("\n Inorder Traverse Tree ");
printf("\n");
inorder_traverse(t);
printf("\n");
printf("\n Postorder Traverse Tree ");
printf("\n");
postorder_traverse(t);
printf("\n");
printf("\n Depth: %d ", get_depth(t));
printf("\n");
printf("\n Leaves of Tree ");
get_leaf(t);
printf("\n");
printf("\n Leaves: %d ", leaves);
printf("\n");
return 0;
}