凡是对二叉树中各结点进行一次处理的问题,都可以用遍历算法来完成。
1.利用遍历算法对二叉树中各类结点计数
设二叉树中出度=0、1、2的结点数分别为n0、 n1 和n2 ,初值均为0。
套用遍历算法(前序、中许、后序均可),扫描到树中某p结点时,若:
if ((p->Lchild==NULL)&&(p->Rchild==NULL))
n0++; //p为叶子//
else if((p->Lchild)&&(p->Rchild))
n2++; //p为出度=2的结点//
else n1++; // p为出度=1的结点//
如:只要把遍历算法在遍历时稍微改变一下。
n0=n1=n2=0;
void preorder( BTptr T) //对当前根结点指针为T的二叉树按前序遍历//
{if (T) { // visit(T); 访问T所指结点 //
if ((T->Lchild==NULL)&&(T->Rchild==NULL))
n0++; //p为叶子//
else if((T->Lchild)&&(T->Rchild))
n2++; //p为出度=2的结点//
else
n1++; // p为出度=1的结点//
preorder(T–>Lchild); //前序遍历T之左子树//