01
1 |
|
03
1 |
|
顺序表
1 |
|
顺序表
1 |
|
04
1 |
|
04
1 |
|
05
1 |
|
06
1 | #include<iostream> |
07
1 |
|
08`
//创建二叉树
#include<btree.h>
void CreatBTNode(BTnode &b,char str)
{
BTNode St[MaxSize],p;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!=’\0’)
{switch(ch)
{
case ‘(‘:top++,St[top]=p;k=1;break;
case ‘)’:top–;break;
case ‘,’:k=z;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case1:St[top]->lchild=p;break;
case2:St[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
}
//查找节点
/递归模型
f(b,x)=NULL
f(b,x)=b
f(b,x)=p
f(b,x)=f(b->rchild,x)
/
//对应的递归算法
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;
}
//求高度
/递归模型
f(b)=0
f(b)=MAX{f(b->lchild),f(b->rchild)}
/
//递归算法
int BTNodeHeight(BTNode *b)
{ int lchild,rchild;
if(b==NULL) return 0;
else
{ lchild= BTNodeHeight(b->lchild);//求左子树的高度
rchild=BTNodeHeight(b->rchild);
return (lchild>rchild?(lchild+1:rchild+1));
}
}
//输出二叉树
void DispBTNode(BTNode *b)
{ if(b!=NULL)
{ printf(“%c”,b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{ printf(“(\n” );
DispBTNode(b->lchild);
if(b->rchild!=NULL) printf(“,\n” );
DispBTNode(b->rchild);
printf(“)\n” );
}
}
}
//二叉树的遍历
//先序遍历
void PreOrder(BTNode b)
{ if(b!=NULL)
{ printf(“%c\n”,b->data );
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
//中根遍历
void InOrder(BTNode b)
{ if(b!=NULL)
{
InOrder(b->lchild);
printf(“%c\n”,b->data );
InOrder(b->rchild);
}
}
//后根遍历
void PostOrder(BTNode b)
{ if(b!=NULL)
{
PostOrder(b->lchild);
PostOrder(b->rchild);
printf(“%c\n”,b->data );
}
}
void main()
{
BTNode b,p,lp,*rp;
CreatBTNode(b,”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”);
printf(“二叉树的基本运算”);
printf(“(1)输出二叉树:”); DispBTNode(b);printf(“\n” );
}
v1.5.2