加文

在这个世界上取得成就的人，都努力去寻找他们想要的机会，如果找不到机会，他们便自己创造机会。 -- 萧伯纳
随笔 - 14, 文章 - 56, 评论 - 1, 引用 - 0
数据加载中……

统计二叉树叶子结点数目

#include <iostream>
using namespace std;
#define STACK_MAX_SIZE 50
typedef struct node
{
    char data;
    node * lchild;
    node * rchild;
}* BTreeNode;

void CreateBTree(BTreeNode &root,char * a)
{
    BTreeNode temp;
    BTreeNode Stack[STACK_MAX_SIZE];
    int top =-1;
    int k;
    int i=0;
    root = NULL;
    while(a[i]!='\0')
    {
        switch(a[i])
        {
        case '#':
            break;
        case '(':
            if(top == STACK_MAX_SIZE-1)
            {
                cout<<"栈溢出！程序自动退出！！"<<endl;
                exit(1);
            }
            else
            {
                top ++;
                Stack[top] = temp;
                k=1;
                break;
            }
        case ')':
            if(top ==-1)
            {
                exit(1);
            } else
            {
                top--;
                break;
            }
        case ',':
            k = 2;
            break;
        default:
            temp = new node();
            temp->data = a[i];
            temp->lchild = NULL;
            temp->rchild = NULL;
            if(root == NULL)
            {
                root = temp;
            }
            else
            {
                if(k==1)
                    Stack[top]->lchild = temp;
                else
                {
                    Stack[top]->rchild = temp;
                }
            }
        }
        i++;
    }
}
// 统计二叉树的叶子节点数目
int CounterLeaf(BTreeNode root)
{
    if(root == NULL)
        return 0;
    else
    {
        if(root->lchild == NULL && root->rchild == NULL)
            return 1;
        else
            return CounterLeaf(root->lchild) + CounterLeaf(root->rchild);
    }
}
int main()
{
    char * a = "E(B(A,D(C,#)),I(G(F,H),J))";
    BTreeNode root;
    CreateBTree(root,a);
    cout<<"二叉树叶子节点数目为："<<CounterLeaf(root);
    getchar();
    return 0;
}

posted on 2011-12-13 16:15 chxzwj 阅读(834) 评论(0)  编辑 收藏 引用 所属分类: 常用算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理