二叉树-算法与数据结构

#include<stdio.h>  
#include<windows.h>  
#include<malloc.h>  
#define maxsize 20  
typedef int elemtype;  
typedef struct node //定义  
{  
elemtype data;  
struct node *lchild;  
struct node *rchild;  
}btnode;  
void createbtnode(btnode *&b,char *str) //创建二叉树  
{  
btnode *st[maxsize],*p=NULL;  
int top=-1,k,j=0;  
char ch;  
b=NULL;  
ch=str[j];  
while(ch!="")  
{  
switch(ch)  
{  
case "(":top++;st[top]=p;k=1;break;  
case ")":top--;break;  
case ",":k=2;break;  
default:p=(btnode *)malloc(sizeof(btnode));  
p->data=ch;p->lchild=p->rchild=NULL;  
if(b==NULL)  
b=p;  
else  
{  
switch(k)  
{  
case 1:st[top]->lchild=p;break;  
case 2:st[top]->rchild=p;break;  
default:printf("错误!
");  
}  
}  
}  
j++;  
ch=str[j];  
}  
}  
btnode *findnode(btnode *b,elemtype x) //查找节点  
{  
btnode *p;  
if(b==NULL)  
return NULL;  
else if(b->data==x)  
return b;  
else  
{  
p=findnode(b->lchild,x);  
if(p!=NULL)  
return p;  
else   
return findnode(b->rchild,x);  
}  
}  
btnode *lchildnode(btnode *p) //找左孩子  
{  
return p->lchild;  
}  
btnode *rchildnode(btnode *p) //找右孩子  
{  
return p->rchild;  
}  
int btnodeheight(btnode *b) //求高度  
{  
int lchildh,rchildh;  
if(b==NULL)  
return 0;  
else  
{  
lchildh=btnodeheight(b->lchild);  
rchildh=btnodeheight(b->rchild);  
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);  
}  
}  
void dispbtnode(btnode *b) //输出二叉树  
{  
if(b!=NULL)  
{  
printf("%c",b->data);  
if(b->lchild!=NULL||b->rchild!=NULL)  
{  
printf("(");  
dispbtnode(b->lchild);  
if(b->rchild!=NULL)  
printf(",");  
dispbtnode(b->rchild);  
printf(")");  
}  
}  
}  
  
  
int Nodes(btnode *b)//求二叉树b的节点个数  
{  
int num1,num2;  
if (b==NULL)   
return 0;  
else if (b->lchild==NULL && b->rchild==NULL)   
return 1;  
else  
{  
num1=Nodes(b->lchild);  
num2=Nodes(b->rchild);  
return (num1+num2+1);  
}  
}  
int LeafNodes(btnode *b)//求二叉树b的叶子节点个数  
{  
int num1,num2;  
if (b==NULL)   
return 0;  
else if (b->lchild==NULL && b->rchild==NULL)   
return 1;  
else  
{  
num1=LeafNodes(b->lchild);  
num2=LeafNodes(b->rchild);  
return (num1+num2);  
}  
}  
void TravLevel(btnode *b) //层次遍历  
{  
btnode *Qu[maxsize];//定义循环队列  
int front,rear;//定义队首和队尾指针  
front=rear=0;//置队列为空队列  
if (b!=NULL)   
printf("%c ",b->data);  
rear++;//节点指针进入队列  
Qu[rear]=b;  
while (rear!=front)//队列不为空  
{  
front=(front+1)%maxsize;  
b=Qu[front];//队头出队列  
if (b->lchild!=NULL)//输出左孩子,并入队列  
{  
printf("%c ",b->lchild->data);  
rear=(rear+1)%maxsize;  
Qu[rear]=b->lchild;  
}  
if (b->rchild!=NULL)//输出右孩子,并入队列  
{  
printf("%c ",b->rchild->data);  
rear=(rear+1)%maxsize;  
Qu[rear]=b->rchild;  
}  
}   
printf("
");  
}  
void PreOrder(btnode *b) //先序遍历的递归算法  
{  
if (b!=NULL)   
{  
printf("%c ",b->data);//访问根节点  
PreOrder(b->lchild);//递归访问左子树  
PreOrder(b->rchild);//递归访问右子树  
}  
}  
void PreOrder1(btnode *b) //先序遍历的非递归算法  
{  
btnode *St[maxsize],*p;  
int top=-1;  
if (b!=NULL)   
{  
top++;//根节点入栈  
St[top]=b;  
while (top>-1)//栈不为空时循环  
{  
p=St[top];//退栈并访问该节点  
top--;  
printf("%c ",p->data);  
if (p->rchild!=NULL)//右孩子入栈  
{  
top++;  
St[top]=p->rchild;  
}  
if (p->lchild!=NULL)//左孩子入栈  
{  
top++;  
St[top]=p->lchild;  
}  
}  
printf("
");  
}  
}  
void InOrder(btnode *b) //中序遍历的递归算法  
{  
if (b!=NULL)   
{  
InOrder(b->lchild);//递归访问左子树  
printf("%c ",b->data);//访问根节点  
InOrder(b->rchild);//递归访问右子树  
}  
}  
void InOrder1(btnode *b) //中序遍历的非递归算法  
{  
btnode *St[maxsize],*p;  
int top=-1;  
if (b!=NULL)  
{  
p=b;  
while (top>-1 || p!=NULL)  
{  
while (p!=NULL)  
{  
top++;  
St[top]=p;  
p=p->lchild;  
}  
if (top>-1)  
{  
p=St[top];  
top--;  
printf("%c ",p->data);  
p=p->rchild;  
}  
}  
printf("
");  
}  
}  
void PostOrder(btnode *b) //后序遍历的递归算法  
{  
if (b!=NULL)   
{  
PostOrder(b->lchild);//递归访问左子树  
PostOrder(b->rchild);//递归访问右子树  
printf("%c ",b->data);//访问根节点  
}  
}  
void PostOrder1(btnode *b) //后续遍历的非递归算法  
{  
btnode *St[maxsize];  
btnode *p;  
int flag,top=-1;//栈指针置初值  
if (b!=NULL)  
{  
do  
{  
while (b!=NULL)//将t的所有左节点入栈  
{  
top++;  
St[top]=b;  
b=b->lchild;  
}  
p=NULL;//p指向当前节点的前一个已访问的节点  
flag=1;  
while (top!=-1 && flag)  
{  
b=St[top];//取出当前的栈顶元素  
if (b->rchild==p)//右子树不存在或已被访问,访问之  
{  
printf("%c ",b->data);//访问*b节点  
top--;  
p=b;//p指向则被访问的节点  

}

  

else  
{  
b=b->rchild;//t指向右子树  
flag=0;  
}  
}  
} while (top!=-1);  
printf("
");  
}   
}  
void DestroyBTNode(btnode *&b) //销毁二叉树  
{  
if (b!=NULL)  
{  
DestroyBTNode(b->lchild);  
DestroyBTNode(b->rchild);  
free(b);  
}  

}

  

void main()  
{  
int hight,n;  
char ch,str[100];  
btnode *b,*p,*p1,*p2;  
printf(" *****************欢迎使用二叉树基本运算系统*******************
");  
printf("请输入一个广义表
(例如:A(B(D(,I),E(J,K(H))),C(F)))
");  
gets(str);  
createbtnode(b,str);  
while(1)  
{  
printf("请选择:
");  
printf(" 1 求树的高度
");  
printf(" 2 求节点的孩子
");  
printf(" 3 输出二叉树
");  
printf(" 4 求二叉树的节点数
");  
printf(" 5 求二叉树的叶子节点数
");  
printf(" 6 层次遍历序列
");  
printf(" 7 先序遍历序列
");  
printf(" 8 中序遍历序列
");  
printf(" 9 后续遍历序列
");  
printf(" 10 释放二叉树并退出
");  
printf(" 11 退出
");  
scanf("%d",&n);  
switch(n)  
{  
case 1:printf("树的高度为:%d
",btnodeheight(b));break;  
case 2:getchar();printf("请输入需查找的节点:");  
scanf("%c",&ch);  
p=findnode(b,ch);  
p1=lchildnode(p);  
p2=rchildnode(p);  
if(p1!=NULL)  
printf("左孩子为:%c
",p1->data);  
else  
printf("没有左孩子
");  
if(p2!=NULL)  
printf("右孩子为:%c
",p2->data);  
else  
printf("没有右孩子
");  
break;  
case 3:dispbtnode(b);  
printf("
");  
break;  
case 4:printf("二叉树的节点个数为:%d个
",Nodes(b));break;  
case 5:printf("二叉树的叶子节点数为%d个
",LeafNodes(b));break;  
case 6:printf("层次遍历序列:");TravLevel(b);break;  
case 7:printf("先序遍历序列:
");  
printf(" 递归算法:");PreOrder(b);printf("
");  
printf(" 非递归算法:");PreOrder1(b);break;  
case 8:printf("中序遍历序列:
");  
printf(" 递归算法:");InOrder(b);printf("
");  
printf(" 非递归算法:");InOrder1(b);break;  
case 9:printf("后序遍历序列:
");  
printf(" 递归算法:");PostOrder(b);printf("
");  
printf(" 非递归算法:");PostOrder1(b);break;  
case 10:DestroyBTNode(b);printf("二叉树已销毁!
");exit(0);break;  
case 11:exit(0);  
default:printf("输入错误
");  
}  
}  
}