如何建立个二叉树

发布网友发布时间：2022-04-29 18:26

共1个回答

热心网友时间：2022-06-19 01:09

输入二叉数的各个结点值，按二叉链表的存储形式建立该二叉数，然后输出先序遍历、中序遍历和层次遍历的序列。
实现函数：
#include<stdio.h>
#include<math.h>
#define NULL 0
#define OK 1
#define ERROR 0
/*-----------------------------------------------------------------*/
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*-----------------------------------------------------------------*/
typedef struct{
BiTNode *base[100];
int front;
int rear;
}sq;
/*-----------------------------------------------------------------*/
sq initqueue()
{ sq q; int i;
for(i=0;i<100;i++) {
q.base[i]=NULL;
q.front=q.rear=0;}
return q;}
/*-----------------------------------------------------------------*/
int PrintElement(char e){
printf("%c",e);
return OK;
}
/*-----------------------------------------------------------------*/
BiTree createTree()
{
char ch;
BiTree bt;
scanf("%c",&ch);
if(ch==' ') return NULL;
else
{
bt=(BiTree)malloc(sizeof(BiTNode));
if(!bt) return NULL;
bt->data=ch;
bt->lchild=createTree();
bt->rchild=createTree();
}
return bt;
}
/*-----------------------------------------------------------------*/
int PreOrderTraverse(BiTree T)
{
if(T)
{
if(PrintElement(T->data))
if(PreOrderTraverse(T->lchild))
if(PreOrderTraverse(T->rchild))
return OK;
return ERROR;
}
else
return OK;
}
/*-----------------------------------------------------------------*/
int InOrderTraverse(BiTree T){
if(T)
{
if(InOrderTraverse(T->lchild))
if(PrintElement(T->data))
if(InOrderTraverse(T->rchild))
return OK;

return ERROR;
}
else
return OK;
}
/*-----------------------------------------------------------------*/
int PostOrderTraverse(BiTree T) {
if(T)
{
if(PostOrderTraverse(T->lchild))
if(PostOrderTraverse(T->rchild))
if(PrintElement(T->data))
return OK;
return ERROR;
}
else
return OK;
}
/*-----------------------------------------------------------------*/
int trverse(BiTree T)
{ sq q;
BiTree e;
q=initqueue();
printf("%c",T->data);
if(T->lchild) {q.base[q.rear]=T->lchild;q.rear=q.rear+1;}
if(T->rchild) {q.base[q.rear]=T->rchild;q.rear=q.rear+1;}
while(q.front!=q.rear){
e=q.base[q.front];q.base[q.front]=NULL;q.front=q.front+1;
if(e){
if(e->lchild) {q.base[q.rear]=e->lchild;q.rear=q.rear+1;}
if(e->rchild) {q.base[q.rear]=e->rchild;q.rear=q.rear+1;}
PrintElement(e->data);}}
return OK;}
/*-----------------------------------------------------------------*/
main()
{ BiTree T;
printf("Copyright@LiuYong2005\nplease input a tree:\t");
T=createTree();
printf("preOrder:\n\t");
PreOrderTraverse(T);
printf("\ninOrder:\n\t");
InOrderTraverse(T);
printf("\npostOrder:\n\t");
PostOrderTraverse(T);
printf("\ntrverse:\n\t");
trverse(T);
}