实验二、二叉树操作实验二、二叉树操作一、 目的掌握二叉树的定义、 性质及存储方式， 各种遍历算法。二、 要求采用二叉树链表作为存储结构， 完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。三、 实验内容1、 分析程序存储结构Typedef struct node{ Char data; Struct node*lchild,*rchild; }BinTNode; //自定义二叉树的结点类型typedef BinTNdoe *BinTree; //自定义二叉树的指针int NodeNum,leaf; // NodeNum 为结点数， leaf 为叶子数主要流程及模块调用进 入 主 函 数 先 进 行 创 建 二 叉 树CreatBinTree 出现主界面调用先序， 中序，后序，层次，以及求所有叶子及结点总数的函数进行遍历。2、 测试内容及结果：设计一棵二叉树，输入完全二叉树的先序序列 ， 用 # 代 表 虚 结 点 （ 空 指 针 ）， 如ABD###CE##F## ，建立二叉树，求出先序、中序和后序以及按层次遍历序列， 求所有叶子及结点总数。3、 改正后的程序：#include #include #include #define Max 20 //结点的最大个数typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型typedef BinTNode *BinTree; //定义二叉树的指针int NodeNum,leaf; //NodeNum 为结点数， leaf 为叶子数 , //Nos]deNum 是全局变量，应用时要初始化//========== 基于先序遍历算法创建二叉树============== //===== 要求输入先序序列， 其中加入虚结点 "#"以示空指针的位置 ========== BinTree CreatBinTree(void) { BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //读入 #，返回空指针else{ T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点if( T != NULL ) { T->data=ch; T->lchild=CreatBinTree(); //构造左子树T->rchild=CreatBinTree(); //构造右子树} return(T); } } //========NLR 先序遍历 ============= void Preorder(BinTree T) { if(T) { printf("%c",T->data); //访问结点Preorder(T->lchild); //先序遍历左子树Preorder(T->rchild); //先序遍历右子树} } //========LNR 中序遍历 =============== void Inorder(BinTree T) { if(T) { Inorder(T->lchild); //中序遍历左子树printf("%c",T->data); //访...
