6.4.2 二叉树基本运算实现算法.pptx

6.4.2二叉树基本运算实现算法;采用括号表示法表示的二叉树字符串str，且每个结点的值是单个字符。用ch扫描str，其中只有4类字符，各类字符的处理方式：;对应的算法如下：;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)

{

case1:St[top]-lchild=p;break;

case2:St[top]-rchild=p;break;

}

}

}

j++;ch=str[j];

}

};（2）销毁二叉树bt的运算算法

销毁二叉树bt的递归模型f(bt)如下：;（3）求二叉树高度运算算法

求二叉树bt的高度的递归模型f(bt)如下：;（4）求二叉树结点个数运算算法

求二叉树bt中结点个数的递归模型f(bt)如下：;（5）求二叉树叶子结点个数运算算法

求二叉树bt中叶子结点个数的递归模型f(bt)如下：;（6）以括号表示法输出二叉树运算算法;voidDispBTree(BTNode*bt)

{if(bt!=NULL)

{printf(%c,bt-data);

if(bt-lchild!=NULL||bt-rchild!=NULL)

{printf((); //有子树时输出(

DispBTree(bt-lchild); //递归处理左子树

if(bt-rchild!=NULL) //有右子树时输出,

printf(,);

DispBTree(bt-rchild); //递归处理右子树

printf()); //输出一个)

}

}

}