数据结构实验:二叉树的遍历(C语言版)

分手后的思念是犯贱 2022-06-07 10:50 280阅读 0赞

\#include<stdio.h>  
\#include<stdlib.h>  
//二叉树结点定义  
typedef struct BITNode  
\{  
char data;  
struct BITNode \*lchild,\*rchild;  
\} BITNode,\*BITree;  
static int length=0;//二叉树结点个数  
//静态二叉链表  
typedef struct ATNode  
\{  
char data;  
int lchild;  
int rchild;  
\} ATNode;  
ATNode Array\[100\];//存储二叉链表结点  
//先序创建二叉树  
void CreateBITree(BITree \*T)  
\{  
char ch;  
scanf("%c",&ch);  
if(ch==' ')  
\*T=NULL;  
else  
\{  
\*T=(BITree )malloc(sizeof(BITNode));  
(\*T)->data=ch;  
CreateBITree(&((\*T)->lchild));  
CreateBITree(&((\*T)->rchild));  
\}  
\}  
//先序遍历二叉树  
void VisitBitree(BITree T)  
\{  
if(T)  
\{  
length++;  
Array\[length\].data=T->data;  
VisitBitree(T->lchild);//访问左孩子  
VisitBitree(T->rchild);//访问右孩子  
\}  
\}  
void Visit(BITree T)  
\{  
if(T)\{  
Visit(T->lchild);  
printf("%c->",T->data);  
Visit(T->rchild);  
\}  
\}  
//二叉树转化为静态二叉链表  
void BitreeTransform(BITree T)  
\{  
int i,j;  
if(T)  
\{  
j=1;  
while(T->data!=Array\[j\].data)  
j++;//确定T结点的数组下标  
if(T->lchild!=NULL)  
\{  
i=j;  
while(T->lchild->data!=Array\[i\].data)  
i++;//确定T->lchild结点的数组下标  
Array\[j\].lchild=i;  
\}  
else  
Array\[j\].lchild=0;  
if(T->rchild!=NULL)  
\{  
i=j;  
while(T->rchild->data!=Array\[i\].data)  
i++;//确定T->rchild结点的数组下标  
Array\[j\].rchild=i;  
\}  
else\{  
Array\[j\].rchild=0;  
BitreeTransform(T->lchild);  
BitreeTransform(T->rchild);  
\}  
\}  
\}  
void main()  
\{  
int j;  
printf("创建一个带节点的二叉链表：\\n");  
BITree T=NULL;//T为空二叉树  
CreateBITree(&T);//创建一棵二叉树  
printf("中序遍历结果为：\\n");  
VisitBitree(T);  
Visit(T);  
printf("\\n");  
BitreeTransform(T);  
printf("转化为静态二叉链表：\\n");  
printf("位置\\tlchild\\tdata\\trchild\\n");  
for(j=1; j<=length; j++)  
\{  
printf("%d\\t%d\\t%c\\t%d\\n", j,Array\[j\].lchild, Array\[j\].data, Array\[j\].rchild);  
\}  
\}