描述
给出一个二叉树的广义表表示方法,请用二叉链表的方式建立一棵二叉树。并输出树中叶子节点的数目。
不考虑空树情况!
#include<iostream> #include<stack> using namespace std; #define MAX(a,b) a>b?a:b; typedef struct Node { char data; Node *left; Node *right; }*pBTNode, BTNode; void CreateBTree(pBTNode &root, char str[]) { pBTNode p=NULL, temp=NULL; stack<pBTNode> st; int i, flag, top=-1; for(i=0; str[i]!='\0'; i++) { switch( str[i] ) { case '(':flag=1;st.push(p);break;//遇到左括号,说明刚刚创建的节点为头结点,入栈;且下一个创建的节点为其左儿子 case ',':flag=2;break;//遇到逗号,说明下一个创建的节点为右儿子 case ')':st.pop();break;//遇到右括号,说明左右儿子已处理完,出栈 default: p=new BTNode; p->data=str[i]; p->left=p->right=NULL; if( root==NULL ) root=p; else { temp=st.top(); switch(flag) { case 1:temp->left=p;break; case 2:temp->right=p; break; } } } } } int Num(pBTNode p) { if( p==NULL ) return 0; if( p->left==NULL && p->right==NULL ) return 1; return Num(p->left)+Num(p->right); } int main() { char str[1000]; BTNode *root=NULL; int t; cin>>t; while( t-- ) { cin>>str; root=NULL; CreateBTree(root, str); cout<<Num(root)<<endl; } }