7-8 数据结构实验二 二叉树的遍历

以二叉链表作存储结构，建立一棵二叉树。 输出该二叉树的先序、中序、后序遍历序列，求出该二叉树的深度，并统计其叶子结点数。

二叉链表的类型描述：

typedef char ElemType;
typedef  struct  BiNode
{  ElemType  data;
    struct  BiNode   *lchild,*rchild;
}BiNode,*BiTree;  

输入格式:

输入一个二叉树的先序序列，孩子为空的位置以#替代。

输出格式:

输出分五行

• 第一行 先序遍历序列
• 第二行 中序遍历序列
• 第三行 后序遍历序列
• 第四行 二叉树深度
• 第五行 叶子结点数

其中遍历过程中按访问顺序打印出结点的内容时，字符间均无间隔。
具体格式参看输出样例。

对于下图中给出的二叉树：

输入样例:

ABD##FE###CG#H##I##

输出样例:

PreOrder:ABDFECGHI
InOrder:DBEFAGHCI
PostOrder:DEFBHGICA
Depth:4
Leaf:4

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiNode
{
   ElemType data;
   struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

BiTree createNode(ElemType data)
{
   BiTree node = (BiTree)malloc(sizeof(BiNode));
   node->data = data;
   node->lchild = NULL;
   node->rchild = NULL;
   return node;
}

BiTree buildTree(char **str)
{
   if (**str == '#')
   {
      (*str)++;
      return NULL;
   }
   BiTree root = createNode(**str);
   (*str)++;
   root->lchild = buildTree(str);
   root->rchild = buildTree(str);
   return root;
}

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

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

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

int depth(BiTree root)
{
   if (root == NULL)
      return 0;
   int leftDepth = depth(root->lchild);
   int rightDepth = depth(root->rchild);
   return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

int countLeafNodes(BiTree root)
{
   if (root == NULL)
      return 0;
   if (root->lchild == NULL && root->rchild == NULL)
      return 1;
   return countLeafNodes(root->lchild) + countLeafNodes(root->rchild);
}

int main()
{
   char input[100];
   scanf("%s", input);
   char *p = input;
   BiTree root = buildTree(&p);

   printf("PreOrder:");
   preOrder(root);
   printf("\n");

   printf("InOrder:");
   inOrder(root);
   printf("\n");

   printf("PostOrder:");
   postOrder(root);
   printf("\n");

   printf("Depth:%d\n", depth(root));
   printf("Leaf:%d\n", countLeafNodes(root));

   return 0;
}