实验三 二叉树操作的实现 代码及运行结果图

二叉树操作的实现

#include #include #include typedef struct BiTNode {

int data;

BiTNode *lchild,*rchild; }BiTNode,*BiTree;

int Nil=0; // 设整型以0为空 void visit(int e) { printf(\ }

void CreateBiTree(BiTree &T) {

int number;

scanf(\ if(number==Nil) T=NULL;

else // 结点的值不为空

{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点 if(!T)

exit(-2);

T->data=number; // 将值赋给T所指结点 CreateBiTree(T->lchild); //C 递归构造左子树 CreateBiTree(T->rchild); // 递归构造右子树 } }

void DestroyBiTree(BiTree &T) {

if(T) // 非空树

{ DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); } }

void PreOrderTraverse(BiTree T,void (*Visit)(int)){

if(T)

{ Visit(T->data);

PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树 PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树 } }

void InOrderTraverse(BiTree T,void(*Visit)(int)) { if(T)

{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树 Visit(T->data); // 再访问根结点

InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树 } }

void PostOrderTraverse(BiTree T,void(*Visit)(int)) {

if(T) // T不空

{ PostOrderTraverse(T->lchild,Visit); PostOrderTraverse(T->rchild,Visit); Visit(T->data); // 最后访问根结点 } }

int LeafNum( BiTree T){

if(!T)

return 0;

else

if(!T->lchild&&!T->rchild)

return 1;

else

// printf(\

return LeafNum(T->lchild)+LeafNum(T->rchild); }

void main() {

BiTree T; int num;

//InitBiTree(T); // 初始化二叉树T

printf(\按先序次序输入二叉树中结点的值,输入0表示节点为空\\n\ CreateBiTree(T); // 建立二叉树T printf(\先序递归遍历二叉树：\\n\

PreOrderTraverse(T ,visit); // 先序递归遍历二叉树T printf(\中序递归遍历二叉树：\\n\

InOrderTraverse(T,visit); // 中序递归遍历二叉树T printf(\后序递归遍历二叉树：\\n\

PostOrderTraverse(T,visit); // 后序递归遍历二叉树T printf(\叶子结点总数为：\\n\ num= LeafNum (T); printf(\ }