计算一棵二叉树单分支结点个数的完整程序

#include <stdio.h>

typedef struct BTNode
{
    char data;
    struct BTNode * lchild; //p是指针L是左,child是孩子
    struct BTNode * rchild;
}BTNode,*BiTree;

struct BTNode * CreateBTree();
void PreTraverseBTree(struct BTNode *);
int DsonNodes(struct BTNode *);

int main()
{
    int t;
    struct BTNode * T = CreateBTree();
    PreTraverseBTree(T);
    printf("\n");
    t = DsonNodes(T);
    printf("%d",t);


    return 0;
}
void PreTraverseBTree(BiTree T)
{
    if(T!=NULL)  //if必须要有,虽然pT存在,但当pT->pLchild 或 pT->pRchild为空时没有,空没有指向的data域
    {
        printf("%c\n", T->data);
        if(T->lchild!=NULL)
            PreTraverseBTree(T->lchild);
        if(T->rchild)
            PreTraverseBTree(T->rchild);
    }
}
int DsonNodes(BiTree T)
{
    if(T!=NULL)
    {
        if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL))
            return DsonNodes(T->lchild)+DsonNodes(T->rchild)+1;
        else
            return DsonNodes(T->lchild)+DsonNodes(T->rchild);
    }
}


struct BTNode * CreateBTree()
{
     struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
     struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
     struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
     struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
     struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));

     pA->data = 'A';
     pB->data = 'B';
     pC->data = 'C';
     pD->data = 'D';
     pE->data = 'E';

     pA->lchild = pB;
     pA->rchild = pC;
     pB->lchild = pB->rchild =NULL;
     pC->lchild = pD;
     pC->rchild = NULL;
     pD->rchild = pE;
     pD->lchild = NULL;
     pE->lchild = pE->rchild = NULL;

     return pA;
}

 

上一篇:清华数据结构PA5——真二叉树重构(Proper Rebuild)


下一篇:数据结构-平衡二叉树(AVL树)