《数据结构课程设计（论文）--二叉树的基本操作》毕业学术论文.doc

PAGE10 / NUMPAGES10 数据结构 课程设计报告 设计题目：二叉树的基本操作 专业：计算机科技 院系：计算机学院 姓名： xx xx 学号： xxxxxxxx 时间：2013年9月22日 目录 设计要求3 问题描述3 需求分析3 详细设计3 概要设计3 各模块源代码3 用户手册9 总结10 设计要求 问题描述 设计一个与二叉树基本操作相关的演示程序。 需求分析 创建二叉树。按照用户需要构建二叉树 分别以先序、中序、后序遍历二叉树 查找子节点元素 详细设计（附源代码） 概要设计 //定义二叉树数据结构 typedef struct TNode { int num; struct TNode *lchild, *rchild; }TNode; 2．各模块源代码（包含main( )函数） #includestdio.h #includestdlib.h #define MaxLength 100 //定义二叉树数据结构 typedef struct TNode { int num; struct TNode *lchild, *rchild; }TNode; //声明全局变量root static TNode *root=NULL; //声明插入新结点的函数(根非空) int myInsert_Node(TNode *p, int n); //定义插入新节点的初始函数，拆开写的目的是递归时避免不必要的判断 void Insert_Node(int n) { if(root==NULL) //如果根结点不存在则创建 { root=(TNode *)malloc(sizeof(TNode)); root-num=n; root-lchild=NULL; root-rchild=NULL; } else { myInsert_Node(root, n);//非根结点的插入操作 } } int myInsert_Node(TNode *p, int n) { TNode *temp; if(np-num) //比当前结点小，则访问左子树 { if(p-lchild==NULL) //左子树为空，则插入该结点 { temp=(TNode *)malloc(sizeof(TNode)); temp-num=n; temp-lchild=NULL; temp-rchild=NULL; p-lchild=temp; return 0; } else //左子树不为空，则与左子树进行比较 { myInsert_Node(p-lchild,n); } } else //右子树同理 { if(p-rchild==NULL) { temp=(TNode *)malloc(sizeof(TNode)); temp-num=n; temp-lchild=NULL; temp-rchild=NULL; p-rchild=temp; return 0; } else { myInsert_Node(p-rchild,n); } } } //前序递归遍历二叉树 void Pre_travel(TNode *p) { if(p) { printf(%d ,p-num); Pre_travel(p-lchild); Pre_travel(p-rchild); } } //中序递归遍历二叉树 void Mid_travel(TNode *p) { if(p) { Mid_travel(p-lchild); printf(%d ,p-num); Mid_travel(p-rchild); } } //后序递归遍历二叉树 void Suf_travel(TNode *p) { if(p) { Suf_travel(p-lchild); Suf_travel(p-rchild); printf(%d , p-num); } } //中序非递归遍历二叉树 /* 从根节点开始，沿左子树一直走到没有左孩子的节点为止，并将所经过的节点的地址进栈； 　 当找到没有左孩子的节点时，从栈顶退出该节点并访问它，此时，此节点的左子树已访问完毕； 　 在用上述方法遍历该节点的右子树，如此重复到栈空为止。 */ void NRMid_travel(TNode *bitree) { TNode *stack[MaxLength]; TNode *p; int top=-1; p=bitree; do { whi