二叉树的实现(C语言)

#include<stdio.h>

#include<malloc.h>

struct Tree;

typedef Tree* BinTree;

typedef char BinTreeNode;

struct Tree

{

char data;

BinTree left;

BinTree right;

};

BinTree createEmptyBinTree(void) //创建一棵空的二叉树。

{

BinTree p;

p=(BinTree)malloc(sizeof(Tree));

return p;

}

int isNull ( BinTree t ) //判断二叉树t是否为空。

{

if(t==NULL)

{

printf("此二叉树为空！\n");

return 0;

}

else

return 1;

}

BinTree consBinTree()//建立一棵二叉树，其根结点是root，左右二叉树分别为left和right {

BinTree root;

char ch;

scanf("%c",&ch);

if ((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'))

{

root=createEmptyBinTree();

root->data=ch;

root->left=consBinTree();

root->right=consBinTree();

}

else

root=NULL;

}

BinTreeNode root( BinTree t )//返回二叉树t的根结点。若为空二叉树，则返回一特殊值。 {

if(t==NULL)

return NULL;

else

return t->data;

}

void visit(BinTreeNode c)

{

printf("%c ",c);

}

BinTree leftChild( BinTree t )//返回t结点的左子树，当指定结点没有左子树时，返回一个特殊值。

{

if(t->left==NULL)

return NULL;

else

return t->left;

}

BinTree rightChild( BinTree t)//返回p结点的右子树，当指定结点没有右子树时，返回一个特殊值。

{

if(t->right==NULL)

return NULL;

else

return t->right;

}

void preOrder( BinTree t)//显示先根周游序列

{

if(t!=NULL)

{

visit(root(t));

preOrder(leftChild(t));

preOrder(rightChild(t));

}

void inOrder(BinTree t)//显示中根周游序列

{

if (t!=NULL)

{

inOrder(leftChild(t));

visit(root(t));

inOrder(rightChild(t));

}

}

void postOrder(BinTree t)//显示后根周游序列

{ if (t!=NULL)

{

postOrder(leftChild(t));

postOrder(rightChild(t));

visit(root(t));

}

}

void show(BinTree t,int len)//数的形状

{

if (t!=NULL)

{

show(t->right,len+1);

for (int i=1;i<=len;i++)

{

printf(" ");

}

printf("%c\n",t->data);

show(t->left,len+1);

}

}

int main()

{

BinTree p1;

int k=1,num;

while(k)

{

printf("\n&&&&&&&&&&&&&&输入序&&&&&&&&&&&&&&&&&\n");

printf(" 输入1，建立一个二叉树！号执行\n"); 相应操作

printf(" 输入2，查看建立的二叉树！\n"); printf("---------------------------------------------------\n"); printf(" 输入3，先根周游二叉树！\n"); printf("---------------------------------------------------\n"); printf(" 输入4，中根周游二叉树！\n"); printf("---------------------------------------------------\n"); printf(" 输入5，后根周游二叉树！\n"); printf("---------------------------------------------------\n"); printf(" 输入其他，退出操作！\n"); printf("---------------------------------------------------\n"); scanf("%d",&num);

switch (num)

{

case 1 :

while(!(p1=consBinTree()))

\n");

printf("请按照先根顺序输入二叉树元素(大小写字母),空格代表子树为空 if(p1) printf("二叉树建立成功！\n"); else printf("二叉树建立失败！\n"); break; case 2 : { printf("建立的二叉树形状为：\n\n"); if(isNull(p1)) show(p1,0); } break; case 3 : { printf("先根周游序列为：\n"); preOrder(p1); printf("\n"); } break; case 4 : { printf("中根周游序列为：\n"); inOrder(p1); printf("\n"); } break;

} { printf("后根周游序列为：\n"); postOrder(p1); printf("\n"); } break; default : printf("您未选定任何操作！请重新输入操作序号！\n") ; k=0; break; } } return 0;