#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
typedef struct BiTNode
{
int data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
void visit(int e)
{
printf("->%d",e);
}
void InitBiTree(BiTree &T)// 操作结果:构造空二叉树T
{
T=NULL;
}
void CreateBiTree(BiTree &T)
//按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树T。变量Nil表示空(子)树。
{
int number;
scanf("%d",&number); // 输入结点的值
if(number==0) // 结点的值为空
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)// 初始条件:二叉树T存在。操作结果:销毁二叉树T
{
if(T) // 非空树
{
DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
//二叉树T存在,Visit是对结点操作的应用函数,先序递归遍历T,对每个结点调用函数Visit一次且仅一次
{
if(T) //T不为空时遍历
{
Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
//二叉树T存在,Visit是对结点操作的应用函数,中序递归遍历T,对每个结点调用函数Visit一次且仅一次
{
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
// 二叉树T存在,Visit是对结点操作的应用函数,后序递归遍历T,对每个结点调用函数Visit一次且仅一次
{
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
char m;
BiTree T;
InitBiTree(T); // 初始化二叉树T
do{
printf("\n");
printf("##################二叉树的基本操作###########################\n");
printf("×××××××××1.二叉树的创建××××××××××××××\n");
printf("×××××××××2.先序递归遍历二叉树×××××××××××\n");
printf("×××××××××3.中序递归遍历二叉树×××××××××××\n");
printf("×××××××××4.后序递归遍历二叉树×××××××××××\n");
printf("×××××××××5.退出程序××××××××××××××××\n");
printf("#############################################################\n");
printf("请输入你的选择:");
scanf("%c",&m);
switch(m) {
case '1':
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,如:(1 2 3 0 0 4 5 0 6 0 0 7 0 0 0)\n");
printf("\n请按先序次序输入二叉树中结点的值:");
CreateBiTree(T); // 建立二叉树T
break;
case '2':
printf("先序递归遍历二叉树: ");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
break;
case '3':
printf("\n中序递归遍历二叉树: ");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
break;
case '4':
printf(" \n后序递归遍历二叉树:");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
break;
case '5':break;
default:
printf("输入的字符不对,请重新输入!");
break;
}
getchar();
}while(m!='5');
}
温馨提示:答案为网友推荐,仅供参考