二叉樹代碼練習

view plaincopy to clipboardprint?#include <stdio.h>  
#include <stdlib.h>  
#include <assert.h>  
 
#define STACK_SIZE 100  
 
typedef struct TREE 
{ 
    char data; 
    struct TREE *left; 
    struct TREE *right; 
}*Tree,Node; 
 
typedef struct STACK 
{ 
    Node node[STACK_SIZE]; 
    int top; 
}Stack; 
 
void init_stack(Stack * stack) 
{ 
    stack->top = 0; 
} 
 
int is_empty(Stack *stack) 
{ 
    return stack->top == 0; 
} 
 
int push(Stack *stack,Node * node) 
{ 
    if(stack->top == STACK_SIZE) 
        return 0; 
 
    stack->node[stack->top++] = *node; 
    return 1; 
} 
 
int top(Stack *stack,Node *node) 
{ 
    if(stack->top == 0) 
        return 0; 
 
    *node = stack->node[stack->top-1]; 
    return 1; 
} 
 
int pop(Stack *stack,Node *node) 
{ 
    if(stack->top == 0) 
        return 0; 
 
    *node = stack->node[--stack->top]; 
    return 1; 
} 
 
void creat_tree(Tree * tree) 
{ 
    char data[1]; 
    scanf("%s",data); 
 
//  char data;  
//  scanf("%c",data); //會把回車當輸入!why?  
 
    if(data[0] == 'a') 
    { 
        *tree = NULL; 
    } 
    else 
    { 
        *tree = malloc(sizeof(Node)); 
        if(*tree == NULL) 
        { 
            exit(0); 
        } 
             
        (*tree)->data = data[0]; 
        creat_tree(&((*tree)->left)); 
        creat_tree(&((*tree)->right)); 
    } 
    return ; 
} 
 
void pre_order(Tree tree) 
{ 
    if(tree == NULL) 
        return ; 
     
    printf("%c",tree->data); 
    pre_order(tree->left); 
    pre_order(tree->right); 
} 
 
void in_order(Tree tree) 
{ 
    if(tree == NULL) 
        return ; 
     
    in_order(tree->left); 
    printf("%c",tree->data); 
    in_order(tree->right); 
} 
 
void post_order(Tree tree) 
{ 
    if(tree == NULL) 
        return ; 
     
    post_order(tree->left); 
    post_order(tree->right); 
    printf("%c",tree->data); 
} 
 
void in_order_stack(Tree tree) 
{ 
    if(tree == NULL) 
        return ; 
 
    Stack stack; 
    init_stack(&stack); 
 
    Node * node = malloc(sizeof(Node)); 
 
    while(!is_empty(&stack) || tree) 
    { 
        if(tree != NULL) 
        { 
            push(&stack,tree); 
            tree = tree->left; 
        } 
        else 
        { 
            pop(&stack,node); 
            printf("%c ",node->data); 
            if(node->right != NULL) 
                tree = node->right; 
        } 
    } 
    printf("\n"); 
} 
 
int tree_heigh(Tree tree) 
{ 
    if(tree == NULL) 
        return 0; 
    else 
    { 
           int left = tree_heigh(tree->left); 
           int right = tree_heigh(tree->right); 
           return left > right ? left+1 : right+1; 
    } 
} 
 
// 1 2 3 a 4 a a a a  
//     1  
//   2   3  
// a  4 a  a  
//   a a  
int main() 
{ 
    Tree tree = NULL; 
    creat_tree(&tree); 
    printf("pre:\n"); 
    pre_order(tree); 
    printf("\nin:\n"); 
    in_order(tree); 
    printf("\npost:\n"); 
    post_order(tree); 
    printf("\n"); 
    printf("Tree heigh is %d\n",tree_heigh(tree)); 
 
    in_order_stack(tree); 
 
    return 0; 
} 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define STACK_SIZE 100

typedef struct TREE
{
 char data;
 struct TREE *left;
 struct TREE *right;
}*Tree,Node;

typedef struct STACK
{
 Node node[STACK_SIZE];
 int top;
}Stack;

void init_stack(Stack * stack)
{
 stack->top = 0;
}

int is_empty(Stack *stack)
{
 return stack->top == 0;
}

int push(Stack *stack,Node * node)
{
 if(stack->top == STACK_SIZE)
  return 0;

 stack->node[stack->top++] = *node;
 return 1;
}

int top(Stack *stack,Node *node)
{
 if(stack->top == 0)
  return 0;

 *node = stack->node[stack->top-1];
 return 1;
}

int pop(Stack *stack,Node *node)
{
 if(stack->top == 0)
  return 0;

 *node = stack->node[--stack->top];
 return 1;
}

void creat_tree(Tree * tree)
{
 char data[1];
 scanf("%s",data);

// char data;
// scanf("%c",data); //會把回車當輸入!why?

 if(data[0] == 'a')
 {
  *tree = NULL;
 }
 else
 {
  *tree = malloc(sizeof(Node));
  if(*tree == NULL)
  {
   exit(0);
  }
   
  (*tree)->data = data[0];
  creat_tree(&((*tree)->left));
  creat_tree(&((*tree)->right));
 }
 return ;
}

void pre_order(Tree tree)
{
 if(tree == NULL)
  return ;
 
 printf("%c",tree->data);
 pre_order(tree->left);
 pre_order(tree->right);
}

void in_order(Tree tree)
{
 if(tree == NULL)
  return ;
 
 in_order(tree->left);
 printf("%c",tree->data);
 in_order(tree->right);
}

void post_order(Tree tree)
{
 if(tree == NULL)
  return ;
 
 post_order(tree->left);
 post_order(tree->right);
 printf("%c",tree->data);
}

void in_order_stack(Tree tree)
{
 if(tree == NULL)
  return ;

 Stack stack;
 init_stack(&stack);

 Node * node = malloc(sizeof(Node));

 while(!is_empty(&stack) || tree)
 {
  if(tree != NULL)
  {
   push(&stack,tree);
   tree = tree->left;
  }
  else
  {
   pop(&stack,node);
   printf("%c ",node->data);
   if(node->right != NULL)
    tree = node->right;
  }
 }
 printf("\n");
}

int tree_heigh(Tree tree)
{
 if(tree == NULL)
  return 0;
 else
 {
        int left = tree_heigh(tree->left);
        int right = tree_heigh(tree->right);
        return left > right ? left+1 : right+1;
 }
}

// 1 2 3 a 4 a a a a
//     1
//   2   3
// a  4 a  a
//   a a
int main()
{
 Tree tree = NULL;
 creat_tree(&tree);
 printf("pre:\n");
 pre_order(tree);
 printf("\nin:\n");
 in_order(tree);
 printf("\npost:\n");
 post_order(tree);
 printf("\n");
 printf("Tree heigh is %d\n",tree_heigh(tree));

 in_order_stack(tree);

 return 0;
}

 作者“kangquan2008的專欄”