二叉树结点╲t课程设计报告.doc

PAGE PAGE 10 目录 TOC \o 1-3 \h \z \u 一 需求分析 2 二 概要设计 2 三 详细设计 3 四 调试分析和测试结果 5 五 总结 7 六 参考文献 8 七 致谢 8 八 附录 8 一 需求分析 问题描述：交换二叉树中所有结点的左、右子树，该二叉树以二叉链表作为存储结构。 基本思想：设二叉树的根指针为s，且以二叉链表表示，可利用一个类型为Q的指针队列来实现，且设队列单元包含两个域，一个为front，一个为rear，整个队列容量为maxsize，当树非空时，将当前的树根结点入队列，同时将当前队列顶元素出队列当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入队列，这样反复进行，直到队列空为止。 图1-1是该课题的功能模块图： 二叉树结点的左、右子树的交换 二叉树结点的左、右子树的交换 重新建立二叉树 交换左右子数 先根遍历二叉树 退出 图 1-1 二 概要设计 该课题主要分为三个功能模块：重新建立二叉树、交换左右子数、先根遍历二叉树。这里主要用到了队列及二叉树的知识，先对二叉树进行层次遍历，然后再进行左右子树交换操作，最后再进行先根遍历二叉树，这就实现了二叉树节点的左右子树交换。三个功能模块相互独立又相互关联，独立仅在于各自操作互不影响，而关联在于后两个功能可以对当前建立的二叉树进行操作，产生不同的结果。 该功能流程图（图2-1）如下： 开 始 开 始 输入二叉树的节点（以“！“结束） enter 重新建立二叉树 交换左右子数 先根遍历二叉树 菜 单 2 1 3 0 结 束 图2-1 三 详细设计 本课题为二叉树结点的左、右子树的交换，主要分为三个模块：重新建立二叉树、交换左右子数、先根遍历二叉树。各模块的详细设计如下： 首先定义结构体类型及二叉树结点类型，如下所示： typedef char datatype; // 树的结点数据类型为字符型，可以根据需要修改 typedef struct node *pointer; // 定义二叉树结点类型 struct node { datatype data; //结点数据 pointer lchild,rchild; //左右孩子结点 }; 三个模块各写三个函数，分别如下所示： bitree level_creat() //由层次序列建立二叉树，返回根指针 { char ch; ch=cin.get(); int front,rear; pointer root,s; root=NULL; //置空二叉树 front=rear=0; //置空队列 //while(cinch,ch!=!) while(cinch,ch!=!) { if(ch!=@) //非虚结点，建立新结点 { s=new node; s-data=ch; s-lchild=s-rchild=NULL; } else s=NULL; rear++; Q[rear]=s; //不管结点是否为虚都要入队 if(rear==1) { root=s; front=1; } //第一个点是根，要修改头指针，他不是孩子 else if(s Q[front]) //孩子和双亲都不是虚结点 if(rear%2==0) Q[front]-lchild=s; // rear是偶数，新结点是左孩子 else { Q[front]-rchild=s; //rear 是奇数，新结点是右孩子 front++; } } return root; } void exchange(bitree t) //交换左右子数函数 { pointer p; if(t==NULL) return; //空树，直接返回 p=t-lchild; t-lchild=t-rchild; t-rchild=p; //交换 exchange(t-rchild); //遍历原左子树 exchange(t-lchild); //遍历原右子树 } void preorder(bitree t) //先根遍历函数 { if(t==NULL) return; coutt-data ; //先访问跟 preorder(t-lchild); //先根遍历左子树 preorder(t-rch