tree.c

c语言一些基础编码

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"

 #include <stdio.h>
#include <conio.h>

#include <stdlib.h>
#include <malloc.h>



#define Null 0
#define MaxSize 64

typedef struct trnode
{
 int data;
 struct trnode *lchild,*rchild;
}BITREE;

typedef BITREE* DataType;

typedef struct stacktag
 {
  BITREE* data[MaxSize];
  int top;
 } STACK;

STACK *s;                     /* s--是顺序栈类型的指针 */
void exchange2(BITREE *tr);   /*  递归方式实现的交换函数 */
BITREE *creat();              /* 建立二叉树 */
void InOrder(BITREE *tr);     /* 中序遍历二叉树 */
void PostOrder(BITREE *tr);


BITREE *creat() /* 建立二叉树 */
{
  BITREE *tr;
  int x;
  printf("\nInput the value of a tree node:\n");
  scanf("%d",&x);
  if(x==0) tr=Null;
  else
  {
   tr=(BITREE *)malloc(sizeof(BITREE));
   tr->data=x;
   tr->lchild=creat();
   tr->rchild=creat();
  }
  return (tr);
 }/* creat */

void InOrder(BITREE *tr) /* 中序遍历二叉树 */
 {
 if(tr!=Null)
 {
   InOrder(tr->lchild);
   printf("%4d",tr->data);
   InOrder(tr->rchild);
 }
}/* end of InOrder */

void exchange(BITREE *tr) /* 借助堆栈实现的交换函数 */
{
 BITREE *p,*t;

/* s是一个指针栈,类型为STACK */

 if(tr!=Null)
 {
  s->top=1;
  s->data[s->top]=tr; /* 根指针进栈 */
  do
  {
   t=s->data[s->top];
   s->top--;
   if((t->lchild!=Null)||(t->rchild!=Null))
    {
      p=t->lchild;
      t->lchild=t->rchild;
      t->rchild=p;
    }
   if(t->lchild!=Null) /* 交换后的左孩子指针入栈 */
    {
      s->top++;
      s->data[s->top]=t->lchild;
    }
   if(t->rchild!=Null)/* 交换后的右孩子指针入栈 */
    {
      s->top++;
      s->data[s->top]=t->rchild;
    }
  } while(s->top!=0 );   /* 栈空结束 */
 } /*end of if(tr!=Null */
}/* end of exchange */




int main()
{
 BITREE *root;
 printf("\n");
 root=creat();
 printf("\n 中序遍历结果为：\n");
 InOrder(root);
 printf("\n");
 exchange(root);
 printf("\n");
 printf("\n交换后中序遍历结果为：\n");
 InOrder(root);
 printf("\n");
 exchange2(root);
 printf("\n再交换后中序遍历结果为：\n");
 InOrder(root);
 printf("\n");
 PostOrder(root);
 getch();
 return 1;
} /* main */

void exchange2(BITREE *tr) /*  递归方式实现的交换函数 */
{
 BITREE *p;
 if(tr!=Null)
 {
  p=tr->lchild;
  tr->lchild=tr->rchild;
  tr->rchild=p;
  exchange(tr->lchild);
  exchange(tr->rchild);
 }
}/* end of exchange2 */

void PostOrder(BITREE *tr)
{
if(tr!=Null)
 {
  PostOrder(tr->lchild);
  PostOrder(tr->rchild);
  free(tr);
 }
}