结点有左右孩子，count++；
一个是递归算法，没咋明白，书上的，三行代码。
一个是利用层次遍历，出队元素有左右孩子时count++。感觉层次遍历可以解决好多问题
#include <stdio.h> #include <stdlib.h> #define MaxSize 100 typedef struct Node{ int data; struct Node *lchild,*rchild; }TreeNode,*Tree; typedef struct{ TreeNode* data[MaxSize]; int front,rear; }Queue; void InitQueue(Queue &Q) { Q.front=Q.rear=0; } bool isEmpty(Queue Q) { if(Q.front==Q.rear) return true; return false; } bool isFull(Queue Q) { if((Q.rear+1)%MaxSize==Q.front) return true; return false; } bool EnQueue(Queue &Q,TreeNode* p) { if(isFull(Q)) return false; Q.data[Q.rear]=p; Q.rear=(Q.rear+1)%MaxSize; return true; } bool DeQueue(Queue &Q,TreeNode* &p) { if(isEmpty(Q)) return false; p=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; } void CreateTree(Tree &T) { int x; scanf("%d",&x); if(x==-1) { T=NULL; return; } else { T=(Tree)malloc(sizeof(TreeNode)); T->data=x; printf("输入%d的左结点：",x); CreateTree(T->lchild); printf("输入%d的右结点：",x); CreateTree(T->rchild); } } //递归算法 int DsonNode(Tree T) { if(T==NULL) return 0; else if(T->lchild&&T->rchild) return DsonNode(T->lchild)+DsonNode(T->rchild)+1; else return DsonNode(T->lchild)+DsonNode(T->rchild); } //非递归算法 int countNode(Tree T) { if(T==NULL) return 0; Queue Q; InitQueue(Q); int count=0; TreeNode* p=T; EnQueue(Q,p); while(!isEmpty(Q)) { DeQueue(Q,p); if(p->lchild&&p->rchild) count++; if(p->lchild!=NULL) EnQueue(Q,p->lchild); if(p->rchild!=NULL) EnQueue(Q,p->rchild); } return count; } void LevelOrder(Tree T) { if(T==NULL) return; Queue Q; InitQueue(Q); TreeNode *p=T; EnQueue(Q,p); while(!isEmpty(Q)) { DeQueue(Q,p); printf("%d ",p->data); if(p->lchild!=NULL) EnQueue(Q,p->lchild); if(p->rchild!=NULL) EnQueue(Q,p->rchild); } } int main() { Tree T; CreateTree(T); LevelOrder(T); printf("\n"); printf("%d",DsonNode(T)); printf("\n"); printf("%d",countNode(T)); return 0; }