实验 4 二叉树的相关运算
一、实验目的
1.理解二叉树的概念;
2.理解二叉树先序、中序、后序遍历的策略;
3.掌握二叉树的建立、二叉树的遍历等算法。
二、实验原理
1.二叉树的遍历
先序遍历二叉树:先访问根结点,再先序遍历其左子树,然后先序遍历其右子树;
中序遍历二叉树:先中序遍历左子树,再访问根结点,然后中序遍历右子树;
后序遍历二叉树:先后序遍历左子树,再后序遍历右子树,然后访问根结点。
2.二叉树的二叉链表存储表示
typedef char DataType;
typedef struct Node
{
DataType data;
struct Node * LChild;
struct Node * RChild;
}BiTNode, *BiTree;
三、实验内容
请按先序序列建立二叉树的二叉链表,然后分别先序遍历、中序遍历以及后序遍历该
二叉树。
运行调试,输入数据,并根据结果进行分析。
部分示例代码及程序运行参考界面如下所示,请完善程序,并撰写实验报告。
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
typedef struct Node
{
DataType data;
struct Node * LChild;
struct Node * RChild;
}BiTNode, *BiTree;
int count=0;
void CreateBiTree(BiTree *bt); /* 按先序序列建立二叉树 */
void PreOrder(BiTree root); /* 先序遍历:根左右 */
void InOrder(BiTree root); /* 中序遍历:左根右 */
void PostOrder(BiTree root) ; /* 后序遍历:左右根 */
void Visit(DataType e); /* 最简单的 Visit 函数,输出元素 e */
void leaf(BiTree root);//统计叶子节点个数