C语言二叉树基本功能.doc

源程序：#include #include #include #define OK 1#define ERROR 0#define MAXSIZE 50 /*定义队列的最大长度*/typedef char ElemType;/*定义二叉链表结构*/typedef struct TNodeElemType data;struct TNode *LChild, *RChild;BTNode,*BiTree;/*定义循环队列结构*/typedef structBiTree elementMAXSIZE;int front,rear;SeqQueue;/*初始化循环队列*/int InitQueue(SeqQueue *Q)Q-front=Q-rear=0;return OK;/*循环队列入队*/int EnterQueue(SeqQueue *Q,BiTree x)if(Q-rear+1)%MAXSIZE=Q-front) /*尾指针加1追上头指针，标志队列已满*/return ERROR;Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /*重新设置队尾指针*/return OK;/*循环队列出队*/int DeleteQueue(SeqQueue *Q,BiTree *x)if(Q-front=Q-rear) /*队列为空*/return ERROR;*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/return OK;/*判断循环队列是否*/int IsEmpty(SeqQueue *Q)if(Q-front=Q-rear)return OK;elsereturn ERROR;/*创建二叉链表*/int CreateBTree(BTNode * &bt)char ch;bt=NULL; ch = getchar(); if(ch=.)bt=NULL; else bt=(BTNode *)malloc(sizeof(BTNode); /*生成一个新结点*/ bt-data=ch; CreateBTree(bt-LChild); /*生成左子树*/ CreateBTree(bt-RChild); /*生成右子树*/ return OK;/*先序遍历二叉树*/int PreOrder(BTNode *bt) /* root为指向二叉树(或某一子树)根结点的指针*/if (bt!=NULL)printf(%c ,bt-data);PreOrder(bt -LChild); /*先序遍历左子树*/PreOrder(bt -RChild); /*先序遍历右子树*/return OK;/*中序遍历二叉树*/int InOrder(BTNode *bt) /*root为指向二叉树(或某一子树)根结点的指针*/if (bt!=NULL)InOrder(bt-LChild); /*中序遍历左子树*/printf(%c ,bt-data);InOrder(bt-RChild); /*中序遍历右子树*/return OK;/*后序序遍历二叉树*/int PostOrder(BTNode *bt) /* root为指向二叉树(或某一子树)根结点的指针*/if(bt!=NULL)PostOrder(bt -LChild); /*后序遍历左子树*/PostOrder(bt -RChild); /*后序遍历右子树*/printf(%c ,bt-data);return OK;/*计算节点数*/int leaf(BTNode *bt)int i;if(bt=NULL)i=0;else if(bt-LChild=NULL)&(bt-RChild=NULL)i=1;else i=leaf(bt-LChild)+leaf(bt-RChild); /* 叶子数为左右子树的叶子数目之和 */return i;/*遍历二叉树的叶子节点并输出*/int PreOrderNode(BTNode *bt) /*先序遍历二叉树, root为指向二叉树根结点的指针*/if (bt!=NULL)if (bt -LChild=NULL & bt -RChild=NULL)printf(%c ,bt -data); /*输出叶子结点*/PreOrder(bt -LChild); /*先序遍历左子树*/PreOrder(bt -RChild); /*先序遍历右子树*/return OK;/*层次遍历二叉树显示*/int LayerOrder(BTNode bt)SeqQueue *Q; BiTree p;Q=(SeqQueue *)malloc(sizeof(SeqQueue);p=(BiTree )malloc(sizeof(BiTree);InitQueue(Q);if(&bt=NULL)return ERROR;EnterQueue(Q,&bt);while(!IsEmpty(Q)DeleteQueue(Q,&p);printf(%c ,p-data);if(p-LChild)EnterQueue(Q,p-LChild);if(p-RChild)EnterQueue(Q,p-RChild);return OK;void main()BTNode *bt;int n,i; while(1)printf(请选择功能：1、构造二叉树 2、先序输出 3、中序输出 4、后序输出n 5、统计叶子节点数目 6、输出叶子节点 7、竖向显示二叉树（即按层显示） 8、退出n);scanf(%d,&n);switch(n)case 1:getchar();printf(请输入元素：);i=CreateBTree(bt);if(i!=0)printf(输入完毕n);elseprintf(n输出错误n);break;case 2:printf(二叉树先序序列为：);i=PreOrder(bt);if(i)printf(n输出完毕n);elseprintf(n输出错误n);break;case 3:printf(中序序列为：);i=InOrder(bt);if(i)printf(n输出完毕n);elseprintf(n输出错误n);break;case 4:printf(后序序列为：);i=PostOrder(bt);if(i)printf(n输出完毕n);elseprintf(n输出错误n);break;case 5:i=leaf(bt);if(i=0)printf(叶子节点数为：%dn,i);elseprintf(n输出错误);break;case 6:printf(先序遍历序列时叶子的节点为：);i=PreOrderNode(bt);if(i)printf(n输出完毕n)