#include <iostream> |
using namespace std; |
typedef char TElemType; |
typedef struct BiTNode |
{ |
TElemType data; |
BiTNode *lc,*rc; |
}*BiTree; |
void CreateBiTree(BiTree &T, char s[]); //带有空子树信息的先序建立二叉树 |
void CreateBiTree(BiTree &T, char s[], int &i); |
void BiTreeLists(BiTree &T); //广义表形式 |
bool YangeBiTree(BiTree &T); |
int main() |
{ |
BiTree T1,T2; char s1[]= "ABC##G##DEH##I##F##" ; char s2[]= "ABC###DE##F##" ; |
CreateBiTree(T1,s1);CreateBiTree(T2,s2); |
cout<< "二叉树(广义表形式)为:" ; |
BiTreeLists(T1); |
cout<<endl; |
if (YangeBiTree(T1)) |
cout<< "该二叉树是严格二叉树!" <<endl; |
else cout<< "该二叉树不是严格二叉树!" <<endl; |
cout<< "二叉树(广义表形式)为:" ; |
BiTreeLists(T2); |
cout<<endl; |
if (YangeBiTree(T2)) |
cout<< "该二叉树是严格二叉树!" <<endl; |
else cout<< "该二叉树不是严格二叉树!" <<endl; |
|
return 0; |
} |
void CreateBiTree(BiTree &T, char s[], int &i) |
{ |
i++; |
if (s[i]== '#' ){T=NULL; return ;} |
T= new BiTNode; T->data=s[i]; |
CreateBiTree(T->lc,s,i); |
CreateBiTree(T->rc,s,i); |
} |
void CreateBiTree(BiTree &T, char s[]) |
{ |
int i=-1; |
CreateBiTree(T,s,i); |
} |
void BiTreeLists(BiTree &T) |
{ |
if (!T) {cout<< '#' ; return ;} |
cout<<T->data; |
if (T->lc ||T->rc) |
{ |
cout<< '(' ; |
BiTreeLists(T->lc); |
cout<< ',' ; |
BiTreeLists(T->rc); |
cout<< ')' ; |
} |
} |
bool YangeBiTree(BiTree &T) |
{ |
if (!T || !T->lc && !T->rc){ return true ;} |
if (T->lc && T->rc ) |
{ |
return YangeBiTree(T->rc) && YangeBiTree(T->lc); |
} |
else |
return false ; |
} |