兰州大学数据结构中二叉树的的存储遍历交换子树统计二叉树的深度

要求：二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。代码利用C语言描述。//时间：2015.6.1//编程环境：win7-64，codeblocks，GUN-GCC编译器#includestdio.h#includestdlib.hstructNode*T;//声明全局变量TstructNode//建立结点{structNode*lson;chardata;structNode*rson;};structNode*CreatTree(structNode*T)//二叉树的建立{charch;scanf(%c,&ch);if(ch=='#'){T=NULL;}else{T=(structNode*)malloc(sizeof(structNode));if(!T)exit(1);//溢出错误T-data=ch;T-lson=CreatTree(T-lson);T-rson=CreatTree(T-rson);}returnT;}voidPreorderTraverse(structNode*T)//递归前序遍历{if(T==NULL)return;else{printf(%c,T-data);PreorderTraverse(T-lson);PreorderTraverse(T-rson);}}voidInOrder(structNode*T)//非递归中序遍历{structNode*stack[10],*p;inttop=-1;if(T!=NULL){p=T;while(top-1||p!=NULL){//扫描p的所有左节点并入栈while(p!=NULL){top++;stack[top]=p;p=p-lson;}if(top-1){//出栈并访问该节点p=stack[top];top--;printf(%c,p-data);//扫描p的右孩子*/p=p-rson;}}printf(\n);}}//非递归后序遍历二叉树voidPostOrder(structNode*T){structNode*stack[10],*p;intsign,top=-1;if(T!=NULL){do{//T所有左节点入栈while(T!=NULL){top++;stack[top]=T;T=T-lson;}//p指向栈顶前一个已访问节点p=NULL;//置T为已访问sign=1;while(top!=-1&&sign){//取出栈顶节点T=stack[top];//右孩子不存在或右孩子已访问则访问Tif(T-rson==p){printf(%c,T-data);top--;//p指向被访问的节点p=T;}else{//T指向右孩子节点T=T-rson;//置未访问标记sign=0;}}}while(top!=-1);printf(\n);}}voidexchange(structNode*T)//交换左右子树{if(T==NULL)return;structNode*x;x=T-lson;T-lson=T-rson;T-rson=x;//完成交换过程exchange(T-lson);exchange(T-rson);}inthigh(structNode*T){intlh,rh;if(T==NULL)return0;else{lh=high(T-lson);rh=high(T-rson);if(lhrh)returnlh+1;elsereturnrh+1;}}voidUI()//用户界面{printf(\n\n\n\n);printf(**************************************************************\n);printf(**\n);printf(*请选择菜单功能选项前的序号*\n);printf(**\n);printf(**************************************************************\n);printf(1.建立并存储树\n2.输出前序遍历结果\n3.输出中序遍历结果\n);printf(4.输出后序遍历结果\n5.交换左右子树\n6.统计高度\n7.退出程序\n\n\n);printf(请选择输入1-7\n);}voidmenu()//菜单{UI();intc;charb;//用于读取输入过程中的回车符while(1){scanf(%d,&c);if(c==7)break;switch(c){case1:printf(你选择的是1.建立并存储树\n请以前序遍历的顺序输入：\n);scanf(%c,&b);T=CreatTree(T);printf(\n二叉树已经建立并存储完成\n);UI();break;case2:printf(你选择的是2.输出前序遍历结果\n);scanf(%c,&b);PreorderTraverse(T);UI();break;case3:printf(你选择的是3.输出中序遍历结果\n);InOrder(T);UI();break;case4:printf(你选择的是4.输出后序遍历结果\n);PostOrder(T);UI();break;case5:printf(您选择的是5.交换左右子树\n);scanf(%c,&b);exchange(T);printf(\n已经完成了二叉树左右子树的交换\n);UI();break;case6:printf(您的选择是6.求二叉树的高度\n);inth=high(T);printf(二叉树的高度是%d\n,h);UI();break;}}}intmain(){menu();}