erchashu
#include
#define OK 1
#define ERROR 0
#define num 100
int found;
typedef char Telemtype;
typedef int status;
typedef struct BiTNode{
Telemtype data;
BiTNode *lchild,*rchild;
}BiTNode,*Bitree;
status CreateBitree(Bitree &T){
Telemtype m;
scanf("%c",&m);
if(m=='@') T=NULL;
else {
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data=m;
CreateBitree(T->lchild);
CreateBitree(T->rchild);
}
return OK;
}
status visit(Telemtype e){printf("%c",e);return OK;}
status Pretraverse(Bitree T){
if(T) {
if(visit(T->data))
if(Pretraverse(T->lchild))
if(Pretraverse(T->rchild)) return OK;
return ERROR;
}
else return OK;
}
status Intraverse(Bitree T){
if(T) {
if(Intraverse(T->lchild))
if(visit(T->data))
if(Intraverse(T->rchild)) return OK;
return ERROR;
}
else return OK;
}
status Posttraverse(Bitree T){
if(T) {
if(Posttraverse(T->lchild))
if(Posttraverse(T->rchild))
if(visit(T->data)) return OK;
return ERROR;
}
else return OK;
}
int Get_Depth(Bitree T)//求子树深度的递归算法
{int m,n;
if(!T) return 0;
else
{
m=Get_Depth(T->lchild);//先求左孩子的深度；
n=Get_Depth(T->rchild);//再求又孩子的深度；
return (m>n?m:n)+1;//比较两个深度的大小，返回较大的一个并加一；
}
}//Get_Depth
Bitree Get_Sub_Depth(Bitree T,Telemtype x,int &k)//求二叉树中以值为x的结点为根的子树深度
{
if(T->data==x)//条件：满足，则执行下面语句；求其深度，并输出来；
{
k=Get_Depth(T); //找到了值为x的结点,求其深度
return T;
//exit(1);
}
else
{
if(T->lchild) Get_Sub_Depth(T->lchild,x,k);//递归算法寻找数据源数为x的结点；
if(T->rchild) Get_Sub_Depth(T->rchild,x,k); //在左右子树中继续寻找；
}
}//Get_Sub_Depth
void Del_Sub(Bitree T)//删除子树T；递归算法思想为：先删除左右孩子后删除T
{
if(T->lchild) Del_Sub(T->lchild); //先删除左右孩子
if(T->rchild) Del_Sub(T->rchild);
free(T);//后删除T
}//Del_Sub
void Del_Sub_x(Bitree T,int x)//删除所有以元素x为根的子树
{
if(T->data==x) {Del_Sub(T);} //删除该子树，这里直接调用Del_Sub(T)函数；
else
{
if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找}//else
}//Del_Sub_x
void NodePath(Bitree T,BiTNode *ch){
typedef enum {FLASE,TRUE}boolean;
BiTNode *stack[num];
int tag[num];
int top,i;
boolean find;
BiTNode *s;
find=FLASE;
top=0;
s=T;
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){
printf("%c",stack[1]->data);
for(i=2;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);
}
using namespace std;
void main(){
Bitree T,p;Telemtype x;int xz=1,k=0;char ch1;
while(xz){
printf(" 二叉树的遍历及求节点路径\n");
printf(" 1.建立二叉树存储结构\n");
printf(" 2.求二叉树的前序遍历\n");
printf(" 3.求二叉树的中序遍历\n");
printf(" 4.求二叉树的后序遍历\n");
printf(" 5.求指定结点的路径\n");
printf(" 0.退出系统\n");
printf("========================\n");
printf(" 请选择：0—5");
scanf("%d",&xz);
switch(xz){
case 1:
printf("输入二叉树的按层结点值（按完全二叉树）：\n");
getchar();
CreateBitree(T);
printf("二叉树的链式存储结构建立完成！\n");
break;
case 2:
printf("该二叉式的前序遍历是：\n");
Pretraverse(T);
printf("\n");
break;
case 3:
printf("该二叉式的中序遍历是：\n");
Intraverse(T);
printf("\n");
break;
case 4:
printf("该二叉式的后序遍历是：\n");
Posttraverse(T);
printf("\n");
break;
case 5:
printf("输入要求路径的结点值：");
getchar();
ch1=getchar();
p=Get_Sub_Depth(T,ch1,k);
if(p!=NULL){
NodePath(T,p);
printf("\n");
printf("以%c为根结点的子树深度为：%d\n",ch1,k);
}
else
printf("没有要求的结点\n");
break;
}
}
}