大作业--二叉树.doc

数据结构作业 年级： 2004级（2）班 专业： 计算机科学与技术专业 学号： 200431500070 姓名： 陆雪 实现二叉树的各种算法 本项目“二叉树”的组成结构如图1所示：本程序的模块结构图如图2所示，图中方框表示函数，方框中指出函数名，箭头表示函数间的调用关系。 源程序包含如下函数： ·CreateBTNode(BTNode * b,char *str) 由str串创建二叉树。 ·*FindNode(BTNode *b,ElemType x) 返回data域为x的结点指针。 ·*LchildNode(BTNode *p) 找左孩子结点。 ·*RchildNode(BTNode *p) 找右孩子结点。 ·BTNodeDepth(BTNode *b) 求二叉树高度。 ·BTWidth(BTNode *b) 求二叉树宽度。 ·DispBTNode(BTNode *b) 输出二叉树。 ·TravLevel(BTNode *b) 层次遍历算法。 ·PreOrder(BTNode *b) 先序遍历算法。 ·InOrder(BTNode *b) 中序遍历算法。 ·PostOrder(BTNode *b) 后序遍历算法。 ·Nodes(BTNode *b) 求二叉树的结点个数。 ·LeafNodes(BTNode *b) 求二叉树的叶结点个数。 ·DispLeaf(BTNode *b) 输出所有叶子结点。 ·AllPath(BTNode *b,ElemType path[],int pathlen) 采用递归算法输出从根结点到叶子结点到叶子结点的路径。 ·LongPath(BTNode *b,ElemType path[],int pathlen, ElemType longpath[],int longpathlen) 求最长路径。 窗体顶端 窗体底端 图1. 二叉树项目组成 图2. 二叉树项目的程序结构图 #includestdio.h #includemalloc.h #define MaxSize 100 typedef char ElemType; /*二叉树的链式存储结构*/ typedef struct node { ElemType data; struct node *lchild; 一棵二叉树 struct node *rchild; } BTNode; /*创建二叉树CreateBTNode(*b,*str) */ void CreateBTNode(BTNode * b,char *str)/*由str串创建二叉链*/ { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; /*建立的二叉树初始时为空*/ ch=str[j]; while (ch!=\0) /*str未扫描完时循环*/ { switch(ch) { case (:top++;St[top]=p;k=1; break; /*为左孩子结点*/ case ):top--;break; case ,:k=2; break; /*为孩子结点右结点*/ default:p=(BTNode *)malloc(sizeof(BTNode)); p-data=ch;p-lchild=p-rchild=NULL; if (b==NULL) /**p为二叉树的根结点*/ b=p; else /*已建立二叉树根结点*/ { switch(k) { case 1:St[top]-lchild=p;break; case 2:St[top]-rchild=p;break; }