一般地，二叉树有如下几个基本运算。
（1）CreateBTree(bt,str)：根据二叉树的括号表示法str建立二叉链bt。
（2）BTHeight(bt)：求一棵二叉树bt的高度。
（3）NodeCount(bt)：求一棵二叉树bt的节点个数。
（4）LeafCount(bt)：求一棵二叉树bt的叶子节点个数。
（5）DispBTree(bt)：以括号表示法输出一棵二叉树bt。
（6）DispBTree1(bt)：以凹入表示法输出一棵二叉树bt。
假设二叉树采用二叉链存储结构，实现以上基本运算的算法如下。
用ch扫描采用括号表示法表示二叉树的字符串str。分以下几种情况。
（1）若ch='('，则将前面刚创建的节点作为双亲节点进栈，并置k=1，表示其后创建的节点将作为这个节点的左孩子节点。
（2）若ch=')'，表示栈中节点的左右孩子节点处理完毕，退栈。
（3）若ch=','，表示其后创建的节点为右孩子节点。
（4）其他情况，表示要创建一个节点，并根据k值建立它与栈中节点之间的联系，当k=1时，表示这个节点作为栈中节点的左孩子节点，当k=2时，表示这个节点作为栈中节点的右孩子节点。如此循环直到str处理完毕。算法中使用一个栈St保存双亲节点，top为其栈指针，k指定其后处理的节点是双亲节点（保存在栈中）的左孩子节点（k=1）还是右孩子节点（k=2）。
对应的算法如下：
void CreateBTree(BTNode * &bt,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
bt=NULL; /*建立的二叉树初始时为空*/
ch=str[j];
while (ch!='\0') /*str未扫描完时循环*/
{
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 (bt==NULL) /*p为二叉树的根节点*/
bt=p;
else /*已建立二叉树根节点*/
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
求二叉树高度的递归模型f(b)如下：
f(b)=
0 若b=NULL
Max{f(b->lchild),f(b->rchild)}+1 其他情况
对应的算法如下：
int BTHeight(BTNode *bt)
{
int lchilddep,rchilddep;
if (bt==NULL) return(0); /*空树的高度为0*/
else
{
lchilddep=BTHeight(bt->lchild); /*求左子树的高度为lchilddep*/
rchilddep=BTHeight(bt->rchild); /*求右子树的高度为rchilddep*/
return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
}
}
对应的递归模型如下：
f(bt)=
0 当bt=NULL
f(bt->lchild)+f(bt->rchild)+1 其他情况
相应的递归算法如下：
int NodeCount(BTNode *bt) /*求二叉树bt的节点个数*/
{
int num1,num2;
if(bt==NULL)
return 0;
else
{
num1=NodeCount(bt->lchild);
num2=NodeCount(bt->rchild);
return (num1+num2+1);
}
}
对应的递归模型如下：
0 当bt=NULL
f(bt)= 1 当bt为叶子节点
f(bt->lchild)+f(bt->rchild) 其他情况
相应的递归算法如下：
int LeafCount(BTNode *bt) /*求二叉树bt的叶子节点个数*/
{
int num1,num2;
if(bt==NULL)
return 0;
else if(bt->lchild==NULL && bt->rchild==NULL)
return 1;
else
{
num1=LeafCount(bt->lchild);
num2=LeafCount(bt->rchild);
return(num1+num2);
}
}
其过程是：对于非空二叉树bt，先输出其元素值，当存在左孩子节点或右孩子节点时，输出一个“(”符号，然后递归处理左子树，输出一个“,”符号，递归处理右子树，最后输出一个“)”符号。对应的递归算法如下：
void DispBTree(BTNode *bt)
{
if(bt!=NULL)
{
cout << bt->data;
if(bt->lchild!=NULL || bt->rchild!=NULL)
{
cout<<"(";
DispBTree(bt->lchild); /*递归处理左子树*/
if(bt->rchild!=NULL)
cout << ",";
DispBTree(bt->rchild); /*递归处理右子树*/
cout<<")";
}
}
}
采用先序遍历非递归的方法，用一个栈St保存树中节点指针，用Level数组保存栈中对应节点的输出长宽和该节点的类型（是根节点、双亲节点的左孩子或右孩子）。先将根节点指针进栈，在栈不空时循环：退栈一个节点，以对应的长宽输出，退栈，并将当前节点的右孩子节点（若存在）指针和左孩子节点（若存在）指针进栈。采用凹入表示法输出时，每个节点之前的括号中的标记表示是什么类型的节点，B表示根节点，L表示左节点，R表示右节点。对应的算法如下：
void DispBTree1(BTNode *bt) /*以凹入表示法输出一棵二叉树*/
{
BTNode *St[MaxSize],*p;
int Level[MaxSize][2],top=-1,n,i,width=4;
char type; /*取值L表示为左节点，R表示为右节点，B表示为根节点*/
if(bt!=NULL)
{
top++;
St[top]=bt; /*根节点入栈*/
Level[top][0]=width;
Level[top][1]=2; /*2表示根*/
while (top>-1)
{ p=St[top]; /*退栈并凹入显示该节点值*/
n=Level[top][0];
switch(Level[top][1])
{
case 0:type='L';break; /*左节点之后输出(L)*/
case 1:type='R';break; /*右节点之后输出(R)*/
case 2:type='B';break; /*根节点之后输出(B)*/
}
for (i=1;i<=n;i++) /*其中n为显示长宽，字符以右对齐显示*/
cout<<" ";
cout<<p->data<<"("<<type<<")";
for(i=n+1;i<=MaxWidth;i+=2)
cout<<"—";
cout<<endl;
top--;
if(p->rchild!=NULL)
{ /*将右子树根节点入栈*/
top++;
St[top]=p->rchild;
Level[top][0]=n+width; /*长宽增width，即缩width格后再输出*/
Level[top][1]=1; /*1表示右子树*/
}
if(p->lchild!=NULL)
{ /*将左子树根节点入栈*/
top++;
St[top]=p->lchild;
Level[top][0]=n+width; /*显示长宽增width*/
Level[top][1]=0; /*0表示左子树*/
}
}
}
}