7-7 先序序列创建二叉树，输出先序序列、中序序列、后序序列并输出叶子结点数

对于给定的二叉树，输出其先序序列、中序序列、后序序列并输出叶子结点数。

输入格式:

二叉树的先序遍历序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:

若是非空二叉树，则输出四行内容 第一行是二叉树的先序遍历序列； 第二行是二叉树的中序遍历序列； 第三行是二叉树的后序遍历序列； 第四行是叶子结点数；

若是空二叉树 只需输出叶子数0

输入样例1:

FCA##DB###EHM###G##

输出样例1:

FCADBEHMG
ACBDFMHEG
ABDCMHGEF
4

输入样例2:

#

输出样例2:

0

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000

typedef struct Tree
{
   char data;
   struct Tree *lchild;
   struct Tree *rchild;
} DouTree, *Treelink;

Treelink createTree(char *preorder)
{
   static int index = 0;
   if (preorder[index] == '#' || preorder[index] == '\0')
   {
      index++;
      return NULL;
   }

   Treelink root = (Treelink)malloc(sizeof(DouTree));
   root->data = preorder[index++];
   root->lchild = createTree(preorder);
   root->rchild = createTree(preorder);

   return root;
}

void Preorder(Treelink root)
{
   if (root != NULL)
   {
      printf("%c", root->data);
      Preorder(root->lchild);
      Preorder(root->rchild);
   }
}

void Inorder(Treelink root)
{
   if (root != NULL)
   {
      Inorder(root->lchild);
      printf("%c", root->data);
      Inorder(root->rchild);
   }
}

void Postorder(Treelink root)
{
   if (root != NULL)
   {
      Postorder(root->lchild);
      Postorder(root->rchild);
      printf("%c", root->data);
   }
}

int countTreeleft(Treelink root)
{
   if (root == NULL)
      return 0;
   else if (root->lchild == NULL && root->rchild == NULL)
      return 1;
   else
      return countTreeleft(root->lchild) + countTreeleft(root->rchild);
}

int main()
{
   char preorder[MAXSIZE];
   scanf("%s", preorder);
   Treelink root = createTree(preorder);

   if (countTreeleft(root) != 0)
   {
      Preorder(root);
      printf("\n");

      Inorder(root);
      printf("\n");

      Postorder(root);
      printf("\n");
   }

   printf("%d", countTreeleft(root));
   free(root);

   return 0;
}