//创建二叉树，先序遍历，结点个数，叶子结点个数，叶子结点用rchild指针串连成单链表

include <stdio.h>

include <stdlib.h>

define maxsize 10

typedef struct BTNode
{
char data;
struct BTNode *lchild, rchild;
} BTNode, BTree;
void CreateBTNode(BTree T)
{
char ch;
scanf("%c", &ch);
if (ch == '#')
{
T = NULL;
}
else
{
T = (BTNode )malloc(sizeof(BTNode));
(T)->data = ch;
(T)->lchild = NULL;
(T)->rchild = NULL;
printf("\n建立左子树\n");
CreateBTNode(&(T)->lchild);
printf("\n建立右子树\n");
CreateBTNode(&(T)->rchild);
}
}
void PreOrder_Traverase(BTree T) //先序遍历
{
if (T == NULL)
{
return;
}
else
{
printf(" %c ", T->data);
PreOrder_Traverase(T->lchild);
PreOrder_Traverase(T->rchild);
}
}
int n = 0;
int count(BTNode *T)
{
if (T != NULL)
{
n++;
count(T->lchild);
count(T->rchild);
}
return n;
}
int countLeaf(BTNode *T)
{
static int leaf = 0;
if (T != NULL)
{
if ((T->lchild == NULL) && (T->rchild == NULL))
{
leaf++;
}
else
{
countLeaf(T->lchild);
countLeaf(T->rchild);
}
}
return leaf;
}
void link(BTNode *T, BTNode *head, BTNode *tail)
{
if (T != NULL)
{
if (T->lchild == NULL && T->rchild == NULL) //判断是否叶子结点
{
if (head == NULL)
{
head = T;
tail = T;
}
else
{
tail->rchild = T;
tail = T;
}
}
link(T->lchild, head, tail);
link(T->rchild, head, tail);
while (head != NULL)
{
printf(" %c", head->data);
head = head->rchild;
}
}
}
int main()
{
BTree T;
BTNode *p, *head, *tail;
head = NULL;
int leaf;
printf("创建二叉树："); //输入ABC##DE#G##F###
CreateBTNode(&T);
printf("\n先序遍历\n");
PreOrder_Traverase(T);
count(T);
printf("\n共%d个结点。\n", n);
leaf = countLeaf(T);
printf("\n叶子结点个数为：%d\n", leaf);
printf("叶子结点串联:");
link(T, head, tail);
printf("\n");
return 0;
}