数据结构常见问题 二叉树的基本运算

二叉树的基本运算

数据结构常见问题 二叉树的基本运算（C语言）2007年05月09日 星期三 13:19/*[问题描述] 随机生成25个整数，介于1～10间为真实节点，其余为虚节点。将这一生成理解成完全二叉树，构造生成一棵完全二叉树。在此基础上执行：先根、中根、后根遍历；指定一节点整数，可给出其从根开始的路径。
[基本要求] 二叉树采用链式方式存储。*/

#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&quo
t;);
preOrder(r);
printf("\n中根遍历各结点依次为:\n");
inOrder(r);
printf("\n后根遍历各结点依次为:\n");
endOrder(r);
Path(num,r);
}

本文来源：https://www.bwwdw.com/article/iiqj.html