creatbinarytree.txt

随机生成25个整数

#include<stdio.h>
#include<stdlib.h>
#define N 25

/*----------------------------------------------------------------*/
typedef struct BiTNode
{
int data;
int tag;
     struct BiTNode *lchild,*rchild,*parent;
}BiTNode,* btree;

typedef struct stack
{
int *base;
int *top;
int stacksize;
}stack;

btree Creat(btree t,int num[],int n,int i);
void preOrder(btree t);
void inOrder(btree t);
void endOrder(btree t);
void Path(int tree[],btree r);
stack* initstack();
void push(stack* p,int n);
void pop(stack* p);
/*----------------------------------------------------------------*/
btree Creat(btree t,int num[],int n,int i)//构建二叉树
{
if(i>n)
   return NULL;
btree r=(btree)malloc(sizeof(BiTNode));
if(r==NULL)
{
   printf("空间分配失败!\n");
   return NULL;
}
r->parent=t;
r->data=num[i];
r->tag=0;     //标记该结点已被访问的次数
r->lchild=Creat(r,num,n,2*i);
r->rchild=Creat(r,num,n,2*i+1);
return r;
}

void preOrder(btree t)//先根遍历二叉树
{
if(t==NULL)
   return;
else
{
   if(t->data<11&&t->data>=1)
    printf("%d   ",t->data);
   else
    printf("*   ");
}
preOrder(t->lchild);
preOrder(t->rchild);
return;
}

void inOrder(btree t)//中根遍历二叉树
{
if(t==NULL)
   return;
inOrder(t->lchild);
if(t->data<11&&t->data>=1)
   printf("%d   ",t->data);
else
   printf("*   ");
inOrder(t->rchild);
return;
}

void endOrder(btree t)//后根遍历二叉树
{
if(t==NULL)
   return;
endOrder(t->lchild);
endOrder(t->rchild);
if(t->data<11&&t->data>=1)
   printf("%d   ",t->data);
else
   printf("*   ");
return;
}

stack* initstack()//初始化栈
{
stack *p=(stack*)malloc(sizeof(stack));
p->base=(int*)malloc(N*sizeof(int));
p->top=p->base;
p->stacksize=N;
return p;
}

void push(stack* p,int n)//入栈
{
*p->top++=n;
return;
}

void pop(stack* p)//出栈
{
--p->top;
return;
}

void Path(int tree[],btree r)    //按先根的次序查找路径
{
int num,i,j;
int *a;
btree t=r->parent;   //t记录当前结点的parent结点
stack* path;     //构造空栈path
printf("\n请输入要查找的整数:\n");
scanf("%d",&num);
i=1;
j=0;
while(tree[i]!=num) //检查所要查找的数是否在二叉树中
   i++;
if(i>N)
   printf("该数不在二叉树中!\n");
else                 //若在二叉树中则查找路径
{
   printf("从根开始的路径为:\n");
   path=initstack();
   i=0;              //i记录已经访问过的结点数
   while(i<N)        //当尚未访问所有的结点时
   {
    if(r==NULL)
    {
     r=t;
     t=t->parent;
    }
    else if(r->tag==0)//第一次访问该结点
    {
     if(r->data!=num)
     {
      push(path,r->data);
      r->tag=1;
      t=r;
      r=r->lchild;
      i++;
     }
     else
     {
      push(path,r->data);
      break;
     }
    }
    else if(r->tag==1)//第二次访问该结点
    {
     r->tag=2;
     t=r;
     r=r->rchild;
    }
    else if(r->tag==2)//第三次访问该结点
    {
     pop(path);
     r=t;
     t=t->parent;
    }
   }//while
   a=path->base;
   while(a<path->top)
   {
    printf("%d   ",*a);
    a++;
   }
   free(path);
}//else
return;
}//Path

/*-----------------------------------------------------------------*/
void main()
{
int i,num[N+1];
for(i=1;i<=N;i++)
   num[i]=rand()%25;//数组的第0号位置不放入元素
printf("结点元素有:\n");
for(i=1;i<N+1;i++)
   printf("%d   ",num[i]);
printf("\n其中真实结点有:\n");
for(i=1;i<N+1;i++)
   if(num[i]<=10)
    printf("%d   ",num[i]);
printf("\n");
btree r,t;
t=NULL;
r=Creat(t,num,N,1);
printf("先根遍历各结点依次为:\n");
preOrder(r);
printf("\n中根遍历各结点依次为:\n");
inOrder(r);
printf("\n后根遍历各结点依次为:\n");
endOrder(r);
Path(num,r);
}