实验三 二叉树操作

实验三二叉树操作实验时间：2011年4月28日12:50-15:50（地点：7-215）实验目的：理解二叉树的逻辑特点和二叉树的性质；掌握二叉树的二叉链表存储结构，掌握二叉树的遍历算法的递归与非递归实现具体实验题目：（任课教师根据实验大纲自己指定）每位同学按下述要求实现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法1）问题描述：在主程序中提供下列菜单： 1…建立树 2…前序遍历树 3…中序(非递归)遍历树4…后序遍历树 0…结束2）实验要求：定义下列过程：CreateTree():按从键盘输入的前序序列，创建树PreOrderTree()：前序遍历树（递归）InOrderTree()：中序(非递归)遍历树LaOrderTree():后序遍历树（递归）1）算法设计思路简介在建立建立二叉树的函数时，开始使二叉树为空，str扫描完成循环，先定义左节点，再定义右节点，p指向二叉树的根结点，在建立输出二叉树的函数时，用括号法表示，先序遍历递归顺序是根，左，右，中序是左，根，右，后序是左，右，根。2）算法描述：可以用自然语言、伪代码或流程图等方式voidCreateBTNode(BTNode*&b,char*str)//由str串创建二叉树voidDispBTNode(BTNode*b)//以括号表示法输出二叉树voidPreOrder(BTNode*b)//先序遍历递归算法voidInOrder1(BTNode*b)//中序遍历非递归算法voidPostOrder(BTNode*b)//后序遍历递归算法3）算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等二叉树不能完全输出，见截图，我考虑过是由于字符串的长度问题影响，但经过调整发现不是这里的问题。代码源：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;//数据元素structnode*lchild;//指向左孩子structnode*rchild;//指向右孩子}BTNode;voidCreateBTNode(BTNode*&b,char*str)//由str串创建二叉树{BTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;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){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}voidDispBTNode(BTNode*b)//以括号表示法输出二叉树{ if(b!=NULL) {printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) {printf("("); DispBTNode(b->lchild); if(b->rchild!=NULL)printf(","); printf(")"); } } }voidPreOrder(BTNode*b)//先序遍历递归算法{ if(b!=NULL) {printf("%c",b->data);//访问根结点 PreOrder(b->lchild);//递归访问左子数 PreOrder(b->rchild);//递归访问右子数 }}voidInOrder1(BTNode*b)//中序遍历非递归算法{ BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL) {p=b; while(top>-1||p!=NULL) {while(p!=NULL) {top++; St[top]=p; p=p->lchild; } if(top>-1) {p=St[top]; top--; printf("%c",p->data); p=p->rchild; } }printf("\n"); }}voidPostOrder(BTNode*b)//后序遍历递归算法{ if(b!=NULL) {PostOrder(b->lchild);//递归访问左子数 PostOrder(b->rchild);//递归访问右子数 printf("%c",b->data);//递归访问根结点 }}voidmain(){ BTNode*b; CreateBTNode(b,"A(B(D,E(H(J,k(L,M(,N))))),C(F,G(,I)))"); printf("二叉树b:"); DispBTNode(b); printf("\n"); printf("先序遍历序列：\n"); print