二叉树学习

tree.h

tree.h
#ifndef _TREE_H
#define _TREE_H

typedef struct node
{
    char data;
    struct node * lchild,* rchild;

}TREE;

#endif

stack.h

#ifndef _STACK_H
#define _STACK_H //避免重复定义 导入重复

#include "tree.h"
#define ElemType TREE *

#define STACK_INIT_SIZE 10
#define STACK_INCREME 10

typedef struct
{
   ElemType * base; //为了实现通用，定义这样一个数据类型的指针
   ElemType * top;
   int size;
}STACK;

STACK * InitStack();
void Destroy(STACK *s);
int Push(STACK *s,ElemType *e);
int Pop(STACK *s,ElemType *e);
int IsEmpty(s);

#endif

stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"


STACK * InitStack()
{
  STACK * s =(STACK *)malloc(sizeof(STACK));
   if(s==NULL)
       exit(0);
   s->base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(s->base==NULL) exit(0);
    s->top=s->base;
    s->size=STACK_INIT_SIZE;
    return s;
}

int Push(STACK *s,ElemType *e)
{
    if(s==NULL||e==NULL) //检查参数的合法性
        return 0;
    if(s->top -s ->base >=s->size)
    {
        s->base=(ElemType *)realloc(s->base,
            (s->size +STACK_INCREME) * sizeof(ElemType));
        if(s->base==NULL)
            return 0;
        s->top=s->base+s->size;
        s->size=s->size+STACK_INCREME;
    }
    // *s->top=*e;
    // s->top++;
    *s->top++ = *e;
    return 1;
}

int Pop(STACK *s,ElemType *e)
{
    if(s==NULL || e==NULL)
        return 0;
    if(s->top==s->base)
        return 0;
    *e =*--s->top;
    return 1;
}

int IsEmpty(STACK *s)
{
    return s->top ==s->base ? 1: 0;
}

void Destroy(STACK *s)
{
    free(s->base);
    free(s);
}

tree.c

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include "tree.h"
#include "stack.h"

TREE * MakeTree()
{
   TREE * t;
   char ch;
   ch=getche();
   if(ch == '#')
     return NULL;
   t=(TREE *)malloc(sizeof(TREE));
   if(t==NULL)
     return NULL;
   t->data=ch;
   t->lchild = MakeTree();
   t->rchild = MakeTree();
   return t;
}

void PrintTreeByBefore(TREE *t)
{
   if(t == NULL)
     return;
   printf("[%c]",t->data);
   PrintTreeByBefore(t->lchild);
   PrintTreeByBefore(t->rchild);
}

void PrintTreeByMid(TREE *t)
{
    TREE *p = t;
    STACK *s=InitStack();
    Push(s,&t);
    while(!IsEmpty(s))
    {
     while(p)
        {
           p=p->lchild;
           Push(s,&p); //将左结点的空孩子结点压入了栈
        }
        Pop(s,&p); //先弹出的是空结点
     if(!IsEmpty(s))
        {
           Pop(s,&p);
           printf("[%c]",p->data);
         p = p->rchild;
           Push(s,&p);
        }
    }
    Destroy(s);
}
void main()
{
   TREE *tree =MakeTree();
    PrintTreeByBefore(tree);
    printf("\n\n******************\n");
    PrintTreeByMid(tree);

}

学习文档：

 二叉树.rar   

辛苦整理，欢迎拍砖！