#include
#include
#define num 100
#define OK 1
typedef int Status;
typedef char DataType;
typedef struct node
{
DataType data;
struct node *lchild,*rchild;
}BinTNode,*BinTree;
int found;
BinTNode *p;
/*****************建立二叉树*****************/
Status CreateBiTree(BinTree &bt) //1.按照先序遍历次序递建立二叉树
{
char ch;
printf("ch=");
scanf("%c",&ch);
getchar();
if (ch==' ') bt=NULL; //程序中直接输入空格停止
else
{ bt=(BinTNode *)malloc(sizeof(BinTNode));
bt->data=ch; //生成根结点
printf("请输入左子树:\n");
CreateBiTree(bt->lchild);
printf("请输入右子树:\n"); //构造左子树
CreateBiTree(bt->rchild); //构造右子树
} return OK;
}
/*****************中序遍历二叉树*****************/
Status Inorder(BinTree bt) //中序遍历算法
{
BinTNode *stack[num]; //定义栈数组
int top=0; //初始化栈
stack[top]=bt;
do
{ while(NULL!=stack[top]) //扫描根结点及其所有的左结点并入栈
{ top=top+1;
stack[top]=stack[top-1]->lchild;
}
top=top-1; //退栈
if(top>=0) //判断栈是否为空
{ printf("%c",stack[top]->data); //访问结点
stack[top]=stack[top]->rchild; //扫描右子树
}
}while(top>=0);
return OK;
}
/*Status Inorder(BinTree bt) //先序遍历算法
{
BinTNode *stack[num]; //定义栈数组
int top=0; //初始化栈
stack[top]=bt;
do
{ while(NULL!=stack[top]) //扫描根结点及其所有的左结点并入栈
{ top=top+1;
printf("%c",stack[top]->data);
stack[top]=stack[top-1]->lchild;
}
top=top-1; //退栈
if(top>=0) //判断栈是否为空
{ printf("%c",stack[top]->data); //访问结点
stack[top]=stack[top]->rchild; //扫描右子树
}
}while(top>=0);
return OK;
}
*/
/*****************求指定节点路径*****************/
BinTree NodePath(BinTree bt, BinTNode *ch) //3.求二叉树指定结点的路径
{ typedef enum{FALSE,TRUE}boolean;
BinTNode *stack[num];//定义栈
int i,top,tag[num];
boolean find;//定义布尔类型变量
BinTNode *s;
find=FALSE;//初始化
top=0;
s=bt;
do
{while(s!=NULL)
{ top++;
stack[top]=s;
tag[top]=0;
s=s->lchild;
}
if(top>0)
{s=stack[top];
if(tag[top]==1)
{ if(s==ch)
{for(i=1;i<=top;i++)
printf("->%c",stack[i]->data);
find=TRUE;
}else top--;
s=stack[top];
}
if(top>0&&!find)
{ if(tag[top]!=1)
{ s=s->rchild;//扫描右子树
tag[top]=1;
} else s=NULL;
}
}
}while(!find&&top!=0);
return s;
}
void FindBT(BinTree bt,DataType x)
{ if((bt!=NULL)&&!found)
{ if(bt->data==x)
{ p=bt;
found=1;
} else
{ FindBT(bt->lchild,x);
FindBT(bt->rchild,x);
}
}
}
BinTNode *Findx(BinTree bt,DataType x)
{ int found=0;
BinTree p=NULL;
FindBT(bt,x);
return(p);
}
/*****************求二叉树的深度*****************/
int Depth(BinTree bt) //4.求二叉树的深度
{ int h,lh,rh;
if (bt==NULL) h=0;
else
{ lh=Depth(bt->lchild);
rh=Depth(bt->rchild);
if (lh>=rh) h=lh+1;
else h=rh+1;
} return h;
}
/*****************求叶子节点的个数*****************/
int Leaf(BinTree bt) //5.求二叉树的叶子结点个数
{ if (bt==NULL) return 0;
else if (bt->lchild==NULL&&bt->rchild==NULL)
return OK;
else return Leaf(bt->lchild)+Leaf(bt->rchild);
}
/*****************调换左右子树*****************/
BinTNode *huhuan(BinTNode *p)//6.将p指针指向的二叉树的左右子树进行互换
{BinTNode *stack[num];//指针类型的堆栈
int k=0;
stack[k]=NULL;
if(p!=NULL)//交换p结点的左右孩子
{ k++;
stack[k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=huhuan(p->lchild);
p->rchild=huhuan(p->rchild);
} return (p);
}
/*****************主函数*****************/
void main()
{ BinTree bt;
char ch1;
int xz=1,sd=0,yz=0;
while(xz)
{ printf(" 建立二叉树并求指定结点路径 \n");
printf("============================\n");
printf(" 1.建立二叉树的存储结构 \n");
printf(" 2.求解二叉树的中序遍历 \n");
printf(" 3.求二叉树指定结点的路径 \n");
printf(" 4.求二叉树的深度 \n");
printf(" 5.求二叉树的叶子结点个数 \n");
printf(" 6.将二叉树左右子树交换 \n");
printf(" 0.退出系统 \n");
printf("============================\n");
printf(" 请选择:(0-6) \n");
scanf("%d",&xz);
getchar();
switch(xz)
{
case 1: printf("请输入根节点:\n");
CreateBiTree(bt);
printf( "二叉树的链式存储结构建立完成!\n");
break;
case 2:printf("该二叉树的中序遍历序列是:\n");
Inorder(bt);
printf( "\n");
break;
case 3:printf( "请输入要求路径的结点值:\n" );
ch1=getchar();
p=NULL;
found=0;
Findx(bt,ch1);
if(p!=NULL)
NodePath(bt,p);
else
printf( "没有要求的节点! \n" );
printf( "\n" );
break;
case 4:sd=Depth(bt);
printf( "该二叉树的深度为:%d \n ",sd );
printf("\n");
break;
case 5:yz=Leaf(bt);
printf( "该二叉树的叶子节点数为:\n%d \n",yz );
printf( "\n" );
break;
case 6: bt=huhuan(bt);
printf( "该二叉树的左右结点已交换成功,其中序遍历序列是:\n" );
Inorder(bt);
printf( "\n" );
break;
}
}
}