tree1_n0.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include "Tree1.h"                               //二叉树类
void property3(TreeNode1 *p,int &n0,int &n2)     //验证二叉树的性质3，n0=n2+1
{                                                //先序遍历以p为根的子树
    if(p!=NULL)
    {
        if(p->left==NULL  && p->right==NULL)     //叶子结点
            n0++;
        if(p->left!=NULL  && p->right!=NULL)     //2度结点
            n2++;
        property3(p->left,n0,n2);
        property3(p->right,n0,n2);
    }
}
void main()
{
    char *str="ABD.G...CE..FH...";               //标明空子树的先根次序
    cout<<"The Tree: "<<str<<"\n";
    Tree1 t1(str);
    t1.preorder();
    t1.inorder();
    t1.postorder();
    int n0=0,n2=0;
    property3(t1.root,n0,n2);
    cout<<"验证二叉树的性质3,  ";
    cout<<"n0="<<n0<<", n2="<<n2<<",  n0==n2+1 ? ";
    if(n0==n2+1)
       cout<<"正确!"<<endl;
    else
       cout<<"不正确?"<<endl;
}
/*
程序运行结果如下：
The Tree: ABD.G...CE..FH...
 PreOrder :  A B D G C E F H 
  InOrder :  D G B A E C H F 
PostOrder :  G D B E H F C A 
验证二叉树的性质3,  n0=3, n2=2, n0==n2+1 ? 正确!
*/