XDOJ-270 統計二叉樹中的葉子結點數

由于二又樹的周遊算法是許多二叉樹運算的算法設計的基礎，是以周遊算法的應用很廣泛。下面将以周遊算法求二叉樹的葉子數為例，來加深對二叉樹周遊算法的了解。

因為葉子結點是二叉樹中那些左孩子和右孩子均不存在的結點，是以可在二叉樹的周遊過程中，對這種特殊結點進行計數，來完成葉子結點數的統計。

一棵樹的葉子數目等于它的左子樹葉子數加上右子樹葉子數的總和。而當一個結點沒有左子樹也沒有右子樹的時候，即為葉子結點。隻要周遊整個樹将符合條件的記錄就可以得出葉子結點數。

要求：

建立二叉連結清單，統計二叉樹中的葉子結點數并輸出。按照完全二叉樹的形式輸入二叉樹的各結點資料(字元)，其中虛結點用'@'表示。輸入以'#'結束。輸出葉子結點的個數及具體值。第一行為為葉子結點的資料值，各資料用空格分隔，第二行為葉子結點的個數。

輸入示例：

abc@@de#

輸出：

b d e

3

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 1024

typedef struct node {
	char data;		//字元項
	struct node* lchild, * rchild;	//左右子樹
}Bitree;
Bitree root;

Bitree* CreateTree();
int CountLeaf(Bitree* p);

int main() {
	Bitree *tree = CreateTree();
	int sum = CountLeaf(tree);
	printf("\n");
	printf("%d", sum);
	return 0;
}
int CountLeaf(Bitree *p){
	if(!p)
		return 0;
	else if(p->lchild==NULL&&p->rchild==NULL){
		printf("%c ", p->data); 
		return 1;
	}
	else
		return CountLeaf(p->lchild)+CountLeaf(p->rchild);
}

Bitree* CreateTree() {
	char ch;
	Bitree* Q[MAXSIZE];
	int front = 1, rear = 0;
	Bitree* root, * s;
	root = NULL;
	while ((ch = getchar()) != '#') {
		s = NULL;
		if (ch != '@') {
			s = (Bitree*)malloc(sizeof(Bitree));
			s->data = ch;
			s->lchild = NULL;
			s->rchild = NULL;
		}
		rear++;
		Q[rear] = s;
		if (rear == 1)
			root = s;
		else {
			if (s && Q[front]) {
				if (rear % 2 == 0) {
					Q[front]->lchild = s;
				}
				else
					Q[front]->rchild = s;
			}
			if (rear % 2 == 1)
				front++;
		}
	}
	return root;
}
           

歡迎大家關注：https://github.com/XDUgaile

寫完的一些東西會不定時丢上去。