实验六 二叉树1(1).doc

实验六二叉树【实验目的】1、 掌握二叉树的定义和各种基本存储结构，特别是链式实现；2、 掌握二叉树的建立以及各种遍历算法；3、 理解二叉树的性质；【实验要求】给出以及后序遍历，请大家完成算法：要求建立基于二叉链表的二叉树，建立二叉树的二叉链表存储并遍历，包括：1、 先序遍历；2、 中序遍历；3、 后序遍历；4、 层次遍历；5、 求叶子结点数。#include#include#include#define INFEASIBLE -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;typedef char TElemType;/二叉树二叉链表储存结构typedef struct BiTNode TElemType data; struct BiTNode *lchild, * rchild;BiTNode,* BiTree;/二叉树输入Status CreateBiTree(BiTree &T)char ch;scanf(%c,&ch);if(ch= ) T=NULL;else if(!(T=(BiTNode * )malloc(sizeof(BiTNode) exit(0); T-data=ch;CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK;/CreateBiTreeStatus Visit(TElemType e) printf(%c,e); return OK;/先序排列Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e) )if(T) if(Visit(T-data) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /PreOrderTraverse/中序遍历Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) )if(T) if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data) if(InOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /InOrderTraverse/后序遍历Status HouOrderTraverse(BiTree T, Status(* Visit)(TElemType e) )if(T) if(HouOrderTraverse(T-lchild,Visit) if(HouOrderTraverse(T-rchild,Visit) if(Visit(T-data) return OK; return ERROR; else return OK; /HouOrderTraverseint LeafCount_BiTree(BiTree T)/求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild&!T-rchild) return 1; /叶子结点 else return LeafCount_BiTree(T-lchild)+LeafCount_BiTree(T-rchild);/左子树的叶子数加 上右子树的叶子数 /LeafCount_BiTree main() BiTree T;int xz=3,xz1=4;do printf(.二叉树.n); printf(.1.按先序遍历输入二叉树.n); printf(.2.输出二叉树.n); printf(.3.退出.n); printf(.n);scanf(%d,&xz); if(xz=1) CreateBiTree(T);if(xz=2) printf(.输出二叉树.n);printf(.1.先序遍历输出.n);printf(.2.中序遍历输出.n);printf(.3.后序遍历输出.n);printf(.4.退出.n);printf(.n); scanf(%d,&xz1); if(xz=1) PreOrderTraverse(T,Visit); if(xz=2) InOrderTrav