2024年4月4日发(作者：)

树与二叉树算法汇总

1．以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树和右子

树表示的子表达式的值，最后就可以根据

根结点的运算符的要求，计算出表达式的最后结果。

typedef struct node

{ElemType data; float val;

char optr; //只取‘+’， ‘-’， ‘*’，‘/’

struct node *lchild，*rchild }BiNode,*BiTree;

float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值

{float lv,rv;

if(bt!=null)

{lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值

rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值

switch(bt->optr)

{ case ‘+’: value=lv+rv; break;

case ‘-’: value=lv-rv;break;

case ‘*’: value=lv*rv;break;

case ‘/’: value=lv/rv;

} } return(value);

}

32.二叉树采取顺序结构存储，是按完全二叉树格式存储的。对非完全二叉树要补上“虚

结点”。由于不是完全二叉树，在顺序结

构存储中对叶子结点的判定是根据其左右子女为0。叶子和双亲结点下标间的关系满足

完全二叉树的性质。

int Leaves(int h) //求深度为h 以顺序结构存储的二叉树的叶子结点数

{ int BT[]; int len=2h-1, count=0; //BT 是二叉树结点值一维数组，容量为2h

for (i=1;i<=len;i++) //数组元素从下标1 开始存放

if (BT[i]!=0) //假定二叉树结点值是整数，“虚结点”用0 填充