以二叉链表作存储结构,建立一棵二叉树。 输出该二叉树的先序、中序、后序遍历序列,求出该二叉树的深度,并统计其叶子结点数。
二叉链表的类型描述:
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;
}
标签:lchild,遍历,BiTree,NULL,二叉树,printf,rchild,数据结构,root
From: https://blog.csdn.net/2401_85947543/article/details/143615554