数据结构课程设计-二叉树的遍历 [文档在线提供].docVIP

/*一、需求分析 本题通过创建一个二叉树的二叉链表，在主函数中采用循环控制的方式建立一棵二叉排序树，然后再采用递归的方式遍历这个二叉排序树并输出各结点的值 二、概要设计 用二叉链表为存储结构，每一结点都有一个数据域，指向左孩子的 指针和指向右孩子的指针， 定义一个插入函数，用当前用户输入的值，逐一与二叉树中各结点的值比较，根据二叉排序树的特点使之插入适当的位置； 定义一个遍历二叉排序树的函数，用来在主函数中调用 三、详细设计*/ #includestdio.h #includestdlib.h struct NodeType{ int data; NodeType *lchild,*rchild;}; int searchData(NodeType *t,NodeType **p,NodeType **q,int x) {int flag=0;*q=t; while(*q) {if(x(*p)-date) {*p=*q; *q=(*q)-rchild;} //将当前结点的右孩子置为新根 else {if(x(*p)-date) //x小于当前结点*q的元素值 {*p=*q; *q=(*q)-lchild;} //将当前结点的左孩子置为新根 else {flag=1;break;} //查找成功，返回 } } return flag; } //定义插入函数 int InsertNode(NodeType **t,int x) {NodeType *p=*t,*q,*s; int flag=0; if(!searchDate(*t,p,q,x)) //在*t为根的子树上查找 {s=(NodeType*)malloc(sizeof(NodeType)); //申请结点，并赋值 s-date=x;s-lchild=NULL;s-rchild=NULL; flag=1; //设置插入成功标志 if(xp-date)p-rchild=s; //插入结点为p的右孩子 else p-lchild=s; //插入结点为p的左孩子 } return flag; } //定义遍历函数 void preorder (NodeType *p) //从右到左中序遍历二叉树 {if(p==NULL) return; if(p-rchild!=NULL)preorder(p-rchild); printf(%d,p-data); if(p-lchild!=NULL)preorder(p-lchild);} void main() {int x,y; NodeType *t; t=(NodeType *)malloc(sizeof(NodeType)); printf(请输入跟结点\n); scanf(%d,x); t-data=x; t-lchild=NULL; t-rchild=NULL; scanf(%d,x); while(x!=-1) //当x==-1时表示程序停止接收数据 {y=InsertNode(t,x); if(!y) printf(插入成功); printf(请输入结点数据\n); scanf(%d,x);} printf(从小到大输出各结点数据\n ); preorder(t); //在主函数中调用遍历函数 } 免责声明：文档在线网（文档中国）中所有的文档资料均由文档在线网会员提供。文档在线网会对会员提供的文档资料进行筛选和编辑，但是并不声明或保证其内容的合法性、正确性或可靠性。该文档资料的版权属于提供者所有，有关版权的问题请直接与提供者联系。